数据结构 树与树结构的扩展

本文最后更新于 2025年9月15日 晚上

指针与结构

通过对链表的研究，我们已经了解了通过指针进行的数据间的结构组织。在链表中，每个节点通过指针与下一个节点建立连接，形成了线性的数据序列。这种简单的指针使用方式让我们初步体验了指针在构建数据结构中的威力。

接下来我们会发现，使用指针可以进行更具控制感的结构设计。与链表的单一方向连接不同，指针的真正潜力在于它能够建立 多维度的关联关系 ：

从线性到非线性的跃升
链表虽然突破了数组的固定大小限制，但仍然局限于线性结构。而通过巧妙地使用多个指针，我们可以构建出具有分支和层次的复杂结构，每个节点不再只能指向一个后继，而是可以同时指向多个不同方向的节点。

灵活的关系建模
在现实世界中，数据之间的关系往往是复杂的、多层次的。例如，一个公司的组织架构、一个家族的血缘关系、或者文件系统的目录结构，都呈现出明显的层级特征。指针为我们提供了直接在内存中模拟这些关系的能力，让数据结构能够真实反映问题域的本质特征。

精确的访问控制
相比于数组的索引访问，指针连接的结构提供了更加精确的导航机制。我们不再需要遍历无关的数据，而是可以沿着预设的路径直达目标，这种”按需访问”的特性为高效算法的设计奠定了基础。

树的结构

通过指针关联的一组具有序列特征和层次特征，除了根节点外每一层的节点都在上层仅有一个父节点与之关联的数据结构被称为树。树结构一般具备两个特征：

  • 每个项都有很多个子节点
  • 除了叫作根的特殊的项，所有其他的项都只有一个父节点

树结构的术语

术语 定义
节点 树中存储的项
根 树的最顶端的节点，只有它没有父节点
子节点 紧邻一个给定的节点下并且直接与给定的节点相连的一个节点。一个节点可以有多个子节点，并且其子节点被视为按照从左到右的顺序排列，最左边的节点称为第一个子节点，最右边的节点称为最后一个子节点
父节点 紧邻一个给定的节点之上并且直接与给定的节点相连的一个节点，一个节点只能有一个父节点
兄弟节点 拥有共同的父节点的子节点
叶子节点 没有子节点的一个节点
内部节点 至少有一个子节点的节点
边/分支/连接 将一个父节点连接到其子节点的线
后代 一个节点的子节点，其子节点的子节点等，一直到叶子节点
祖先 一个节点的父节点，其父节点的父节点等，一直到根节点
路径 连接一个节点与其一个后代节点的边的序列
路径长度 路径中的边的数目
深度或层级 一个节点的深度或层级等于将其连接到根节点的路径的长度，因此根节点的深度或层级是0
高度 树中的叶子节点的最大层级数
子树 将一个节点和其他所有的子节点考虑在内，所形成的一个树

树的优势

回顾树的两个关键特征：

层级关系： 树结构天然构建了父子层级，使得每个父节点都能直接控制和管理其下的子节点。这种层级控制为复杂问题的分层处理提供了结构基础，我们在后续的算法实现中会频繁利用这一特征。

兄弟关系： 同一父节点下的多个子节点形成了天然的分支选择机制，类似于 switch/case 的条件分发模式。通过条件判断可以精确选择访问路径，避免遍历无关分支，实现高效的定向查询。

基于这两个核心特征，树结构能够实现：

问题分解能力： 将复杂问题按层次逐级拆分，每一层处理特定维度的子问题，与递归思想高度契合，支持多步骤的渐进式求解。

查询优化效果： 数据按特征分层存储后，查询时无需遍历全量数据，而是在每层进行少量比较即可确定下探路径，最终以 O(log n) 的效率直达目标。

正是这些特性使得树结构在文件系统、数据库索引、语法解析等需要高效查询和分层管理的场景中得到广泛应用。

树的类型

