通俗讲红黑二叉树原理,红黑树为什么是平衡二叉树

首页 > 经验 > 作者:YD1662022-11-14 14:42:53

无法通过变色而进行旋转的场景分为以下四种:

左左节点旋转

这种情况下,父节点和插入的节点都是左节点,如下图(旋转原始图1)这种情况下,我们要插入节点 65。

规则如下:以祖父节点【右旋】,搭配【变色】。

通俗讲红黑二叉树原理,红黑树为什么是平衡二叉树(17)

按照规则,步骤如下:

通俗讲红黑二叉树原理,红黑树为什么是平衡二叉树(18)

左右节点旋转

这种情况下,父节点是左节点,插入的节点是右节点,在旋转原始图 1 中,我们要插入节点 67。

规则如下:先父节点【左旋】,然后祖父节点【右旋】,搭配【变色】。

按照规则,步骤如下:

通俗讲红黑二叉树原理,红黑树为什么是平衡二叉树(19)

右左节点旋转

这种情况下,父节点是右节点,插入的节点是左节点,如下图(旋转原始图 2)这种情况,我们要插入节点 68。

规则如下:先父节点【右旋】,然后祖父节点【左旋】,搭配【变色】。

通俗讲红黑二叉树原理,红黑树为什么是平衡二叉树(20)

上一页12345下一页

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.