ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据结构--二叉树 [打印本页]

作者: 汕尾海湾 时间: 2025-1-17 05:10
标题: 数据结构--二叉树
目次
有序二叉树：
平衡二叉树：
234树：
红黑树
红黑树特点：
为什么红黑树是最优二叉树？
哈夫曼树和哈夫曼编码

有序二叉树：

平衡二叉树：

在有序二叉树的基础上得来的，且左右子树的高度差绝对值不能超过1.
调解计谋：
1、LL型调解计谋

留意要找造成不平衡节点的最近的不平衡节点
2、RR型

10插入后，5是不平衡的节点，往右走两步。中间节点为8
3、LR型

转换为LL型

4、RL型

平衡二叉树太耗费资源，引入了红黑树。红黑树的基础是234树

234树：

变成四个节点的后，取中间节点向上走一层，毗连两端

红黑树

二节点用黑色表现，三节点用黑红，四节点用黑红红表现，然后按照234树变成红黑树。

红黑树特点：

1、红黑树只有赤色和黑色两种颜色
2、根节点一定是黑色的，
3、叶子节点是存在的，同一为黑色

4、如果一个节点的值是赤色的那么他的子节点的值一定是黑色的
5、从根节点到恣意一个叶子节点，路径上的黑色节点数目雷同。（黑色节点数就是234数的高度）
为什么红黑树是最优二叉树？

最长链不超过最短链的二倍

时间复杂度比有序二叉树更稳定，平衡调解更简单

哈夫曼树和哈夫曼编码

自界说变长编码表轻易引起歧义

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)