当前位置：首页 > news >正文

非线性数据结构之数

news 2025/7/4 4:50:57

一、基本概念

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 树	自调整，最近访问至根	适合频繁访问的数据结构	随机访问不高效	缓存、需要局部访问的系统