红黑树插入算法
一、题目描述
将数组转化为红黑树(add函数共包含四部分:add()、insertFixup()、rotateRight()、rotateLeft(),增加函数,颜色调整、左旋、右旋)。
二、解题思路
步骤一:常规插入:树的二分查找,然后对插入点进行颜色调整。
步骤二:调整方式见下图。
步骤三:部分结点需要进行左旋和右旋。
三、注意事项
1)步步为营,必须弄清楚所以指针去向。
2)因为Java语言的原因,栈内的指针不保存,因此需要每次返回root。
3)左旋右旋发生后,当前结点发生变化,需要更改当前结点。
4)严格按照上图思考,先判断叔叔是祖父节点的左孩子还是右孩子?再对当前结点是左孩子还是右孩子进行判断。
四、代码实现
见我的github:RedBlackTree