根据树的结构特点与组织特点，有以下几种树的类型

二叉树

二叉树是一种将节点按照层次结构组织起来的数据结构，每个节点最多只有两个与它直接相关联的子节点。

二叉查找树

二叉查找树在二叉树的基础上增加了有序性约束：对于任意节点，其左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。这种特性使得查找、插入和删除操作的平均时间复杂度为O(log n)，但在极端情况下（如插入有序数据）可能退化为O(n)。

AVL树

AVL树是一种严格的自平衡二叉查找树，要求任何节点的两个子树的高度差不超过1。通过在插入和删除操作后进行旋转调整来维持平衡，保证了所有操作的时间复杂度始终为O(log n)。虽然查询性能稳定，但频繁的平衡调整使得插入和删除操作开销较大。

B树

B树是一种多路平衡查找树，每个节点可以包含多个键值和多个子节点。B树的设计目的是减少磁盘I/O操作次数，特别适合数据库和文件系统等需要大量磁盘访问的场景。通过增加节点的容量，B树能够降低树的高度，从而减少查找时需要访问的节点数量。

B+树

B+树是B树的变种，具有以下关键特征：所有的实际数据都存储在叶子节点中，非叶子节点只存储索引信息；叶子节点之间通过指针连接形成有序链表。这种设计使得B+树特别适合范围查询和顺序访问，同时保持了良好的随机访问性能。MySQL等数据库系统广泛采用B+树作为索引结构。

红黑树

红黑树是一种近似平衡的二叉查找树，通过给节点着色（红色或黑色）并遵循特定的颜色规则来维持平衡。相比AVL树，红黑树的平衡条件较为宽松，在保证O(log n)性能的同时，插入和删除时需要的旋转操作更少，因此在需要频繁修改的场景中表现更好。这也是为什么Java的TreeMap和C++的map选择红黑树作为底层实现的原因。

树的实现

开始之前

在开始讨论树结构之前，我们要注意与之前的数组或者hash表结构可以直观的感受数据的组织和排布过程不同，树的结构实现是比链表更加复杂的递归引用结构。我们需要通过树节点的定义和方法设计上来理解树中元素的增加，遍历，查询过程。

二叉树

满二叉树

叶子节点都在最底层

除了叶子节点外，其他节点都有左右子节点

完全二叉树

除了最后一层，其他层的节点数都要达到最大

最后一层，第一个子节点到最后一个子节点之间不能有空的子节点

最后一层如果有奇数个节点的话，最后一个节点必须是左子节点

前序遍历

前序遍历

前序遍历的特点是：

先访问根节点

再访问左子树

再访问右子树

以循环实现为例：

将遍历流程分为两个部分

先准备栈结构和数组，再按顺序将结构按顺序压入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static ArrayList<Integer> preOrder(TreeNode<Integer> root){
		ArrayList<Integer> res = new ArrayList<>();
		if(root == null) return res ;
		Stack<TreeNode<Integer>> stack = new Stack<>();
		stack.push(root);
	
		while (!stack.isEmpty()){
				TreeNode<Integer> curr = stack.pop();
				res.add(curr.data);
				if(curr.right!= null) stack.push(curr.right);
				if(curr.left != null) stack.push(curr.left);
		}
		return res ;
}

中序遍历

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static ArrayList<Integer> midOrder(TreeNode<Integer> root){
		ArrayList<Integer> res = new ArrayList<>();
		if(root == null) return res ;
		Stack<TreeNode<Integer>> stack = new Stack<>();
		TreeNode<Integer> curr = root ;
		while (curr != null || ! stack.isEmpty()){
				while(curr != null){
						stack.push(curr);
						curr = curr.left;
				}
				TreeNode<Integer> node = stack.pop();
				res.add(node.data);
				curr = node.right ;
		}
		return res; 
}

public static List<Integer> midOrderR(TreeNode<Integer> root){
		List<Integer> res = new ArrayList<>();
		midOrder(root, res);
		return res ;
}

