1. 简介
在数据结构中,树是一种层次结构的数据结构,由节点(node)组成,其中每个节点通过边(edge)与其他节点连接。树是一种非线性的数据结构,广泛用于表示具有层级关系的数据。常见的树包括二叉树、平衡树、红黑树、B树等。
1.1 基本概念
-
节点(Node):树中的基本元素,包含数据和指向子节点的指针(或引用)。
-
边(Edge):连接树中两个节点的连接线。
-
根节点(Root):树的顶层节点,没有父节点。
-
子节点(Child Node):某个节点的下级节点。
-
父节点(Parent Node):某个节点的上级节点。
-
叶节点(Leaf Node):没有子节点的节点。
-
深度(Depth):树中某个节点到根节点的路径长度。
-
高度(Height):树中某个节点到其最深叶节点的最长路径长度。
-
子树(Subtree):树的某个节点及其所有后代节点构成的树。
1.2 常见树类型
-
二叉树(Binary Tree):每个节点最多有两个子节点,通常称为“左子节点”和“右子节点”。
-
二叉搜索树(Binary Search Tree, BST):一种特定的二叉树,满足以下性质:对于树中的每个节点,左子树的所有节点值小于节点的值,右子树的所有节点值大于节点的值。
-
平衡树(Balanced Tree):是一种二叉搜索树,要求任何节点的左右子树高度差的绝对值不超过某个阈值(如AVL树和红黑树)。
-
堆(Heap):一种完全二叉树,满足堆的性质(如最大堆和最小堆)。
-
B树(B-tree):一种自平衡的树数据结构,广泛应用于数据库和文件系统中。
1.3 树的常见操作
-
插入操作:在二叉树或二叉搜索树中插入新节点。二叉树的插入操作较为简单,通常通过递归方式将节点插入到空子树中。二叉搜索树的插入需要遵循二叉搜索树的特性,将新节点放入合适的位置。
-
删除操作:删除节点时需要处理三个情况:1)节点是叶子节点,直接删除;2)节点有一个子节点,用该子节点替代;3)节点有两个子节点,通常使用右子树的最小节点或左子树的最大节点替代。
-
查找操作:在二叉搜索树中,查找操作通过与节点的值进行比较,从根节点开始向左或向右子树递归查找,直到找到目标节点。
-
遍历操作:树的遍历可以分为深度优先遍历(前序、中序、后序遍历)和广度优先遍历(层次遍历)。遍历操作通常用于访问树中的所有节点。
-
前序遍历(Pre-order):根节点 -> 左子树 -> 右子树
-
中序遍历(In-order):左子树 -> 根节点 -> 右子树
-
后序遍历(Post-order):左子树 -> 右子树 -> 根节点
-
层次遍历(Level-order):逐层从上到下访问每一层节点
-
2. 树的分类
2.1 二叉树(Binary Tree)
二叉树是每个节点最多有两个子节点的树结构。二叉树广泛应用于数据存储和表示中。
-
性质:
-
每个节点至多有两个子节点,通常称之为左子节点和右子节点。
-
在二叉树中,节点的排列可以使得某些算法(如查找、插入和删除)非常高效。
-
-
应用:
-
表达式树:用于表示数学表达式,叶节点是操作数,非叶节点是运算符。
-
Huffman编码树:用于压缩数据时,基于频率构造的树。
-
定义节点和二叉树的基本操作
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
left = right = null;
}
}
public class BinaryTree {
TreeNode root;
public BinaryTree() {
root = null;
}
// 插入操作 (递归插入)
public void insert(int val) {
root = insertRec(root, val);
}
private TreeNode insertRec(TreeNode root, int val) {
if (root == null) {
root = new TreeNode(val);
return root;
}
if (val < root.val) {
root.left = insertRec(root.left, val);
} else if (val > root.val) {
root.right = insertRec(root.right, val);
}
return root;
}
// 查找操作
public boolean search(int val) {
return searchRec(root, val);
}
private boolean searchRec(TreeNode root, int val) {
if (root == null) {
return false;
}
if (root.val == val) {
return true;
} else if (val < root.val) {
return searchRec(root.left, val);
} else {
return searchRec(root.right, val);
}
}
// 中序遍历
public void inorderTraversal() {
inorderRec(root);
}
private void inorderRec(TreeNode root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.val + " ");
inorderRec(root.right);
}
}
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
bt.insert(10);
bt.insert(5);
bt.insert(15);
bt.inorderTraversal(); // 输出: 5 10 15
}
}
2.2 二叉搜索树(Binary Search Tree, BST)
二叉搜索树是一种特殊的二叉树,满足以下性质:
-
对于每个节点,左子树的所有节点值小于当前节点的值,右子树的所有节点值大于当前节点的值。
-
操作:
-
插入:从根节点开始,递归地将新节点插入到左子树或右子树。
-
查找:从根节点开始,比较当前节点的值与目标值,根据大小关系选择左子树或右子树进行查找。
-
删除:删除节点时,需要考虑节点的子节点情况,常用的策略是用右子树最小的节点替代被删除的节点。
-
-
应用:
-
高效的查找、插入和删除操作。
-
数据库中实现索引。
-
插入和查找操作
class BSTNode {
int val;
BSTNode left, right;
BSTNode(int val) {
this.val = val;
left = right = null;
}
}
public class BinarySearchTree {
BSTNode root;
public BinarySearchTree() {
root = null;
}
// 插入操作 (递归)
public void insert(int val) {
root = insertRec(root, val);
}
private BSTNode insertRec(BSTNode root, int val) {
if (root == null) {
root = new BSTNode(val);
return root;
}
if (val < root.val) {
root.left = insertRec(root.left, val);
} else {
root.right = insertRec(root.right, val);
}
return root;
}
// 查找操作
public boolean search(int val) {
return searchRec(root, val);
}
private boolean searchRec(BSTNode root, int val) {
if (root == null) {
return false;
}
if (root.val == val) {
return true;
} else if (val < root.val) {
return searchRec(root.left, val);
} else {
return searchRec(root.right, val);
}
}
// 中序遍历
public void inorderTraversal() {
inorderRec(root);
}
private void inorderRec(BSTNode root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.val + " ");
inorderRec(root.right);
}
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.inorderTraversal(); // 输出: 5 10 15
}
}
2.3 平衡树(Balanced Tree)
平衡树是一类二叉搜索树,它的高度是有限制的,保证树的高度与节点数量呈对数关系。常见的平衡树包括AVL树和红黑树。
-
性质:对于每个节点,其左右子树的高度差不超过1(AVL树)或对每个节点施加颜色和高度限制(红黑树)。
-
应用:由于平衡树的高度较小,它能够提供高效的查找、插入和删除操作。
A是平衡树,B不是。
2.4 红黑树(Red-Black Tree)
红黑树是一种自平衡的二叉查找树,具有如下性质:
-
每个节点是红色或黑色。
-
根节点是黑色。
-
每个红色节点的两个子节点都是黑色。
-
从任意节点到其所有叶子节点的路径上,必须有相同数量的黑色节点。
-
操作:
-
插入:插入新节点后,通过旋转和调整节点颜色来恢复红黑树的平衡。
-
删除:删除节点后,可能需要通过旋转和调整来维持树的平衡。
-
-
应用:
-
Java中的
TreeMap
和TreeSet
,C++的std::map
和std::set
。
-
一个简化的红黑树(平衡树)插入和平衡算法
enum Color { RED, BLACK }
class RBTreeNode {
int val;
Color color;
RBTreeNode left, right, parent;
RBTreeNode(int val) {
this.val = val;
this.color = Color.RED;
left = right = parent = null;
}
}
public class RedBlackTree {
private RBTreeNode root;
private RBTreeNode TNULL;
public RedBlackTree() {
TNULL = new RBTreeNode(0);
TNULL.color = Color.BLACK;
root = TNULL;
}
// 左旋转
private void leftRotate(RBTreeNode x) {
RBTreeNode y = x.right;
x.right = y.left;
if (y.left != TNULL) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
// 右旋转
private void rightRotate(RBTreeNode x) {
RBTreeNode y = x.left;
x.left = y.right;
if (y.right != TNULL) {
y.right.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
root = y;
} else if (x == x.parent.right) {
x.parent.right = y;
} else {
x.parent.left = y;
}
y.right = x;
x.parent = y;
}
// 插入修正
private void fixInsert(RBTreeNode k) {
RBTreeNode u;
while (k.parent.color == Color.RED) {
if (k.parent == k.parent.parent.right) {
u = k.parent.parent.left;
if (u.color == Color.RED) {
u.color = Color.BLACK;
k.parent.color = Color.BLACK;
k.parent.parent.color = Color.RED;
k = k.parent.parent;
} else {
if (k == k.parent.left) {
k = k.parent;
rightRotate(k);
}
k.parent.color = Color.BLACK;
k.parent.parent.color = Color.RED;
leftRotate(k.parent.parent);
}
} else {
u = k.parent.parent.right;
if (u.color == Color.RED) {
u.color = Color.BLACK;
k.parent.color = Color.BLACK;
k.parent.parent.color = Color.RED;
k = k.parent.parent;
} else {
if (k == k.parent.right) {
k = k.parent;
leftRotate(k);
}
k.parent.color = Color.BLACK;
k.parent.parent.color = Color.RED;
rightRotate(k.parent.parent);
}
}
if (k == root) {
break;
}
}
root.color = Color.BLACK;
}
// 插入节点
public void insert(int key) {
RBTreeNode node = new RBTreeNode(key);
RBTreeNode y = null;
RBTreeNode x = root;
while (x != TNULL) {
y = x;
if (node.val < x.val) {
x = x.left;
} else {
x = x.right;
}
}
node.parent = y;
if (y == null) {
root = node;
} else if (node.val < y.val) {
y.left = node;
} else {
y.right = node;
}
node.left = TNULL;
node.right = TNULL;
node.color = Color.RED;
fixInsert(node);
}
// 查找操作
public boolean search(int key) {
return searchTreeHelper(root, key) != TNULL;
}
private RBTreeNode searchTreeHelper(RBTreeNode node, int key) {
if (node == TNULL || key == node.val) {
return node;
}
if (key < node.val) {
return searchTreeHelper(node.left, key);
}
return searchTreeHelper(node.right, key);
}
public static void main(String[] args) {
RedBlackTree rbt = new RedBlackTree();
rbt.insert(10);
rbt.insert(20);
rbt.insert(30);
System.out.println(rbt.search(20)); // 输出: true
System.out.println(rbt.search(40)); // 输出: false
}
}
2.5 B树(B- Tree)
B树是一种多叉自平衡树,广泛应用于数据库和文件系统中。
-
性质:
-
节点可以有多个子节点,并且每个节点包含多个键值。
-
B树的所有叶子节点都在同一层,查找操作的效率与树的高度成对数关系。
-
-
操作:
-
查找:从根节点开始,根据键值顺序逐层查找。
-
插入:在合适的位置插入新节点,若节点已满,则进行分裂。
-
删除:删除节点时需要保持树的平衡。
-
-
应用:
-
数据库的索引结构,文件系统中的目录管理。
-
简单操作
import java.util.*;
class BTreeNode {
List<Integer> keys;
List<BTreeNode> children;
boolean isLeaf;
public BTreeNode(boolean isLeaf) {
this.isLeaf = isLeaf;
keys = new ArrayList<>();
children = new ArrayList<>();
}
}
public class BTree {
private BTreeNode root;
private int t; // 阶数
public BTree(int t) {
this.t = t;
root = new BTreeNode(true);
}
// 插入操作
public void insert(int key) {
if (root.keys.size() == 2 * t - 1) {
BTreeNode s = new BTreeNode(false);
s.children.add(root);
split(s, 0);
root = s;
}
insertNonFull(root, key);
}
private void insertNonFull(BTreeNode node, int key) {
int i = node.keys.size() - 1;
if (node.isLeaf) {
node.keys.add(0);
while (i >= 0 && key < node.keys.get(i)) {
node.keys.set(i + 1, node.keys.get(i));
i--;
}
node.keys.set(i + 1, key);
} else {
while (i >= 0 && key < node.keys.get(i)) {
i--;
}
i++;
BTreeNode child = node.children.get(i);
if (child.keys.size() == 2 * t - 1) {
split(node, i);
if (key > node.keys.get(i)) {
i++;
}
}
insertNonFull(node.children.get(i), key);
}
}
private void split(BTreeNode parent, int i) {
BTreeNode fullChild = parent.children.get(i);
BTreeNode newChild = new BTreeNode(fullChild.isLeaf);
parent.children.add(i + 1, newChild);
parent.keys.add(i, fullChild.keys.get(t - 1));
for (int j = t; j < fullChild.keys.size(); j++) {
newChild.keys.add(fullChild.keys.get(j));
}
fullChild.keys = fullChild.keys.subList(0, t - 1);
if (!fullChild.isLeaf) {
for (int j = t; j < fullChild.children.size(); j++) {
newChild.children.add(fullChild.children.get(j));
}
fullChild.children = fullChild.children.subList(0, t);
}
}
public static void main(String[] args) {
BTree btree = new BTree(3);
btree.insert(10);
btree.insert(20);
btree.insert(5);
btree.insert(6);
btree.insert(12);
}
}
2.6 B+树(B+ Tree)
B+树是B树的一个变种,所有数据值都保存在叶子节点中,非叶子节点仅作为索引。
-
性质:
-
叶子节点通过链表连接,可以进行高效的范围查询。
-
非叶子节点仅用于索引,不保存实际数据。
-
-
操作:
-
查找:与B树相似,查找过程中只关注索引。
-
范围查询:由于叶子节点通过链表连接,范围查询非常高效。
-
-
应用:
-
数据库索引,尤其是在关系型数据库中的主键索引。
-
3. 并查集(Union-Find)
并查集是一种用于处理集合合并和查询问题的数据结构。它支持两种主要操作:
-
查找(Find):确定某个元素属于哪个集合。
-
合并(Union):将两个集合合并成一个集合。
树的实现:
-
并查集通常使用树来表示集合,每个集合对应一棵树,根节点表示集合的代表元素。
-
路径压缩(Path Compression):在查找操作中,将沿途的节点直接连接到根节点,从而加速后续的查找操作。
-
按秩合并(Union by Rank):合并操作时,始终将较小的树合并到较大的树下,保持树的深度较小。
应用场景:
-
图论:判断图中两个节点是否连通,求解最小生成树(Kruskal算法)。
-
社交网络:检测社交网络中的用户是否属于同一群体。
-
动态连通性问题:实时查询和更新网络中各个节点之间的连接关系。
4. 差异
-
二叉树最适合简单应用,但如果不平衡,效率较低。
-
二叉搜索树在插入和查找操作上较为高效,但在最坏情况下可能退化为链表。
-
AVL树和红黑树提供平衡结构,保证了操作的对数时间复杂度,非常适合对性能要求较高的应用。
-
B树和B+树多用于磁盘存储中,尤其适用于范围查询和数据库索引,因为它们是多路平衡树,能够处理更大规模的数据。B+树在数据库中应用广泛,特别适合做范围查询。