红黑树的完美平衡

一句话总结

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

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

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

红黑树是一种经过优化的能够自平衡的二叉搜索树。任何时候，任何情况下，它的树高都能保持在 O(logN)（完美平衡），这样就能保证增删查改的时间复杂度都是 O(logN)。

不过完美平衡的代价是代码实现比较复杂，本文不会深入红黑树的实现细节，而是通过算法可视化让你对红黑树有一个直观的认识。

具体的代码实现，我会更新在数据结构的设计章节的选学部分，因为红黑树确实不是必须掌握的数据结构，就算在工作和刷题中需要使用 TreeMap/TreeSet，直接调用标准库就可以了，没必要有源码级的理解。

红黑树始终保持完美平衡，即从根节点到叶子节点的每一条树枝上的「黑色节点」个数完全相同。你可以认为红黑树中的红色节点属于辅助节点，且不会出现很多，所以计算树的高度时可以只考虑黑色节点