3.红黑树

2.红黑树(Red-Black Tree)

红黑树是二叉搜索树的一种改进，是另一种平衡树。我们知道二叉搜索树在最坏的情况下退化成了一个链表，而红黑树在每一次插入或删除节点之后都会花O(log N)的时间来对树的结构作修改，以保持树的平衡。也就是说，红黑树的查找方法与二叉搜索树完全一样；插入和删除节点的方法前半部分与二叉搜索树完全一样，而后半部分添加了一些修改树的结构的操作。

红黑树的定义：

1. 每个节点是红色或者黑色
2. 根节点是黑色
3. 每个叶子节点都是黑色的(这里的叶子节点指的并非指6,11,15,22,27这样的节点，而是图中的NIL节点，表示这是树的尾端。)
4. 对于任意的一个节点，其到尾端节点(NIL)的路径都包含了相同数目的黑节点。

参考：一步一图一代码,一定要让你真正彻底明白红黑树

请我一杯咖啡吧！

赞赏

微信打赏