当前位置:首页 > 经验 >

二叉树怎么转化为红黑树(红黑树和平衡二叉树区别)

来源:原点资讯(www.yd166.com)时间:2022-11-14 14:25:16作者:YD166手机阅读>>

二叉树怎么转化为红黑树,红黑树和平衡二叉树区别(21)

6.3 删除的叶子节点为 2- 节点

当删除的叶子节点是 2- 节点,则将节点删除后,需要对树进行调整,调整规则如下:

1)当前节点的父节点是 2- 节点,兄弟节点不为 2- 节点,则将兄弟节点的一个 key 上移成父节点,而父节点下移成子节点,此时树满足 2-3-4 树,完成调整。

(2)当前节点的父节点是 2-节点,兄弟节点也为 2- 节点,则此时将父节点与兄弟节点合并,将合并后的节点看成当前节点,然后重复的判断,即判断合并后的当前节点的兄弟节点与父节点的情况,然后走对应的(1)(2)(3)处理,直到满足 2-3-4 树,完成调整。

(3)当前节点的父节点不为 2- 节点,即此时有两个或三个兄弟节点,此时需要根据相邻兄弟节点情形进行调整,规则如下:

(3)-a:若当前节点的相邻兄弟节点为非 3 个 key ,则父节点的一个 key 下移,与相邻兄弟节点合并,此时树满足2-3树,完成调整。

(3)-b:若当前节点的相邻兄弟节点为 3 个 key ,则父节点的一个 key 下移成 1 个 key 的节点,相邻兄弟节点的一个 key 上移与父节点合并,此时树满足 2-3-4 树,完成调整。

图解:

二叉树怎么转化为红黑树,红黑树和平衡二叉树区别(22)

二叉树怎么转化为红黑树,红黑树和平衡二叉树区别(23)

图解:

二叉树怎么转化为红黑树,红黑树和平衡二叉树区别(24)

栏目热文

红黑树对比二叉树好处有哪些(二叉树到底有啥用)

红黑树对比二叉树好处有哪些(二叉树到底有啥用)

二叉查找树:#二叉查找树就是左结点小于根节点,右结点大于根节点的一种排序树,也叫二叉搜索树。也叫BST,英文Binary...

2022-11-14 14:26:52查看全文 >>

二叉平衡树和红黑树的区别(红黑树为什么是平衡二叉树)

二叉平衡树和红黑树的区别(红黑树为什么是平衡二叉树)

二叉搜索树:也称二叉查找树,或二叉排序树。定义也比较简单,要么是一颗空树,要么就是具有如下性质的二叉树:(1)若任意节点...

2022-11-14 14:15:53查看全文 >>

100斤猪饲料加多少小苏打(100斤料拌多少小苏打)

100斤猪饲料加多少小苏打(100斤料拌多少小苏打)

小苏打,我们在做面点经常用到,又叫面起子,属于食品添加剂,听说在养猪上也有不少妙用,总结了以下几点用法,给大家参考。1、...

2022-11-14 14:28:12查看全文 >>

猪饲料营养成分配方(猪饲料配方到底含不含激素)

猪饲料营养成分配方(猪饲料配方到底含不含激素)

仔猪的饲养管理很关键,仔猪能够健康的生长发育,就是一个好的开端,仔猪饲养得越好,以后育肥的效果就会更好,所以,我们一定要...

2022-11-14 14:25:42查看全文 >>

喂牛的最佳饲料配方(牛饲料配方大全)

喂牛的最佳饲料配方(牛饲料配方大全)

我们养牛户很多都不知道牛喂什么饲料比较好,牛要养得好,有更高的经济收益,饲料肯定是少不了,关键是选择合适的饲料,才能使牛...

2022-11-14 14:25:06查看全文 >>

红黑树和b+树的区别(b树和b+树的优缺点)

红黑树和b+树的区别(b树和b+树的优缺点)

二分查找算法二分查找又称折半查找,它是一种效率较高的查找方法。二分查找要求:(1)必须采用顺序存储结构 (2)必须按关键...

2022-11-14 14:11:36查看全文 >>

二叉树对比红黑树(二叉树数据图解)

二叉树对比红黑树(二叉树数据图解)

在讲解HBase的LSM合并树之前,我们需要来了解一些常用的数据结构知识。跳表链表上图是一个有序链表,我们要检索一个数据...

2022-11-14 14:23:35查看全文 >>

红黑树解决了什么问题(红黑树解决冲突)

红黑树解决了什么问题(红黑树解决冲突)

来源公众号:苦逼的码农作者:帅地红黑树算是很难的一种数据结构吧,一般很少考察插入、删除等具体操作步骤,如果遇到要你手写红...

2022-11-14 14:11:08查看全文 >>

红黑树结构优缺点(红黑树解决什么问题)

红黑树结构优缺点(红黑树解决什么问题)

1. 红黑树的概念红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过...

2022-11-14 14:35:35查看全文 >>

红黑树和平衡二叉树区别(详解什么是平衡二叉树)

红黑树和平衡二叉树区别(详解什么是平衡二叉树)

一,AVL树(平衡二叉树)(1)简介AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现...

2022-11-14 14:23:26查看全文 >>

文档排行