查找中常见的树数据结构

news/2024/4/28 9:36:30/文章来源:https://blog.csdn.net/weixin_65032328/article/details/136921278

在动态查找中常见的树相关的数据结构包括：
- 排序二叉树（Binary Search Trees）
- 平衡二叉树（AVL Trees，Balanced binary search trees）
- 红黑树(自平衡二叉树)（Red-Black Trees）
- B树
- B+树
区别：树的高度不同。树的高度越低，性能越高。这是因为每一个节点都是一次I/O。
推荐一个数据结构可视化网站 Data Structure Visualizations，是旧金山大学（USFCA）的一个网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

一、排序二叉树

排序二叉树结构默认的就是左小右大的排序方式，并且采用中序遍历（根节点在中间），得到的就是按照升序排序好的数据。（对应的还有前序遍历、后序遍历）
有这样一个表：
按照二叉树的方式排序的结果是：
如果不给 id 字段添加索引，默认就是全表扫描，假设查询id=10的数据，那至少进行10次磁盘IO。效率低。如果给id字段添加索引，假设该索引使用了二叉树这种数据结构，那么IO的次数就是4次。查询效率显著提高了。
排序二叉树的缺陷
- 这种普通二叉树在数据极端（插入的节点集本身就是有序的，要么从小到大排列，要么由大到小排列）的情况下，效率较低。比如下面的这个二叉树：
- 在这种极端的情况下。该二叉树就像是一个链表。查找效率下降到了O(n)。查询效率极低。

为了避免出现上述一边倒的存储，于是就提出了平衡二叉树。
在平衡二叉树中任何节点的两个子树的高度最大差值为1，所以它也被称为高度平衡树。增加或删除结点可能需要通过一次或多次树旋转来重新平衡这个树。
结点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0、-1的节点被认为是平衡的。带有平衡因子-2或2的节点被认为是不平衡的，并需要重新平衡这个树。
比如，我们存储排序好的数据【3、4、8、12、13、14、16、23】，增加结点如果出现不平衡，则通过节点的左旋或右旋，重新平衡树结构，最终平衡二叉树如下图所示：

① 红黑二叉树（简称：红黑树），它首先是一颗二叉树，同时也是一颗自平衡的排序二叉树。
② 红黑树在原有的排序二叉树增加了如下几个要求：
- 每个结点要么红色，要么黑色。
- 根结点永远是黑色。
- 所有的叶子结点都是空结点（即null），并且是黑色的。
- 每个红色结点的两个子结点都是黑色（从每个叶子结点到根结点的路径上不会有两个连续的红色结点）。
- 从任一结点到其子树中每个叶子结点的路径都包含相同数量的黑色结点。
- 每次新结点在插入时，颜色是红色的。插入后，会根据红黑树的约束条件进行：树的旋转和颜色的调整。
③ 这些约束强化了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。这样就让树大致上是平衡的。
④ 红黑树是一个更高效的检索二叉树，JDK 提供的集合类 TreeMap、TreeSet 本身就是一个红黑树的实现。红黑树的基本操作：插入、删除、左旋、右旋、着色。每插入或者删除一个结点，可能导致树不在符合红黑树的特现，需要进行修复，进行 “左旋、右旋、着色” 操作，使树继续保持红黑树的特性。

B Trees 中的 B 指的是：Balanced（平衡）。
B树首先是一个自平衡的。
B树每个节点下的子节点数量>2。
B树每个节点中也不是存储单个数据，可以存储多个数据。
B树又称为平衡多路查找树。
B树分支的数量不是2，是大于2，具体是多少个分支，由阶决定。例如：
- 3阶的B树，一个节点下最多有3个子节点，每个节点中最多有2个数据。
- 4阶的B树，一个节点下最多有4个子节点，每个节点中最多有3个数据。
- 5阶（5，4）
- …
- 16阶（16，15）【MySQL采用了16阶】
采用B树，B树的高度更低。磁盘IO次数更少。
4阶的B树如下：
在数据库中，每个节点不仅存储了索引值，还存储该索引值对应的数据行。
B树的缺点：
- 不适合做区间查找，对于区间查找效率较低。每次都要从根节点开始。所以在 MySQL 中使用了 B+ Trees 来解决这个问题。