改写有序表的题目核心点

1、核心点

1）分析增加什么数据项可以支持题目

2）有序表一定要保持内部参与排序的key不重复

【补充说明：要存储重复的key值，要么将相同的key压在一起，要么将每个key再封装一层，用内存地址区分】

3）增加这个数据项了，在平衡性调整时，保证这个数据项也能更新正确

4）做到上面3点，剩下就是搜索二叉树怎么实现想要的接口的问题了

2、浅谈红黑树

红黑树的五个条件：

1. 每个节点非黑即红；
2. 根节点是黑色；
3. 叶节点(NIL)是黑色【虚拟空节点，并不是看得见的叶子节点】
4. 如果一个节点是红色，则它的两个子节点是黑色的；
5. 从根节点触发到所有叶节点的路径上，黑色节点数量相同。

先回忆AVL树和SB树的平衡条件：

• AVL树左右子树的高度差不超过1，是非常严苛的平衡；
• SB树中每棵子树的大小不小于其兄弟的子树大小，其实质就是保证了较少节点的子树和较多节点的子树的节点数量差不超过两倍，是模糊的平衡性。

而结合红黑树的第4和5个条件，也就是红黑树最长路径和最短路径之间的关系是：$最长路径=2\times 最短路径$

可见，红黑树本质上也是用树高来控制平衡，但是相比AVL树控制得更松散，依然是模糊的平衡性，目的和SB树一样，减少频繁地调整，内存IO消耗较低。

了解了之前AVL树和SB树的平衡调整，红黑树的平衡调整也是类似的。