红黑树插入新节点图文详解

发布:2022-10-26 11:11:18
阅读:1319
作者:网络整理
分享:复制链接

红黑树中插入新节点图文流程

第一步,指定新节点newNode=20;设y成为叶子,x成为红黑树的根,初始树如下图:

红黑树初始树

第二步,检查树是否为空,即x是否为NIL。

如果是,newNode则作为根节点插入并将其着色为黑色。

否则,将newNode与根比较,如果newNode大于根,则遍历右子树,并与右子节点比较;反之,遍历左子树,并与左子节点比较。

第三步,重复此操作,直至找到插入位置。具体如下图:

红黑树插入新节点图文

红黑树插入新节点图文

第四步,因此时新节点newNode不为根,将新节点newNode分配成红色,并分配叶。

红黑树插入新节点图文

第五步,因newNode为红色,其父级节点也是红色,违反红黑树平衡性质。需要进行旋转,重新分配节点,来平衡该红黑树,直至输出最终红黑树。

输出红黑树

扫码进群
微信群
免费体验AI服务