在红黑树中插入新节点图文流程
第一步,指定新节点newNode=20;设y成为叶子,x成为红黑树的根,初始树如下图:
第二步,检查树是否为空,即x是否为NIL。
如果是,newNode则作为根节点插入并将其着色为黑色。
否则,将newNode与根比较,如果newNode大于根,则遍历右子树,并与右子节点比较;反之,遍历左子树,并与左子节点比较。
第三步,重复此操作,直至找到插入位置。具体如下图:
第四步,因此时新节点newNode不为根,将新节点newNode分配成红色,并分配叶。
第五步,因newNode为红色,其父级节点也是红色,违反红黑树平衡性质。需要进行旋转,重新分配节点,来平衡该红黑树,直至输出最终红黑树。