文章目录

前言 红黑树 为什么要有红黑树 红黑树的特征 新增节点 问题：如何判断用旋转还是用变色的手段来满足红黑树的规则？ 最坏情况 删除 总结 下一步

前言

前面两篇文章： 【技术点】数据结构–二叉树（一） 【技术点】数据结构–二叉树（二） 讲了普通二叉树然后再到平衡搜索二叉树(BBST，Balance Binary Search Tree，又称AVL树)。 这一篇来讲讲更厉害(也就是更复杂)的一种树：红黑树(RBTree, Red Black Tree)。

红黑树

为什么要有红黑树

前面讲到的AVL树在搜索性能上已经达到了二分查找的性能：O(lgn)。 在插入时的性能也