红黑树的编程思考 200行实现插入删除测试源码
-
红黑树规范 a. 根为黑色 通过根的变色,可以实现整体黑色的增减 b. 每条路径黑色数量相等 c. 红色不相邻 结合2点,最长路径不超两倍,保证基本分布平均
-
红黑树来自于3节点实践及各种旋转变化,是原理性的东西,但对于编程来说,可以不考虑这些,只用三个函数即可实现
-
顶点替换函数(不用考虑左右旋转,按关系按键值都可确定,总是交换颜色) a. 子为父:影响三棵树 兄弟树 Near树(在父子中间的孙子,需要交给父)Far树 b. 红黑分析:Near树 子父->父子,总不变 c. 兄弟树 父色->父色+子色 Far树 子色+父色->子色 d. 如果交换子父颜色:兄弟树多子色 ,Far树少子色 e. 红变化:子为红色,黑不变,红子在满足条件的情况下,任意进位,不影响黑高 f. 黑变化:兄弟树多一黑,Far树少一黑,如果Far节点为红,涂黑后黑不变(用于兄弟树黑子删除)
-
红平衡函数:增加节点必为红,按其键值找到父节点,执行递归函数 a. 递归出口:父节点为空,设为根,变黑,此为递归终点,黑高增加一个 b. 递归出口:父节点为黑,满足红黑要求 c. 父节点为红,叔叔为红,则将父与叔叔变黑,将祖节点变红,由祖节点递归 d. 递归出口:父节点为红,键值如果在祖及父中间,自己先替父,再替祖 e. 递归出口:父节点为红,不在祖及父中间,父替祖
-
删除节点 a. 删除时,先找替代,其替代必为其最靠近的点,右子的最左,或左子的最右,任选一个即可,以下选右边最近的点 b. 替代可能有右子为红,将右子进位,可将替代变红 c. 替代可能为自身,此时可能左子为红,将此子进位,替代变红 d. 删除时,如替代为红,直接删除
-
黑平衡函数:黑子删除 需要本通道增加一黑,兄弟通道黑不变 a. 递归出口:为根 递归终点,黑高减少一个 b. 递归出口:不为根必有父,为黑子必有兄弟,如其Far节点为红,将其涂黑后,用兄弟进位,本通道多一黑,任务完成 c. 递归出口:近侄为红,近侄替兄弟,变为楼上情况,再替父,完成 d. 递归出口:如父为红,将父变黑,兄弟变红(兄弟无红子,满足红黑条件) e. 如兄弟为红,其红子代父,红黑不变,再递归检查,等于检查兄弟过来的子树,总有出口 f. 全黑,将兄弟变红,兄弟树也减少一黑,用父递归
-
将替代断开连接,并替换删除目标,复制其颜色即可,以上均要进行根检查