private static void midOrder(TreeNode<Integer> node, List<Integer> res){
		if(node == null) return ;
		midOrder(node.left , res );
		res.add(node.data);
		midOrder(node.right , res) ;
}

后序遍历

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public static List<Integer> postOrder(TreeNode<Integer> root){
		LinkedList<Integer> res = new LinkedList<>();
		if(root == null) return res ;
		Stack<TreeNode<Integer>> stack = new Stack<>();
		stack.push(root);
	
		while (!stack.isEmpty()){
				TreeNode<Integer> curr = stack.pop();
				res.addFirst(curr.data);
				if(curr.left != null) stack.push(curr.left);
				if(curr.right != null) stack.push(curr.right);
		}
		return res ;
}

public static List<Integer> postOrderR(TreeNode<Integer> root){
		List<Integer> res = new ArrayList<>();
		postOrder(root,  res );
		return res ;
}

private static void postOrder(TreeNode<Integer> node , List<Integer> res ){
		if(node == null) return ;
		postOrder(node.left , res);
		postOrder(node.right, res);
		res.add(node.data);
}

public static List<Integer> postOrder(TreeNode<Integer> root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
  
    Stack<TreeNode<Integer>> stack1 = new Stack<>();
    Stack<TreeNode<Integer>> stack2 = new Stack<>();
  
    stack1.push(root);
  
    while (!stack1.isEmpty()) {
        TreeNode<Integer> node = stack1.pop();
        stack2.push(node); 
      
        if (node.left != null) stack1.push(node.left);
        if (node.right != null) stack1.push(node.right);
    }
  
    while (!stack2.isEmpty()) {
        res.add(stack2.pop().data);
    }
  
    return res;
}

层序遍历

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static List<Integer> levelOrder(TreeNode<Integer> root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;

    Queue<TreeNode<Integer>> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode<Integer> node = queue.poll(); // 出队
        res.add(node.data);                   // 访问节点

        if (node.left != null) queue.offer(node.left);   // 左子树入队
        if (node.right != null) queue.offer(node.right); // 右子树入队
    }

    return res;
}

二叉查找树

二叉查找树

二叉查找树通过在 添加过程中定义添加规则，将TreeNode根据与根节点的大小排布在根节点两侧，二叉查找树要求树结构满足以下规则：

左子树的所有节点值小于这个节点值

右子树的所有节点值大于这个节点值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
public class BST<E extends Comparable<E>>{
		private class TreeNode{
				E data;
				TreeNode left ;
				TreeNode right ;
				public TreeNode(E data){
				this.data = data;
				}
		}
		private TreeNode root ;
		private int size ;
		public BST(){
				this.root = null;
				this.size = 0 ;
		}
	
		public int getSize(){
				return size ;
		}
	
		public boolean isEmpty(){
				return size == 0 ;
		}
	
		public void add(E e){
				if(root == null){
						root = new TreeNode(e);
						size++;
						return ;
				}else {
						TreeNode curr = root ;
						while(curr != null){
								if(e.compareTo(curr.data) == 0){
										return ;
								} else if(e.compareTo(curr.data) < 0 && curr.left ==null){
										curr.left = new TreeNode(e);
										size++ ;
										return ;
								} else if(e.compareTo(curr.data) > 0 && curr.right ==null){
										curr.right = new TreeNode(e);
										size++ ;
										return ;									
								}
								if(e.compareTo(curr.data)<0){
										curr = curr.left;
								}else {
										curr = curr.right ;
								}
						} 
				}
		}
		public boolean contains(E target){
				if(root == null) return false ;
				TreeNode curr = root ;
				while(curr != null){
						if(target.compareTo(curr.data) == 0){
								return true;
						} else if(target.compareTo(curr.data) < 0) {
								curr = curr.left;
						} else{
								curr = curr.right;
						}
				}
				return false ;	
		}
	
