第七章 查找 七、红黑树

一、为什么要发明红黑树

因为：

平衡二叉树AVL:插入/删除很容易破坏“平衡”特性，需要频繁调整树的形态。如:插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大），再进行LL/RR/LR/RL调整。

平衡二叉树:适用于以查为主、很少插入/删除的场景。

而且：

红黑树RBT:插入/删除很多时候不会破坏“红黑”特性，无需频繁调整树的形态。即便需要调整，一般都可以在常数级时间内完成。

红黑树:适用于频繁插入、删除的场景，实用性更强。

所以：

要发明红黑树

二、定义

1、红黑树是二叉排序树：

左子树结点值 > 根结点值 > 右子树结点值 

2、与普通BST相比：

1. 每个结点或是红色，或是黑色的②根节点是黑色的
2. 叶结点（外部结点、NULL结点、失败结点）均是黑色的
3. 不存在两个相邻的红结点（即红结点的父节点和孩子结点均是黑色）
4. 对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同

3、性质1

从根节点到叶结点的最长路径不大于最短路径的2倍

4、性质2

有n个内部节点的红黑树高度

5、红黑树查找操作时间复杂度

三、红黑树的查找

四、红黑树的插入

五、红黑树的删除