非线性数据结构之数

一、基本概念

1. 二叉树的节点与深度

• 节点：二叉树的基本组成单位，每个节点包含一个数据值、一个左子节点和一个右子节点。
• 树的深度（Height）：指树的根节点到叶子节点的最长路径所包含的边数。

2. 二叉树的类型

• 叶节点：没有子节点的节点。
• 内部节点：具有子节点的节点。

---

二、二叉树的种类

1. 完全二叉树（Complete Binary Tree）

定义：完全二叉树的所有层都被完全填满，除了最后一层的节点必须自左向右排列。

特点：

• 通常使用数组实现，具有简洁的内存结构，且方便通过索引访问。
• 节点索引公式：若根节点为第 0 个元素，则节点 i 的左子节点索引为 2i + 1，右子节点为 2i + 2，父节点为 (i-1) / 2。

优缺点：

• 优点：提高了存储和遍历的效率，常用于实现堆。
• 缺点：对树的结构有严格要求，插入和删除操作需要维护完全性。

应用：常见于堆排序、优先队列实现等。

---

2. 满二叉树（Full Binary Tree）

定义：每个节点都有两个子节点，且所有叶节点的深度相同。

特点：

• 所有层都被完全填满，节点数达到最大。
• 满二叉树的节点数 n 与深度 h 满足公式：n = 2^(h+1) - 1。

优缺点：

• 优点：结构紧凑，便于平衡和遍历。
• 缺点：插入和删除操作较为不便，需维持每层的完整性。

应用：常用于存储静态数据，或需要完全对称的数据结构中。

---

3. 二叉搜索树（Binary Search Tree, BST）

定义：BST 是一种特殊的二叉树，满足以下性质：

• 若左子树不为空，则左子树上所有节点的值均小于根节点的值。
• 若右子树不为空，则右子树上所有节点的值均大于根节点的值。
• 左右子树均为二叉搜索树。

特点：

• 支持平均 O(log n) 的插入、删除和查找操作。
• 中序遍历 BST 可获得有序序列。

优缺点：

• 优点：查找和修改操作效率高，适合动态数据集。
• 缺点：在极端情况下（如插入数据有序），树可能会退化为链表，导致性能下降到 O(n)。

应用：用于数据库索引、文件系统、字典等。

示例代码（Java）：

class TreeNode {int value;TreeNode left;TreeNode right;TreeNode(int value) {this.value = value;}
}class BinarySearchTree {TreeNode root;// 插入public void insert(int value) {root = insertRecursive(root, value);}private TreeNode insertRecursive(TreeNode node, int value) {if (node == null) {return new TreeNode(value);}if (value < node.value) {node.left = insertRecursive(node.left, value);} else if (value > node.value) {node.right = insertRecursive(node.right, value);}return node;}// 查找public boolean search(int value) {return searchRecursive(root, value);}private boolean searchRecursive(TreeNode node, int value) {if (node == null) {return false;}if (value == node.value) {return true;} return value < node.value ? searchRecursive(node.left, value) : searchRecursive(node.right, value);}
}

三、平衡树

定义

平衡树是一种保持树结构平衡的二叉树，通常限制了节点的高度差异，使得查找、插入和删除操作保持在 O(log n) 的时间复杂度。

特点：平衡树通常通过旋转操作来调整子树的高度，从而防止极端情况导致的退化。

---

1. AVL 树

定义：AVL 树是一种自平衡二叉搜索树，具有以下性质：

• 每个节点的左右子树高度差最多为 1。

特点：

• 通过“旋转”操作（单旋、双旋）在插入和删除节点后重新平衡树。
• 查找、插入、删除操作复杂度均为 O(log n)。

优缺点：

• 优点：严格平衡，查找效率较高。
• 缺点：旋转操作较多，插入和删除效率较低。

应用：适用于查找频繁、插入删除较少的场景，如数据库索引。

---

2. 红黑树（Red-Black Tree）

定义：红黑树是一种二叉搜索树，具有以下性质：

• 节点为红色或黑色。
• 根节点为黑色。
• 红节点的子节点必须为黑色（红节点不能相邻）。
• 从根节点到叶节点的每条路径都包含相同数目的黑节点。

特点：

• 通过颜色和旋转操作来维持平衡。
• 查找、插入、删除操作平均时间复杂度为 O(log n)。

优缺点：

• 优点：插入和删除效率高，适合频繁修改的数据。
• 缺点：实现复杂。

应用：常见于 Java 的 TreeMap、C++ 的 map，适用于需要快速插入和删除的应用。

---

3. Splay 树

定义：Splay 树是一种自调整二叉搜索树，最近访问的节点将旋转至根节点。这样更常用的元素将接近根节点，减少平均查找时间。

特点：

• 最近使用的数据靠近根节点，提高局部访问效率。
• 每次查找、插入或删除操作都会将目标节点旋转至根节点。

优缺点：

• 优点：适合高频访问的数据。
• 缺点：单次操作复杂度较高，不适合随机访问。

应用：缓存、文件系统等需要频繁访问某些节点的数据结构。

---

4. 比较总结

树种类	平衡方式	优点	缺点	适用场景
AVL 树	左右子树高度差平衡	查找效率高	插入、删除操作复杂	查找频繁，变动少的数据集
红黑树	颜色与旋转	插入、删除效率高	实现复杂	Java 的 TreeMap、Linux VFS
Splay 树	自调整，最近访问至根	适合频繁访问的数据结构	随机访问不高效	缓存、需要局部访问的系统

这些平衡树结构适用于不同的场景，各有优缺点。在实际应用中根据需求选择适合的平衡树可以显著提高数据结构的操作效率。