		public void set(E src ,E target ){
				if(contains(target)) return ;
				TreeNode srcNode = find(src);
		    if(srcNode != null) {       
		        srcNode.data = target;
		    }
		}
	
		public E minValue(){
				if(root == null){
						throw new RuntimeException("tree is null");
				}
				TreeNode min = root ;
				while(min.left != null){
						min = min.left ;
				}
				return min.data;
		}
		public E maxValue(){
				if(root == null){
						throw new RuntimeException("tree is null");
				}
				TreeNode max = root ;
				while(max.right != null){
						max = max.right;
				}
				return max.data;
		}
		public E removeMin(){
				if(root == null){
						throw new RuntimeException("tree is null");
				}
				TreeNode min = root ;
				TreeNode parent = null ;
				while (min.left != null) {
						parent = min ;
						min = min.left;			
				}
				if(parent == null){
						root = root.right;
				} else {
						parent.left = min.right;
						min.right = null ;
				}
				size-- ;
				return min.data;
		}
		public E removeMax(){
				if(root == null){
						throw new RuntimeException("tree is null");
				}
				TreeNode max = root ;
				TreeNode parent = null;
				while(max.right != null){
						parent = max ;
						max = max.right;
				}
				if(parent == null){
						root = root.left;
				}else {
						parent.right = max.left;
						max.left = null;
				}
				size -- ;
				return max.data;		
		}
	
		public E remove(E e){
		    if(root == null) return null;  
		  
		    TreeNode curr = root;
		    TreeNode parent = null;
		  
		    // 查找要删除的节点
		    while(curr != null && e.compareTo(curr.data) != 0){
		        parent = curr; 
		        if(e.compareTo(curr.data) < 0) {
		            curr = curr.left;
		        } else {
		            curr = curr.right;
		        }
		    }
		  
		    if(curr == null) return null; 
		  
		    E removedData = curr.data;
		  
		    // 情况1：叶子节点
		    if(curr.left == null && curr.right == null){
		        if(parent == null){ 
		            root = null;
		        } else if(parent.left == curr){
		            parent.left = null;
		        } else {
		            parent.right = null;
		        }
		    }
		    // 情况2：只有右子树
		    else if(curr.left == null){
		        if(parent == null){
		            root = curr.right;
		        } else if(parent.left == curr){
		            parent.left = curr.right;
		        } else {
		            parent.right = curr.right;
		        }
		    }
		    // 情况3：只有左子树
		    else if(curr.right == null){
		        if(parent == null){
		            root = curr.left;
		        } else if(parent.left == curr){
		            parent.left = curr.left;
		        } else {
		            parent.right = curr.left;
		        }
		    }
		    // 情况4：有两个子树
		    else {
		        // 找到右子树的最小节点
		        TreeNode minParent = curr;
		        TreeNode min = curr.right;
		        while(min.left != null){
		            minParent = min;
		            min = min.left;
		        }
		      
		        // 用最小节点的值替换当前节点
		        curr.data = min.data;
		      
		        // 删除最小节点
		        if(minParent == curr){
		            curr.right = min.right;
		        } else {
		            minParent.left = min.right;
		        }
		    }  
		    size--;
		    return removedData;  
		}

		public TreeNode find(E target){
				if(root == null) return null;
				TreeNode curr = root ;
				while(curr != null){
						if( target.compareTo(curr.data) == 0){
								return curr;
						} else if( target.compareTo(curr.data)< 0) {
								curr = curr.left ;						
						} else {
								curr = curr.right ;				
						}
				}
				return null;	
		}
}

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
private TreeNode add(TreeNode node, E e){
		if(node == null){
				size++ ;
				return new TreeNode(e);
		}	
		if(e.compareTo(node.data) < 0){
				node.left = add(node.left, e);
		} else {
			  node.right = add(node.right, e);
		}
		return node ;
}

