【面经】查找中常见的树数据结构

---

• 在动态查找中常见的树相关的数据结构包括：
  • 二叉排序（搜索、查找）树（BST，Binary Search Tree），左小右大原则。
  • 平衡二叉树（AVL Tree，Balanced Binary Search Tree），平衡因子不大于1.
  • 红黑树（红黑二叉树）（Red-Black Tree），大致平衡，最长路径长度不大于最短路径长度的两倍。
  • B树（平衡多路查找树），允许一个结点有多个子结点并且每个结点可以存储多个key和data。
  • B+树，所有的data都存储在叶子结点并且使用指针将叶子结点链接起来，便于区间查找。
• 区别：树的高度不同。树的高度越低，性能越高。这是因为每查找一个节点都是一次I/O。
• 推荐一个数据结构可视化网站 Data Structure Visualizations，是旧金山大学（USFCA）的一个网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

---

一、二叉排序（搜索、查找）树（BST，Binary Search Tree）

• 二叉排序树结构默认的就是左小右大的排序原则。
• 二叉排序树性质：非空左子树的所有键值小于其根结点的键值；非空右子树的所有键值大于其根结点的键值；左右子树都是二叉搜索树。
• 有这样一个表：
  
• 按照二叉排序树的方式排序的结果是：
  
• 对于二叉排序树进行中序遍历，即可得到从小到大的有序序列。它利用了二分的思想，可以快速查找到关键码，查找效率为O(logn)。

（1）二叉排序树的查找、插入和删除过程

• 查找：
  • 从根节点开始，如果要查找的关键码大于当前关键码，则下一个查找的结点为根节点的右子树，反之则是左子树。 再以新节点为根，重复以上的查找步骤，直到查到得到匹配的关键码为止。
• 插入：
  • 基于查找操作进行查找合适的位置进行插入。 该合适的位置指的是按照查找步骤进行到的叶子节点处，若欲插入的关键码大于该叶子结点，则插入为右孩子，反之为左孩子。 插入的结点必须是叶子结点。 若开始树空，则直接成为根节点；若欲插入的关键码已存在，则插入失败。 二叉树的构造过程也是不断插入的过程。
• 删除：
  • 同样是基于查找操作，首先查找到欲删除的结点。此时，删除结点通常包括三种情况
    • ①若删除的结点是叶子结点，则可以直接将结点删去；（0个）
    • ②若删除的结点只有左孩子或者右孩子，则用它的孩子代替它；（1个）
    • ③若删除的结点有左右孩子，则可以寻找其中序遍历的直接前驱（左子树最右边的叶子结点）或者直接后继（右子树最左边的叶子结点）代替它，再删去该直接前驱或直接后继。（2个）

（2）叉树排序树的缺陷

• 这种普通二叉排序树在数据极端（插入的节点集本身就是有序或有一定的顺序的，要么从小到大排列，要么由大到小排列）的情况下，效率较低。比如下面的这个二叉树：
  
• 在这种极端的情况下。该二叉树就像是一个链表。查找效率下降到了O(n)。查询效率极低。

（3）二叉排序树的改进

• 插入时要保证二叉树的平衡因子的绝对值不大于1，于是产生了平衡二叉树（AVL树）。
• 可以参考的博客

---

二、平衡二叉树（AVL Tree，Balanced binary search tree）

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

（1）平衡二叉树的缺陷

• 如果插入操作比查询操作多， AVL 就要花费大量开销做旋转来调整节点以保证树的平衡。

（2）平衡二叉树的改进

• 为了减少旋转开销，引入了红黑树。
• 平衡二叉(AVL)树中的 LL旋转、RR旋转、LR旋转、RL旋转 的详细解释

---

三、红黑树（自平衡二叉树）（Red-Black Trees）

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

---

四、B树（平衡多路查找树）

• B Tree 中的 B 指的是：Balanced（平衡），B树首先是一个自平衡的。
• B树相比于前面的各种二叉树，B树允许每个结点可以有更多的子结点并且每个结点中可以存储多个key值。
  
• 采用B树，B树的高度更低。磁盘IO次数更少。

（1）B Tree的缺点

• 不适合做区间查找，对于区间查找效率较低。每次都要从根节点开始。所以在 MySQL 中使用了 B+ Trees 来解决这个问题。

---

五、B+树

• B+树将数据都存储在叶子节点中。并且叶子节点之间使用指针连接，这样很适合范围查询。
• B+树的非叶子节点上只有索引值，没有数据，所以非叶子节点可以存储更多的索引值，这样让B+树更矮胖，提高检索效率。
  
• 一文彻底搞懂MySQL基础：B树和B+树的区别

---

六、B树和B+树的区别

1. 单个结点只存储key值，不存储数据，所有的数据都存储在叶子结点中，能够存储更多的元素，减少磁盘的IO次数，所以B+树更加适合作为MySQL数据库的底层数据结构。
2. B+树的叶子结点相互之间有一个链路，形成了一个有序的链表，便于区间查找。

---