数据结构--二叉树
目录
有序二叉树：
平衡二叉树：
在有序二叉树的基础上得来的，且左右子树的高度差绝对值不能超过1.
调整策略：
1、LL型调整策略
注意要找造成不平衡节点的最近的不平衡节点
2、RR型
10插入后，5是不平衡的节点，往右走两步。中间节点为8
3、LR型
转换为LL型
4、RL型
平衡二叉树太耗费资源，引入了红黑树。红黑树的基础是234树
234树：
变成四个节点的后，取中间节点向上走一层，连接两端
红黑树
二节点用黑色表示，三节点用黑红，四节点用黑红红表示，然后按照234树变成红黑树。
红黑树特点：
1、红黑树只有红色和黑色两种颜色
2、根节点一定是黑色的，
3、叶子节点是存在的，统一为黑色
4、如果一个节点的值是红色的那么他的子节点的值一定是黑色的
5、从根节点到任意一个叶子节点，路径上的黑色节点数目相同。（黑色节点数就是234数的高度）
为什么红黑树是最优二叉树？
最长链不超过最短链的二倍
时间复杂度比有序二叉树更稳定，平衡调整更简单
哈夫曼树和哈夫曼编码
自定义变长编码表容易引起歧义
原文地址：https://blog.csdn.net/a13641376265/article/details/145169370
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！