public List<E> preOrder(){
		List<E> res = new ArrayList<>();
		preOrder(root,res);
		return res ;
}
private void preOrder(TreeNode node, List<E> res){
		if(node == null){
				return;
		}
		res.add(node.data);
		preOrder(node.left, res);
		preOrder(node.right, res);
}
public List<E> inOrder(){
		List<E> res = new ArrayList<>();
		inOrder(root,res);
		return res;
}

public void inOrder(TreeNode node, List<E> res){
		if(node == null){
				return ;
		}
		inOrder(node.left, res);
		res.add(node.data);
		inOrder(node.right, res);
}

private TreeNode find(TreeNode node, E e){
		if(node == null) return null;
		if(e.compareTo(node.data) == 0){
				return node;
		} else if(e.compareTo(node.data)<0){
				return find(node.left , e);
		} else {
				return find(node.right, e);
		}
}

public E minValue(){
		if(root == null){
				throw new RuntimeException("tree is null");
		}
		TreeNode min = root ;
		min = minValue(min);
		return min.data;
}
private TreeNode minValue(TreeNode node){
		if(node.left == null){
				return node;
		}
		return minValue(node.left);
}

public E maxValue(){
		if(root == null){
				throw new RuntimeException("tree is null");
		}
		TreeNode max = root ;
		max = maxValue(max);
		return max.data;
}
public TreeNode maxValue(TreeNode node){
		if(node.right == null){
				return node;
		}
		return maxValue(node.right);
}
public E removeMin(){
		E res = minValue();
		root = removeMin(root);
		return res;
}

private TreeNode removeMin(TreeNode node){
		if(node.left == null){
				TreeNode rightNode = node.right;
				node.right = null;
				size-- ;
				return rightNode;
		}
		TreeNode leftRoot = removeMin(node.left);
		node.left = leftRoot;
		return node ;
}
public E removeMax(){
		E res = maxValue();
		root = removeMax(root);
		return res ;
}
private TreeNode removeMax(TreeNode node){
		if(node.right == null){
				TreeNode leftNode = node.left;
				node.left = null;
				size -- ;
				return leftNode;	
		}
		TreeNode rightRoot = removeMax(node.right);
		node.right = rightRoot ;
		return node;
}

public void remove(E e){
		root = remove(root,e);
}
private TreeNode remove(TreeNode node, E e){
		if(node == null) return null;
		if(e.compareTo(node.data) < 0){
				node.left = remove(node.left, e);
				return node;
		}else if(e.compareTo(node.data) > 0){
				node.right = remove(node.right,e);
				return node;
		}else {
				if (node.left == null){
						TreeNode rightNode = node.right;
						node.right = null;
						size-- ;
						return rightNode;
				}
				if (node.right == null){
						TreeNode leftNode = node.left ;
						node.left = null ;
						size-- ;
						return leftNode;
				}
				TreeNode successor = minValue(node.right);
				successor.left = node.left;
				successor.right = removeMin(node.right);
				node.left = null;
				node.right = null;
				return successor ;
		}
}

平衡二叉树与AVL树

在仅使用二叉查找树进行数据存储时，在某些特殊情形下，二叉查找树会退化为链表。

平衡二叉树的实现优化了这一问题。

平衡二叉树通过高度和影响因子来处理二叉查找树中的平衡问题，在平衡二叉树中，左右子树的高度差不超过1。

原理是在节点插入/删除 后，计算节点当前的高度（左右子树的最大值+1），之后检查影响因子（左右子树差），当影响因子绝对值大于1时，触发左旋或右旋操作。调整整颗树的平衡性

左旋过程

右旋过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
public class AVLTree<E extends Comparable<E>>{
		private class TreeNode{
				E data;
				TreeNode left ;
				TreeNode right ;
				int height = 1;
			
				public TreeNode(E data) {this.data = data ;}
		}
		private TreeNode root ;
		private int size ;
	
		public AVLTree(){
				this.root = null;
				this.size = 0;
		}
		public int getSize() { return size;} 
		public boolean isEmpty() { return size == 0;}
	
