【数据结构】1、红黑树,节点插入,修复平衡操作总结(针对jdk8中hashmap冲突过多链表转红黑树)

二叉树节点插入

0.如果只有一个节点,那么就直接作为根,涂黑,如果父为黑,或者祖父为空,那么不做操作

1.叔叔节点不为空且为红 那么就修改父,叔叔,祖父节点颜色,最后把当前节点设置为祖父节点,在进行平衡

2.如果父为右节点,并且叔叔节点为空或者为黑,当前节点是右节点,如果父不为空, 那么把父设置为黑,然后如果祖父不为空,那么祖父改为红,并对祖父进行左旋,然后再平衡

3.如果父为右节点,并且叔叔节点为空或者为黑,当前节点是左节点, 吧当前节点的父节点进行右旋

4.如果父为左节点,并且叔叔节点为空或者为黑,当前节点是左节点, 吧当前节点的祖父节点改为红进行右旋

5.如果父为左节点,并且叔叔节点为空或者为黑,当前节点是右节点, 吧当前节点的祖父节点改为红进行左旋

画出来的几个过程图

 

原文地址:https://www.cnblogs.com/cutter-point/p/10976416.html