红黑树的完美平衡及可视化

labuladong原创约 853 字

前置知识

阅读本文前，你需要先学习：

一句话总结

红黑树是自平衡的二叉搜索树，它的树高在任何时候都能保持在 $O(\log N)$ （完美平衡），这样就能保证增删查改的时间复杂度都是 $O(\log N)$ 。

可视化面板支持创建红黑树：

二叉搜索树的应用及可视化讲了普通的二叉搜索树存储键值对实现 TreeMap/TreeSet 的思路。

二叉搜索树的操作效率取决于树高，树结构越平衡，树高就接近 $\log N$ ，增删查改的效率就比较高。而普通二叉搜索树最关键的问题是它不会自动对树进行平衡，特殊的情况下会退化成链表，增删查改的时间复杂度退化为 $O(N)$ 。

下面这个可视化面板就是一个例子，如果插入若干个有序的键值对，你就能发现每次新增的键都会被插入到最右侧，导致这棵二叉搜索树退化成了链表：