		private int getHeight(TreeNode node){
				if(node == null) return 0;
				return node.height ;
		}	
		public List<E> preOrder(){
				List<E> res = new ArrayList<>();
				preOrder(root,res);
				return res ;
		}
		private void preOrder(TreeNode node, List<E> res){
				if(node == null){
						return;
				}
				res.add(node.data);
				preOrder(node.left, res);
				preOrder(node.right, res);
		}
		public List<E> inOrder(){
				List<E> res = new ArrayList<>();
				inOrder(root,res);
				return res;
		}
	
		public void inOrder(TreeNode node, List<E> res){
				if(node == null){
						return ;
				}
				inOrder(node.left, res);
				res.add(node.data);
				inOrder(node.right, res);
		}
		public void add(E e){
				root = add(root,e);
		}
	
		private TreeNode find(TreeNode node, E e){
				if(node == null) return null;
				if(e.compareTo(node.data) == 0){
						return node;
				} else if(e.compareTo(node.data)<0){
						return find(node.left , e);
				} else {
						return find(node.right, e);
				}
		}
	
		public E minValue(){
				if(root == null){
						throw new RuntimeException("tree is null");
				}
				TreeNode min = root ;
				min = minValue(min);
				return min.data;
		}
		private TreeNode minValue(TreeNode node){
				if(node.left == null){
						return node;
				}
				return minValue(node.left);
		}
	
		public E maxValue(){
				if(root == null){
						throw new RuntimeException("tree is null");
				}
				TreeNode max = root ;
				max = maxValue(max);
				return max.data;
		}
		public TreeNode maxValue(TreeNode node){
				if(node.right == null){
						return node;
				}
				return maxValue(node.right);
		}
		private TreeNode add(TreeNode node, E e){
				if(node == null){
						size++ ;
						return new TreeNode(e);
				}	
				if(e.compareTo(node.data) < 0) {
						node.left = add(node.left,e);			
				} else {
						node.right = add(node.right,e);
				}
				node.height = Math.max(getHeight(node.left),getHeight(node.right))+1;
				int balanceFactor = getBalanceFactor(node);
				if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0){
						return  rightRotate(node);
				}
				if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0){
						return  leftRotate(node);
				}
				if(balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
						TreeNode z = leftRotate(node.left);
						node.left =  z;
						return rightRotate(node);
				}
				if(balanceFactor < 0 && getBalanceFactor(node.right) > 0){
						TreeNode z = rightRotate(node.right);
						node.right = z;
						return leftRotate(node);					
				}		
				return node ;
		}
	
		public boolean isBST(){
				List<E> res = inOrder();
				int len = res.size();
				if (len <= 1){
						return true ;
				}
				for(int i = 1; i< len ; i++){
						if(res.get(i).compareTo(res.get(i-1)) < 0){
								return false ;
						}
				}
				return true ;
		}
	
		public boolean isBalanced(){
				return isBalanced(root); 
		}
		private boolean isBalanced(TreeNode node){
				if(node == null) return true;
				int balanceFactor = getBalanceFactor(node) ;
				if(Math.abs(balanceFactor) > 1) return false;
				return isBalanced(node.left) && isBalanced(node.right);
		}
	
		private int getBalanceFactor(TreeNode node){
				if(node == null) return 0;
				return getHeight(node.left) - getHeight(node.right);
		}
	
		private TreeNode rightRotate(TreeNode y){
				TreeNode x = y.left;
				TreeNode t3 = x.right;
				x.right = y;
				y.left = t3;
			
				x.height = Math.max(getHeight(x.left),getHeight(x.right)+1);
				y.height = Math.max(getHeight(y.left),getHeight(y.right)+1);
				return x;
		}
	
		private TreeNode leftRotate(TreeNode y){
				TreeNode x = y.right;
				TreeNode t3 = x.left;
			
				x.left = y;
				y.right = t3;
			
				x.height = Math.max(getHeight(x.left),getHeight(x.right))+1;
				y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
				return x;
		}
		public void remove(E e){root = remove(root,e);}
		private TreeNode remove(TreeNode node, E e){
				if(node == null) return null;
				TreeNode retNode;
				if(e.compareTo(node.data) < 0){
						node.left = remove(node.left, e);
						retNode = node;
				}else if(e.compareTo(node.data) > 0){
						node.right = remove(node.right, e);
						retNode = node;
				} else {
						if(node.left == null){
								TreeNode rightNode = node.right;
								node.right = null;
								size -- ;
								retNode = rightNode;
						} else if (node.right == null){
								TreeNode leftNode = node.left;
								node.left = null;
								size--;
								retNode = leftNode;
						} else {
								TreeNode successor = minValue(node.right);
							
								successor.right = remove(node.right,successor.data);
								successor.left = node.left;
							
								node.left = null;
								node.right = null;
								size -- ;
								retNode = successor;
						}
			  }
			  
				retNode.height = Math.max(getHeight(retNode.left),getHeight(retNode.right))+1;
				int balanceFactor = getBalanceFactor(retNode);
				if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0){
						return  rightRotate(retNode);
				}
				if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0){
						return  leftRotate(retNode);
				}
				if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
						TreeNode z = leftRotate(retNode.left);
						node.left =  z;
						return rightRotate(retNode);
				}
				if(balanceFactor < 0 && getBalanceFactor(retNode.right) > 0){
						TreeNode z = rightRotate(retNode.right);
						retNode.right = z;
						return leftRotate(retNode);					
				}		
				return retNode ;
		}
		}
		public E removeMin(){
				E res = minValue();
				root = remove(root,res);
				return res;
		}
		public E removeMax(){
				E res = maxValue();
				root = remove(root, res);
				return res ;
		}
}

