二叉搜索树和平衡二叉搜索树
1.二叉搜索树
二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，它的每个节点都满足以下条件：
- 左子树的值小于当前节点的值。
- 右子树的值大于当前节点的值。
- 左、右子树也是二叉搜索树。
这些特性使得二叉搜索树在查找、插入和删除操作时具有较高的效率，特别是当树的高度较小时。
1.1 基本操作
查找操作：
- 从根节点开始，若目标值小于当前节点值，则搜索左子树；若目标值大于当前节点值，则搜索右子树。
- 如果找到目标值，则返回节点；如果查找到空节点，则表示没有找到目标值。
插入操作：
- 插入新的值时，从根节点开始，沿着树的路径走，找到合适的位置进行插入。
- 插入的位置遵循左小右大的规则。
删除操作：
删除一个节点可能有三种情况：
- 没有子节点（叶节点）：直接删除该节点。
- 只有一个子节点：删除节点并用其子节点替代。
- 有两个子节点：找到该节点的右子树中最小值（或者左子树中最大值），用该值替代当前节点，并删除替代节点。
遍历：
- 前序遍历（Pre-order）：先访问根节点，再递归访问左子树和右子树。
- 中序遍历（In-order）：先访问左子树，再访问根节点，最后访问右子树。中序遍历二叉搜索树会得到一个升序序列。
- 后序遍历（Post-order）：先递归访问左子树和右子树，最后访问根节点。
1.2 时间复杂度
- 查找、插入和删除操作的平均时间复杂度：O(log n)，其中n是树中的节点数。
- 最坏情况下的时间复杂度：O(n)，当树退化成链表时（即每个节点只有一个子节点），查找、插入和删除的时间复杂度会变为O(n)。
1.3 优化
为了避免树退化成链表，常常会使用自平衡二叉搜索树，如AVL树或红黑树，它们能够确保树的高度始终保持在对数级别，从而保证操作的最坏时间复杂度为O(log n)。
ps: 刷算法题目的时候，如果需要二叉搜索树来解题，直接使用二叉搜索树的话，一般会超时。因为题目给的例子中，一般会让二叉搜索树退化成链表。所以如果我们要使用二叉搜索树的话，至少要会写AVL树（平衡二叉搜索树）。红黑树的实现起来更加复杂，在面试和刷题的过程中，写起来很容易出错。
1.4 示例
假设有如下数字：[7, 3, 9, 2, 5, 8, 10]，按照顺序插入到一个空的二叉搜索树中，树的结构如下：
7
/ \
3 9
/ \ / \
2 5 8 10
在这个树中：
- 根节点是7。
- 3是7的左子节点，9是7的右子节点。
- 左子树继续遵循左小右大的规则，5是3的右子节点，2是3的左子节点。
- 右子树中，8是9的左子节点，10是9的右子节点。
这个二叉搜索树可以支持高效的查找、插入和删除操作，且中序遍历会输出[2, 3, 5, 7, 8, 9, 10]，即升序排列的元素。
2.平衡二叉搜索树
平衡二叉树（Balanced Binary Tree），又叫 AVL 树（Adelson-Velsky and Landis Tree），是一种自平衡的二叉查找树。在这棵树中，每个节点的左右子树的高度差（称为平衡因子）绝对值不超过 1。这样可以保证树的高度始终保持在对数级别，从而确保常见操作（如查找、插入、删除）的时间复杂度是 O(log n)。
2.1 主要特性：
二叉查找树性质：每个节点的左子树的值小于节点的值，右子树的值大于节点的值。
平衡因子：对于每个节点，其左子树的高度与右子树的高度之差，称为平衡因子（Balance Factor, BF）。对于 AVL 树，平衡因子的绝对值不超过 1，公式如下：
[
BF = \text{高度(左子树)} - \text{高度(右子树)}
]
- BF = 0：左右子树高度相等；
- BF = 1：左子树高于右子树；
- BF = -1：右子树高于左子树。
旋转操作：当树的平衡因子不满足要求时，需要进行旋转来恢复平衡。旋转有四种类型：
- 右旋（Right Rotation）：用于处理左子树过高的情况。
- 左旋（Left Rotation）：用于处理右子树过高的情况。
- 左-右旋（Left-Right Rotation）：先对左子树做左旋，再对当前节点做右旋。
- 右-左旋（Right-Left Rotation）：先对右子树做右旋，再对当前节点做左旋。
2.2 操作：
- 查找操作：由于平衡二叉树保持了良好的高度平衡，它的查找操作与普通的二叉查找树相同，时间复杂度为 O(log n)。
- 插入操作：插入新节点时，可能会导致树失去平衡，需要重新调整树的结构。插入完成后，通过旋转操作重新平衡树，时间复杂度为 O(log n)。
- 删除操作：删除节点时，也需要保持树的平衡。删除后，可能会破坏树的平衡，导致需要进行旋转操作来恢复平衡，时间复杂度也是 O(log n)。
2.3 优缺点：
优点：
- 由于平衡性，查询、插入、删除操作的时间复杂度是 O(log n)，能够保证最坏情况下操作的性能。
- 对于动态集合，AVL 树是一种很好的选择，能够确保每次操作都保持对数级别的性能。
缺点：
- 由于插入和删除操作需要通过旋转保持平衡，操作相对较复杂，尤其是在需要多次旋转的情况下。
- 相比于普通的二叉查找树，AVL 树的维护开销较大。
2.4 旋转操作具体讲解
左旋（Left Rotation）：通常用于处理右子树较高的情况（右重）。通过左旋操作，可以将当前节点的右子树提升为根节点，从而使得树更平衡。
右旋（Right Rotation）：通常用于处理左子树较高的情况（左重）。右旋操作将当前节点的左子树提升为根节点，从而使得树更平衡。
左右旋（Left-Right Rotation）：是左旋和右旋的组合，处理的是左子树较高且左子树的右子树较高的情况。
右左旋（Right-Left Rotation）：是右旋和左旋的组合，处理的是右子树较高且右子树的左子树较高的情况。
2.5 旋转的过程与示例：
1. 左旋（Left Rotation）
左旋通常用于右子树较重的情况，即右子树的高度比左子树大。
原始树：
30
\
40
\
50
左旋后的树：
40
/ \
30 50
过程解释：
- 将 40 上升为根节点。
- 将 30 成为 40 的左子节点。
- 将 50 作为 40 的右子节点（不变）。
左旋操作会使得右子树变得不那么高，从而平衡树。
2. 右旋（Right Rotation）
右旋通常用于左子树较重的情况，即左子树的高度比右子树大。
原始树：
30
/
20
/
10
右旋后的树：
20
/ \
10 30
过程解释：
- 将 20 上升为根节点。
- 将 30 成为 20 的右子节点。
- 将 10 作为 20 的左子节点（不变）。
右旋操作使得左子树变得不那么高，从而平衡树。
3. 左右旋（Left-Right Rotation）
左旋和右旋的组合，适用于左子树的右子树比左子树左子树高的情况。
原始树：
30
/
10
\
20
左旋 + 右旋后的树：
20
/ \
10 30
过程解释：
- 首先对 10 进行左旋，将 20 提升为左子树的新根。
- 然后对 30 进行右旋，将 20 提升为根节点。
通过组合旋转，平衡树的结构。
4. 右左旋（Right-Left Rotation）
右旋和左旋的组合，适用于右子树的左子树比右子树右子树高的情况。
原始树：
30
\
50
/
40
右旋 + 左旋后的树：
40
/ \
30 50
过程解释：
- 首先对 50 进行右旋，将 40 提升为右子树的新根。
- 然后对 30 进行左旋，将 40 提升为根节点。
2.5 旋转的意义：
旋转的核心目的是通过调整树的结构来维持树的平衡，避免因某一侧的子树过高导致整个树的高度过大，从而使得树的查找、插入和删除操作的时间复杂度保持在 O(log n)。旋转的过程是局部的，它只调整旋转节点及其子树，而不会影响树的其他部分。
2.6 平衡二叉搜索树的实现
下面是一个 Java 代码示例，展示了如何实现一个平衡二叉树（AVL树）。AVL树是一种自平衡的二叉搜索树，它的特点是每个节点的左右子树高度差不超过1。
class AVLTree {
// 定义树的节点
static class Node {
int value;
Node left, right;
int height; // 存储每个节点高度，不用每次都进行计算
public Node(int value) {
this.value = value;
this.height = 1; // 初始化高度为1
}
}
private Node root;
// 获取节点的高度
private int height(Node node) {
if (node == null) return 0;
return node.height;
}
// 获取节点的平衡因子
private int balanceFactor(Node node) {
if (node == null) return 0;
return height(node.left) - height(node.right);
}
// 更新节点的高度
private void updateHeight(Node node) {
node.height = 1 + Math.max(height(node.left), height(node.right));
}
// 左旋操作
// y(30)
// \
// x(40)
// / \
//T2(35) T3(50)
// x(40)
// / \
// y(30) T3(50)
// \
// T2(35)
private Node leftRotate(Node y) {
Node x = y.right; // x是作为新的根节点
Node T2 = x.left; // 保留跟节点左子树的右子树，防止被覆盖。
// 执行旋转
x.left = y; //
y.right = T2; // 为什么放在y的右子树。因为二叉搜索树x是y的右子树，所以x的所有子树都大于y。
// 更新高度
updateHeight(y);
updateHeight(x);
return x; // 新的根节点
}
// 右旋操作 和左旋的逻辑类似
private Node rightRotate(Node x) {
Node y = x.left;
Node T2 = y.right;
// 执行旋转
y.right = x;
x.left = T2;
// 更新高度
updateHeight(x);
updateHeight(y);
return y; // 新的根节点
}
// 插入节点
public Node insert(Node node, int value) {
if (node == null) return new Node(value);
// 1. 插入节点
if (value < node.value) {
node.left = insert(node.left, value);
} else if (value > node.value) {
node.right = insert(node.right, value);
} else {
return node; // 不允许重复元素
}
// 2. 更新当前节点的高度
updateHeight(node);
// 3. 检查平衡因子，判断是否需要旋转
int balance = balanceFactor(node);
// 左子树比右子树高
if (balance > 1 && value < node.left.value) {
return rightRotate(node); // 左左情况
}
// 右子树比左子树高
if (balance < -1 && value > node.right.value) {
return leftRotate(node); // 右右情况
}
// 左右子树不平衡
if (balance > 1 && value > node.left.value) {
node.left = leftRotate(node.left); // 左右情况
return rightRotate(node);
}
// 右左子树不平衡
if (balance < -1 && value < node.right.value) {
node.right = rightRotate(node.right); // 右左情况
return leftRotate(node);
}
return node;
}
// 插入新的值到树中
public void insert(int value) {
root = insert(root, value);
}
// 中序遍历树
public void inorderTraversal(Node node) {
if (node != null) {
inorderTraversal(node.left);
System.out.print(node.value + " ");
inorderTraversal(node.right);
}
}
// 打印中序遍历结果
public void printTree() {
inorderTraversal(root);
System.out.println();
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
// 插入一些元素
tree.insert(30);
tree.insert(20);
tree.insert(10);
tree.insert(5);
tree.insert(25);
tree.insert(35);
// 打印树的中序遍历
System.out.println("中序遍历结果:");
tree.printTree();
}
}
2.7 代码说明：
- Node 类：表示二叉树的节点，包含值（
value）、左右子节点（left和right）以及该节点的高度（height）。 - AVLTree 类：包含树的根节点和各类操作，包括插入节点、旋转操作（左旋、右旋）和更新节点高度。
- 插入操作：插入节点后，会检查当前树是否失衡，并通过旋转操作来保持平衡。
- 旋转操作：根据平衡因子（左右子树高度差）来决定左旋、右旋，或者先左旋再右旋（左右不平衡）或先右旋再左旋（右左不平衡）。
2.8 运行结果：
该程序通过插入一些节点后，会输出树的中序遍历结果，以确保树保持了平衡。
中序遍历结果:
5 10 20 25 30 35
3.总结：
二叉搜索树的性能能够帮助我们在有序集合中快速查找元素，但是二叉搜索树如果退化的话，就会变成链表。这时候就需要平衡二叉搜索树，平衡二叉搜索树提供了一种高效的方式来保持树的平衡，以确保树的高度始终保持在 O(log n) 的范围内。