各种树的介绍
树
- 一个根节点,每个结点可能有多个子节点
二叉树
- 一个根节点,或者为空
- 每个结点只有两个子节点
二叉搜索树
也叫二叉查找树
- 首先是一棵二叉树
- 左边孩子结点的值都小于当前结点
- 右边孩子结点的值都大于当前结点
缺点
- 极端情况下,树模型会退化成链表,查找变成了 O(n) 复杂度的
平衡二叉搜索树(AVL树)
也叫平衡二叉查找树
- 首先是一棵二叉搜索树
- 对每个结点而言, 左右孩子结点的深度差值不能超过1, 从而保证查找是 O(log n) 的
- 控制平衡方法: 参考链接AVL树详解
- 左-左型: 右旋
- 右-右型: 左旋
- 左-右型: 左旋 + 右旋
- 第一步左旋后面部分,变成 左-左 型
- 第二步使用右旋修正 左-左 型
- 右-左型: 右旋 + 左旋
- 第一步右旋后面部分,变成 右-右 型
- 第二步使用左旋修正 右-右 型
缺点
- 每棵树的左右子树高度最多差1这个要求太严了
- 几乎每次插入或者删除结点时都会造成规则破坏, 也就需要频繁的通过左旋或者右旋操作来修正
- 插入和删除太频繁的场景中不太适合使用AVL树, 性能会因为左右子树高度最多差1这个规则频繁被打破而降低
红黑树
- 首先是一棵二叉搜索树
- 每个结点不是黑色就是红色
- 根节点为黑色
- 每个叶子结点都为黑色的空结点(NULL)
- 注意: 叶子节点不存数据
- 任何相邻结点不同时为红色
- 注意,相邻结点可以为黑色,且可以某条路径上全是黑色
- 对每个结点而言,当前结点到叶子结点的所有路径包含相同的黑色结点数
优点
- 能保证查找时间复杂度是 O(log n) 的, 和AVL树差不多
- 证明: [待更新]
- 插入和删除操作中不会频繁破坏红黑树的规则
红黑树的应用
- 容器集合 HashMap, TreeMap等
- HashMap是 链表 + 红黑树的实现, 当冲突时就需要使用红黑树加快检索
- HashMap中 链表长度太短时使用链表, 太长时使用红黑树, 这个阈值一般设置为8
二三树
- 红黑树是二三树的一个变形,一般用红黑树就够了
[待更新]
B树
- B树在大量的数据库和文件系统场景中都有使用
[待更新]
B+树
[待更新]
总结
- 可以说红黑树是一种不严格的平衡树