2-3树，B树与B+树

AVL树解决了二叉查找树会退化为链表的问题，但是随着值的插入，会频繁发生子树的旋转影响整体查询性能。

2-3树

2-3树

2-3树是一种多路查找树，是B树的一种特例（m=3）。

它提供了稳定的层高，同时提供了优秀的查找性能，2-3树通过聚合和分裂的方式，保证叶子节点层的层深一致，同时因为层深一致，且父节点是由叶子节点由中间分裂得来的，所以2-3树是一颗绝对平衡的树。

B树与B+树

B树与B+树 是由单一父节点延申出更多路径一种多路查找树，在数据库实现的内容中具体讨论了其数据的组织过程。

红黑树

红黑树具有以下要求

  1. 每个节点是红色或者是黑色的
  2. 根节点是黑色的
  3. 每个叶子节点是黑色的
  4. 如果一个节点是红色的，那么他的孩子节点都是黑色的
  5. 从任意一个节点到叶子节点，经过的黑色节点数量都一样

通过这些要求，保证了红黑树的平衡性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class RBTree<E extends Comparable<E>>{
		private static final boolean RED = true;
		private static final boolean BLACK = false;
		private class TreeNode{
				E data;
				TreeNode left ;
				TreeNode right ;
				boolean color ;
				public TreeNode(E data){
					this.data = data;
					this.color = RED;
				}
		}
		private TreeNode root;
		private int size ;
		public RBTree(){
				this.root = null;
				this.size = 0;
		}
		public int getSize(){return size;}
		public boolean isEmpty() { return size == 0;}
	
		private boolean isRED(TreeNode node){
				if(node == null){
						return BLACK; 
				}
				return node.color == RED; 
		}
		private TreeNode leftRotate(TreeNode node){
				TreeNode x = node.right ;
				node.right = x.left;
				x.left = node;
				x.color = node.color;
				node.color = RED;
				return x; 
		}
		private TreeNode rightRotate(TreeNode node){
				TreeNode x = node.left ;
				node.left = x.right;
				x.right = node;
				x.color = node.color ;
				node.color = RED;
			
				return x;
		}
	
		private void flipColors(TreeNode node){
				node.color = RED;
				node.left.color = BLACK;
				node.right.color = BLACK;
	
		}
	
		public void add(E e){
				root = add(root,e);
				root.color = BLACK;
		}
	
		private TreeNode add(TreeNode node, E e){
				if(node == null){
						size++ ;
						return new TreeNode(e);
				}	
				if(e.compareTo(node.data) < 0) {
						node.left = add(node.left,e);			
				} else {
						node.right = add(node.right,e);
				}
				if(isRED(node.right) && !isRED(node.left)){
						node = leftRotate(node);
				}
				if(isRED(node.left) && node.left != null && isRED(node.left.left)){
						node = rightRotate(node);
				}
				if(isRED(node.left) && isRED(node.right)){
						flipColors(node);
				}
				return node;
		}
}

