Java与算法之(13) - 二叉搜索树

查找是指在一批记录中找出满足指定条件的某一记录的过程，例如在数组{ 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 }中查找数字15，实现代码很简单：

1. int key = 15;
2. int[] datas = new int[] { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
3. for(int i = 0; i < datas.length; i++) {
4. if(datas[i] == key) {
5. System.out.println("找到了, 共查找" + (i + 1) + "次");
6. break;
7. }
8. }

但是查找效率并不稳定，如果查找8，只需要比较一次，查找15则需要比较15次。如果数组扩大到1亿个数，而查找的数字恰好排在最后，查找则变得非常低效。

更好的查找方式是使用二叉搜索树，首先用数组构建二叉树，如下图：

二叉树的相关基础知识可参考：Java与算法之(7) - 完全二叉树

注意上面这棵二叉树的特点，每个左子节点的值都比父节点小，每个右子节点的值都比父节点大。满足这个条件的二叉树称为二叉搜索树（Binary Search Tree），也叫二叉排序树（Binary Sorting Tree）。

根据这个特性，可以得出查找的规律。以查找15为例，从根节点8开始比较，因15>8，（如果存在）则一定在8的右子树内；与右子树12比较，因15>12，（如果存在）则一定在12的右子树内；与14比较。。。与15比较，找到目标。

如果查找5，则依次比较8、4、6、5。

在这棵树中，查找任何一个数字，最多需要比较4次（约log2(15)）。介绍查找方法之前，先看如何构建这棵树。

1 插入节点

用数据描述这棵树，首选需要描述节点。用一个类来表示，每个节点包括本身的值及左右两个子节点的指针。

1. private static class Node {
2. Node leftChild;
3. Node rightChild;
4. int data;
5. public Node(int data) {
6. this.data = data;
7. }
8. }

树由节点组成，一个一个节点加进去，树叶逐渐变得枝繁叶茂。构建树的过程可以分解成不断重复的插入节点行为。

第一个加入的节点做为根节点，以后加入节点的操作和前面所述的查询过程一样，从根开始比较，如果小于则和左子节点比较，如果大于则和右子节点比较，不断重复这个过程直到到达叶子节点。比叶子节点小则做为叶子节点的左子节点，大则做为右子节点。

构建过程如下：

这个过程的逻辑是一直向下寻找，直到没有子节点为止。整个过程适合用递归的方式，主要代码如下：

1. public void add(int key) {
2. if(root == null) {
3. root = new Node(key);
4. return;
5. }
6. addNode(root, new Node(key));
7. }
8. private void addNode(Node parent, Node child) {
9. if(child.data == parent.data) {
10. return;
11. }
12. if(child.data < parent.data) {
13. if(parent.leftChild != null) {
14. addNode(parent.leftChild, child);
15. } else {
16. parent.leftChild = child;
17. }
18. } else {
19. if(parent.rightChild != null) {
20. addNode(parent.rightChild, child);
21. } else {
22. parent.rightChild = child;
23. }
24. }
25. }

2 查找节点

查找一个节点和插入一个节点的流程很相似，但是结果相反。插入节点是一直向下寻找，找到则插入失败，找不到则做为叶子节点加入树中。查找节点是一直向下寻找，找到则成功返回，找不到则查找失败。

代码如下：

1. public void search(int key) {
2. this.steps = 0;
3. Node node = searchNode(root, key);
4. if(node == null) {
5. System.out.println("共查找" + this.steps + "次, 未找到" + key);
6. } else {
7. System.out.println("共查找" + this.steps + "次, 搜索到" + key);
8. }
9. }
10. private Node searchNode(Node from, int key) {
11. this.steps++;
12. if(from == null || key == from.data) {
13. return from;
14. } else if(key > from.data) {
15. return searchNode(from.rightChild, key);
16. } else {
17. return searchNode(from.leftChild, key);
18. }
19. }

3 删除节点

在二叉搜索树中删除一个节点后，需要调整二叉树的结构，使其仍然保持二叉搜索树的特点。以被删除节点拥有子节点的情况，分三种情况考虑。见下图：

• 15节点左右子节点都没有，删除时直接把父节点14的右子节点设置为null即可
• 2节点没有右子节点，删除时需要把左子树连接回树中，即把4的左子节点指向1；6节点没有左子节点，删除时需要把右子树连接回书中，即把4的右子节点指向7
• 8节点同时拥有左右子节点，删除规则是先找到右子节点即12，然后递归12节点的左子节点，直到叶子节点，这张图中将找到9。设置8节点的值为9，并删除9节点。

按这个规则推导其他数字删除的步骤：

删除4，先找到6，6没有左子节点，查找结束，将4节点的值设置为6，按规则2删除6节点。

删除12，先找到14，递归左子节点找到13，设置12节点的值为13，删除13。

二叉搜索数完整代码如下：

1. public class BinarySearchTree {
2. private Node root;
3. private int steps;
4. /**
5. * 插入节点
6. * @param key
7. */
8. public void add(int key) {
9. if(root == null) {
10. root = new Node(key);
11. return;
12. }
13. addNode(root, new Node(key));
14. }
15. private void addNode(Node parent, Node child) {
16. if(child.data == parent.data) {
17. return;
18. }
19. if(child.data < parent.data) {
20. if(parent.leftChild != null) {
21. addNode(parent.leftChild, child);
22. } else {
23. parent.leftChild = child;
24. }
25. } else {
26. if(parent.rightChild != null) {
27. addNode(parent.rightChild, child);
28. } else {
29. parent.rightChild = child;
30. }
31. }
32. }
33. /**
34. * 查找节点
35. * @param key
36. */
37. public void search(int key) {
38. this.steps = 0;
39. Node node = searchNode(root, key);
40. if(node == null) {
41. System.out.println("共查找" + this.steps + "次, 未找到" + key);
42. } else {
43. System.out.println("共查找" + this.steps + "次, 搜索到" + key);
44. }
45. }
46. private Node searchNode(Node from, int key) {
47. this.steps++;
48. if(from == null || key == from.data) {
49. return from;
50. } else if(key > from.data) {
51. return searchNode(from.rightChild, key);
52. } else {
53. return searchNode(from.leftChild, key);
54. }
55. }
56. /**
57. * 删除节点
58. * @param key
59. */
60. public void delete(int key) {
61. Node child = root;
62. Node parent = child;
63. boolean isLeftChild = true;
64. while(child != null) {
65. if(child.data == key) {
66. deleteNode(parent, child, isLeftChild);
67. child = null;
68. } else if(key < child.data) {
69. isLeftChild = true;
70. parent = child;
71. child = child.leftChild;
72. } else {
73. isLeftChild = false;
74. parent = child;
75. child = child.rightChild;
76. }
77. }
78. }
79. private void deleteNode(Node parent, Node child, boolean isLeftChild) {
80. if(child.leftChild == null && child.rightChild == null) {
81. if(isLeftChild) {
82. parent.leftChild = null;
83. } else {
84. parent.rightChild = null;
85. }
86. } else if(child.leftChild == null) {
87. if(isLeftChild) {
88. parent.leftChild = child.rightChild;
89. } else {
90. parent.rightChild = child.rightChild;
91. }
92. } else if(child.rightChild == null) {
93. if(isLeftChild) {
94. parent.leftChild = child.leftChild;
95. } else {
96. parent.rightChild = child.leftChild;
97. }
98. } else {
99. Node leaf = child.rightChild;
100. parent = child;
101. while(leaf.leftChild != null) {
102. parent = leaf;
103. leaf = leaf.leftChild;
104. }
105. child.data = leaf.data;
106. if(parent != child)
107. parent.leftChild = leaf.leftChild;
108. else
109. parent.rightChild = leaf.rightChild;
110. }
111. }
112. /**
113. * 中序遍历二叉搜索树, 结果是从小到大排列的
114. * @param node
115. */
116. public void inOrder(Node node) {
117. if(node == null) {
118. return;
119. }
120. inOrder(node.leftChild);
121. System.out.print(node.data + " ");
122. inOrder(node.rightChild);
123. }
124. private static class Node {
125. Node leftChild;
126. Node rightChild;
127. int data;
128. public Node(int data) {
129. this.data = data;
130. }
131. }
132. public static void main(String[] args) {
133. int[] datas = new int[] { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
134. BinarySearchTree bsTree = new BinarySearchTree();
135. for(int i = 0; i < datas.length; i++) {
136. bsTree.add(datas[i]);
137. }
138. System.out.print("中序遍历");
139. bsTree.inOrder(bsTree.root);
140. System.out.println();
141. bsTree.search(8);
142. bsTree.search(12);
143. bsTree.search(15);
144. System.out.println("删除节点8");
145. bsTree.delete(8);
146. System.out.print("中序遍历");
147. bsTree.inOrder(bsTree.root);
148. System.out.println();
149. bsTree.search(8);
150. }
151. }

运行结果：

1. 中序遍历1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2. 共查找1次, 搜索到8
3. 共查找2次, 搜索到12
4. 共查找4次, 搜索到15
5. 删除节点8
6. 中序遍历1 2 3 4 5 6 7 9 10 11 12 13 14 15
7. 共查找5次, 未找到8

本例中的二叉树结构是一种理想情况，如果对数组{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}使用上面的方法构建二叉搜索树，动手画一下就可以发现最终得到的仍然是一个链表，查找15需要比较15次。

这棵树根的左右严重失衡，左侧一个子节点都没有，而右侧的深度为15。为了保证查找的效率，需要对这棵树做优化，让整棵树保持一定的平衡，这就是下一篇的主角：平衡二叉搜索树。