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)); // 输出: trueSystem.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+树在数据库中应用广泛，特别适合做范围查询。