树结构总结

核心特性对比

树类型 时间复杂度 空间复杂度 平衡性 实现复杂度 主要特点
二叉查找树 平均O(log n)，最坏O(n) O(n) 不保证 简单 查找、插入、删除操作简单
AVL树 O(log n) O(n) 严格平衡 中等 查找性能稳定，但插入删除开销大
红黑树 O(log n) O(n) 近似平衡 复杂 平衡插入删除开销，综合性能好
B树 O(log n) O(n) 自平衡 复杂 减少磁盘I/O，适合外存
B+树 O(log n) O(n) 自平衡 复杂 叶子节点链接，支持范围查询

应用场景选择指南

内存存储场景

1. 普通二叉查找树

  • 适用场景： 数据相对随机分布，对性能要求不是特别严格
  • 典型应用： 教学演示、简单的查找应用
  • 选择理由： 实现简单，代码可读性好

2. AVL树

  • 适用场景： 查找操作频繁，插入删除操作较少
  • 典型应用： 静态数据的快速查询、字典实现
  • 选择理由： 严格平衡保证了稳定的查找性能

3. 红黑树

  • 适用场景： 增删改查操作都比较频繁，需要综合性能
  • 典型应用： Java的TreeMap/TreeSet、C++的map/set、Linux内核
  • 选择理由： 在保证O(log n)的同时，插入删除的平衡调整开销较小

外存存储场景

4. B树

  • 适用场景： 数据量大，需要持久化存储，随机访问为主
  • 典型应用： 数据库索引、文件系统
  • 选择理由： 减少磁盘I/O次数，充分利用磁盘块大小

5. B+树

  • 适用场景： 需要范围查询，顺序访问频繁
  • 典型应用： MySQL的InnoDB引擎、PostgreSQL索引
  • 选择理由： 叶子节点的链式结构支持高效的范围扫描

决策框架

在选择树结构时，建议按以下顺序考虑：

1. 存储方式决策

1
2
3
4
存储在内存？
├── 是 → 考虑二叉树系列（BST、AVL、红黑树）
└── 否 → 考虑多路树系列（B树、B+树）

2. 操作模式决策

1
2
3
4
5
6
7
8
9
10
内存存储的情况下：
├── 查找为主，很少修改 → AVL树
├── 增删改查都频繁 → 红黑树
└── 简单应用，性能要求不高 → 二叉查找树

外存存储的情况下：
├── 主要是点查询 → B树
├── 需要范围查询 → B+树
└── 混合场景 → B+树（更通用）

3. 性能要求决策

1
2
3
4
5
6
对性能要求：
├── 极致查找性能 → AVL树
├── 平衡的增删改查性能 → 红黑树
├── 减少I/O次数 → B树/B+树
└── 实现简单为主 → 二叉查找树

数据结构
#数据结构
数据结构 树与树结构的扩展
http://gadoid.io/2025/09/15/数据结构-树与树结构的扩展/
作者
Codfish
发布于
2025年9月15日
许可协议