二叉查找树,又叫二叉排序树,二叉搜索树,是一种有特定规则的二叉树,定义如下:

  1. 它是一棵二叉树,或者是空树。
  2. 左子树所有节点的值都小于它的根节点,右子树所有节点的值都大于它的根节点。
  3. 左右子树也是一棵二叉查找树。

二叉查找树 - 图1

二叉查找树的特点是,一直往左儿子往下找左儿子,可以找到最小的元素,一直往右儿子找右儿子,可以找到最大的元素。

看起来,我们可以用它来实现元素排序,可是我们却使用了二叉堆来实现了堆排序,因为二叉查找树不保证是一个平衡的二叉树,最坏情况下二叉查找树会退化成一个链表,也就是所有节点都没有左子树或者没有右子树,树的层次太深导致排序性能太差。

使用二分查找,可以很快在一棵二叉查找树中找到我们需要的值。

我们来分析二叉查找树添加,删除,查找元素的方法。

一、添加元素

以下是一个二叉查找树的表示:

  1. // 二叉查找树
  2. type BinarySearchTree struct {
  3. Root *BinarySearchTreeNode // 树根节点
  4. }
  5. // 二叉查找树节点
  6. type BinarySearchTreeNode struct {
  7. Value int64 // 值
  8. Times int64 // 值出现的次数
  9. Left *BinarySearchTreeNode // 左子树
  10. Right *BinarySearchTreeNode // 右字树
  11. }
  12. // 初始化一个二叉查找树
  13. func NewBinarySearchTree() *BinarySearchTree {
  14. return new(BinarySearchTree)
  15. }

一个节点代表一个元素,节点的 Value 值是用来进行二叉查找的关键,当 Value 值重复时,我们将值出现的次数 Times 加 1。添加元素代码如下:

  1. // 添加元素
  2. func (tree *BinarySearchTree) Add(value int64) {
  3. // 如果没有树根,证明是棵空树,添加树根后返回
  4. if tree.Root == nil {
  5. tree.Root = &BinarySearchTreeNode{Value: value}
  6. return
  7. }
  8. // 将值添加进去
  9. tree.Root.Add(value)
  10. }
  11. func (node *BinarySearchTreeNode) Add(value int64) {
  12. if value < node.Value {
  13. // 如果插入的值比节点的值小,那么要插入到该节点的左子树中
  14. // 如果左子树为空,直接添加
  15. if node.Left == nil {
  16. node.Left = &BinarySearchTreeNode{Value: value}
  17. } else {
  18. // 否则递归
  19. node.Left.Add(value)
  20. }
  21. } else if value > node.Value {
  22. // 如果插入的值比节点的值大,那么要插入到该节点的右子树中
  23. // 如果右子树为空,直接添加
  24. if node.Right == nil {
  25. node.Right = &BinarySearchTreeNode{Value: value}
  26. } else {
  27. // 否则递归
  28. node.Right.Add(value)
  29. }
  30. } else {
  31. // 值相同,不需要添加,值出现的次数加1即可
  32. node.Times = node.Times + 1
  33. }
  34. }

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

复制代码

如果添加元素时是棵空树,那么初始化根节点。

然后添加的值和根节点比较,判断是要插入到根节点左子树还是右子树,还是不用插入。

当值比根节点小时,元素要插入到根节点的左子树中,当值比根节点大时,元素要插入到根节点的右子树中,相等时不插入,只更新次数。

然后再分别对根节点的左子树和右子树进行递归操作即可。

#二、查找最大值或最小值的元素

查找最大值和最小值比较简单,一直往左儿子往下找左儿子,可以找到最小的元素,一直往右儿子找右儿子,可以找到最大的元素。

  1. // 找出最小值的节点
  2. func (tree *BinarySearchTree) FindMinValue() *BinarySearchTreeNode {
  3. if tree.Root == nil {
  4. // 如果是空树,返回空
  5. return nil
  6. }
  7. return tree.Root.FindMinValue()
  8. }
  9. func (node *BinarySearchTreeNode) FindMinValue() *BinarySearchTreeNode {
  10. // 左子树为空,表面已经是最左的节点了,该值就是最小值
  11. if node.Left == nil {
  12. return node
  13. }
  14. // 一直左子树递归
  15. return node.Left.FindMinValue()
  16. }
  17. // 找出最大值的节点
  18. func (tree *BinarySearchTree) FindMaxValue() *BinarySearchTreeNode {
  19. if tree.Root == nil {
  20. // 如果是空树,返回空
  21. return nil
  22. }
  23. return tree.Root.FindMaxValue()
  24. }
  25. func (node *BinarySearchTreeNode) FindMaxValue() *BinarySearchTreeNode {
  26. // 右子树为空,表面已经是最右的节点了,该值就是最大值
  27. if node.Right == nil {
  28. return node
  29. }
  30. // 一直右子树递归
  31. return node.Right.FindMaxValue()
  32. }

三、查找指定元素

二分查找的技巧也在这里有用武之地了:

  1. // 查找节点
  2. func (tree *BinarySearchTree) Find(value int64) *BinarySearchTreeNode {
  3. if tree.Root == nil {
  4. // 如果是空树,返回空
  5. return nil
  6. }
  7. return tree.Root.Find(value)
  8. }
  9. func (node *BinarySearchTreeNode) Find(value int64) *BinarySearchTreeNode {
  10. if value == node.Value {
  11. // 如果该节点刚刚等于该值,那么返回该节点
  12. return node
  13. } else if value < node.Value {
  14. // 如果查找的值小于节点值,从节点的左子树开始找
  15. if node.Left == nil {
  16. // 左子树为空,表示找不到该值了,返回nil
  17. return nil
  18. }
  19. return node.Left.Find(value)
  20. } else {
  21. // 如果查找的值大于节点值,从节点的右子树开始找
  22. if node.Right == nil {
  23. // 右子树为空,表示找不到该值了,返回nil
  24. return nil
  25. }
  26. return node.Right.Find(value)
  27. }
  28. }

如果是空树,返回 nil,否则与根节点比较。

如果刚刚好等于根节点的值,返回该节点,否则根据值的比较,继续往左子树或右字树递归查找。

四、查找指定元素的父亲

与查找指定元素一样,只不过追踪的是该元素的父亲节点。

  1. // 查找指定节点的父亲
  2. func (tree *BinarySearchTree) FindParent(value int64) *BinarySearchTreeNode {
  3. if tree.Root == nil {
  4. // 如果是空树,返回空
  5. return nil
  6. }
  7. // 如果根节点等于该值,根节点其没有父节点,返回nil
  8. if tree.Root.Value == value {
  9. return nil
  10. }
  11. return tree.Root.FindParent(value)
  12. }
  13. func (node *BinarySearchTreeNode) FindParent(value int64) *BinarySearchTreeNode {
  14. // 外层没有值相等的判定,因为在内层已经判定完毕后返回父亲节点。
  15. if value < node.Value {
  16. // 如果查找的值小于节点值,从节点的左子树开始找
  17. leftTree := node.Left
  18. if leftTree == nil {
  19. // 左子树为空,表示找不到该值了,返回nil
  20. return nil
  21. }
  22. // 左子树的根节点的值刚好等于该值,那么父亲就是现在的node,返回
  23. if leftTree.Value == value {
  24. return node
  25. } else {
  26. return leftTree.FindParent(value)
  27. }
  28. } else {
  29. // 如果查找的值大于节点值,从节点的右子树开始找
  30. rightTree := node.Right
  31. if rightTree == nil {
  32. // 右子树为空,表示找不到该值了,返回nil
  33. return nil
  34. }
  35. // 右子树的根节点的值刚好等于该值,那么父亲就是现在的node,返回
  36. if rightTree.Value == value {
  37. return node
  38. } else {
  39. return rightTree.FindParent(value)
  40. }
  41. }
  42. }

代码相应的进行了调整,方便获取到父亲节点。

如果返回的父亲节点为空,表示没有父亲。

五、删除元素

删除元素有四种情况:

  1. 第一种情况,删除的是根节点,且根节点没有儿子,直接删除即可。
  2. 第二种情况,删除的节点有父亲节点,但没有子树,也就是删除的是叶子节点,直接删除即可。
  3. 第三种情况,删除的节点下有两个子树,因为右子树的值都比左子树大,那么用右子树中的最小元素来替换删除的节点,这时二叉查找树的性质又满足了。右子树的最小元素,只要一直往右子树的左边一直找一直找就可以找到。
  4. 第四种情况,删除的节点只有一个子树,那么该子树直接替换被删除的节点即可。

代码实现如下:

  1. // 删除指定的元素
  2. func (tree *BinarySearchTree) Delete(value int64) {
  3. if tree.Root == nil {
  4. // 如果是空树,直接返回
  5. return
  6. }
  7. // 查找该值是否存在
  8. node := tree.Root.Find(value)
  9. if node == nil {
  10. // 不存在该值,直接返回
  11. return
  12. }
  13. // 查找该值的父亲节点
  14. parent := tree.Root.FindParent(value)
  15. // 第一种情况,删除的是根节点,且根节点没有儿子
  16. if parent == nil && node.Left == nil && node.Right == nil {
  17. // 置空后直接返回
  18. tree.Root = nil
  19. return
  20. } else if node.Left == nil && node.Right == nil {
  21. // 第二种情况,删除的节点有父亲节点,但没有子树
  22. // 如果删除的是节点是父亲的左儿子,直接将该值删除即可
  23. if parent.Left != nil && value == parent.Left.Value {
  24. parent.Left = nil
  25. } else {
  26. // 删除的原来是父亲的右儿子,直接将该值删除即可
  27. parent.Right = nil
  28. }
  29. return
  30. } else if node.Left != nil && node.Right != nil {
  31. // 第三种情况,删除的节点下有两个子树,因为右子树的值都比左子树大,那么用右子树中的最小元素来替换删除的节点。
  32. // 右子树的最小元素,只要一直往右子树的左边一直找一直找就可以找到,替换后二叉查找树的性质又满足了。
  33. // 找右子树中最小的值,一直往右子树的左边找
  34. minNode := node.Right
  35. for minNode.Left != nil {
  36. minNode = minNode.Left
  37. }
  38. // 把最小的节点删掉
  39. tree.Delete(minNode.Value)
  40. // 最小值的节点替换被删除节点
  41. node.Value = minNode.Value
  42. node.Times = minNode.Times
  43. } else {
  44. // 第四种情况,只有一个子树,那么该子树直接替换被删除的节点即可
  45. // 父亲为空,表示删除的是根节点,替换树根
  46. if parent == nil {
  47. if node.Left != nil {
  48. tree.Root = node.Left
  49. } else {
  50. tree.Root = node.Right
  51. }
  52. return
  53. }
  54. // 左子树不为空
  55. if node.Left != nil {
  56. // 如果删除的是节点是父亲的左儿子,让删除的节点的左子树接班
  57. if parent.Left != nil && value == parent.Left.Value {
  58. parent.Left = node.Left
  59. } else {
  60. parent.Right = node.Left
  61. }
  62. } else {
  63. // 如果删除的是节点是父亲的左儿子,让删除的节点的右子树接班
  64. if parent.Left != nil && value == parent.Left.Value {
  65. parent.Left = node.Right
  66. } else {
  67. parent.Right = node.Right
  68. }
  69. }
  70. }
  71. }

首先查找到要删除元素的节点:tree.Root.Find(value),然后找到该节点父亲:tree.Root.FindParent(value),根据四种不同情况对删除节点进行补位。核心在于,第三种情况下,删除的节点有两个子树情况下,需要用右子树中最小的节点来替换被删除节点。

上面的代码可以优化,可以在查找删除元素的节点时顺道查出其父亲节点,不必要分开查询父亲节点,在第三种情况下查出右子树的最小节点时可以直接将其移除,不必递归使用 tree.Delete(minNode.Value)

由于这种通用形式的二叉查找树实现甚少使用,大部分程序都使用了AVL树或红黑树,以上优化理解即可。

六、中序遍历(实现排序)

使用二叉查找树可以实现排序,只需要对树进行中序遍历即可。

我们先打印出左子树,然后打印根节点的值,再打印右子树,这是一个递归的过程。

  1. // 中序遍历
  2. func (tree *BinarySearchTree) MidOrder() {
  3. tree.Root.MidOrder()
  4. }
  5. func (node *BinarySearchTreeNode) MidOrder() {
  6. if node == nil {
  7. return
  8. }
  9. // 先打印左子树
  10. node.Left.MidOrder()
  11. // 按照次数打印根节点
  12. for i := 0; i <= int(node.Times); i++ {
  13. fmt.Println(node.Value)
  14. }
  15. // 打印右子树
  16. node.Right.MidOrder()
  17. }

七、完整代码

  1. package main
  2. import (
  3. "fmt"
  4. )
  5. // 二叉查找树节点
  6. type BinarySearchTree struct {
  7. Root *BinarySearchTreeNode // 树根节点
  8. }
  9. // 二叉查找树节点
  10. type BinarySearchTreeNode struct {
  11. Value int64 // 值
  12. Times int64 // 值出现的次数
  13. Left *BinarySearchTreeNode // 左子树
  14. Right *BinarySearchTreeNode // 右字树
  15. }
  16. // 初始化一个二叉查找树
  17. func NewBinarySearchTree() *BinarySearchTree {
  18. return new(BinarySearchTree)
  19. }
  20. // 添加元素
  21. func (tree *BinarySearchTree) Add(value int64) {
  22. // 如果没有树根,证明是棵空树,添加树根后返回
  23. if tree.Root == nil {
  24. tree.Root = &BinarySearchTreeNode{Value: value}
  25. return
  26. }
  27. // 将值添加进去
  28. tree.Root.Add(value)
  29. }
  30. func (node *BinarySearchTreeNode) Add(value int64) {
  31. if value < node.Value {
  32. // 如果插入的值比节点的值小,那么要插入到该节点的左子树中
  33. // 如果左子树为空,直接添加
  34. if node.Left == nil {
  35. node.Left = &BinarySearchTreeNode{Value: value}
  36. } else {
  37. // 否则递归
  38. node.Left.Add(value)
  39. }
  40. } else if value > node.Value {
  41. // 如果插入的值比节点的值大,那么要插入到该节点的右子树中
  42. // 如果右子树为空,直接添加
  43. if node.Right == nil {
  44. node.Right = &BinarySearchTreeNode{Value: value}
  45. } else {
  46. // 否则递归
  47. node.Right.Add(value)
  48. }
  49. } else {
  50. // 值相同,不需要添加,值出现的次数加1即可
  51. node.Times = node.Times + 1
  52. }
  53. }
  54. // 找出最小值的节点
  55. func (tree *BinarySearchTree) FindMinValue() *BinarySearchTreeNode {
  56. if tree.Root == nil {
  57. // 如果是空树,返回空
  58. return nil
  59. }
  60. return tree.Root.FindMinValue()
  61. }
  62. func (node *BinarySearchTreeNode) FindMinValue() *BinarySearchTreeNode {
  63. // 左子树为空,表面已经是最左的节点了,该值就是最小值
  64. if node.Left == nil {
  65. return node
  66. }
  67. // 一直左子树递归
  68. return node.Left.FindMinValue()
  69. }
  70. // 找出最大值的节点
  71. func (tree *BinarySearchTree) FindMaxValue() *BinarySearchTreeNode {
  72. if tree.Root == nil {
  73. // 如果是空树,返回空
  74. return nil
  75. }
  76. return tree.Root.FindMaxValue()
  77. }
  78. func (node *BinarySearchTreeNode) FindMaxValue() *BinarySearchTreeNode {
  79. // 右子树为空,表面已经是最右的节点了,该值就是最大值
  80. if node.Right == nil {
  81. return node
  82. }
  83. // 一直右子树递归
  84. return node.Right.FindMaxValue()
  85. }
  86. // 查找指定节点
  87. func (tree *BinarySearchTree) Find(value int64) *BinarySearchTreeNode {
  88. if tree.Root == nil {
  89. // 如果是空树,返回空
  90. return nil
  91. }
  92. return tree.Root.Find(value)
  93. }
  94. func (node *BinarySearchTreeNode) Find(value int64) *BinarySearchTreeNode {
  95. if value == node.Value {
  96. // 如果该节点刚刚等于该值,那么返回该节点
  97. return node
  98. } else if value < node.Value {
  99. // 如果查找的值小于节点值,从节点的左子树开始找
  100. if node.Left == nil {
  101. // 左子树为空,表示找不到该值了,返回nil
  102. return nil
  103. }
  104. return node.Left.Find(value)
  105. } else {
  106. // 如果查找的值大于节点值,从节点的右子树开始找
  107. if node.Right == nil {
  108. // 右子树为空,表示找不到该值了,返回nil
  109. return nil
  110. }
  111. return node.Right.Find(value)
  112. }
  113. }
  114. // 查找指定节点的父亲
  115. func (tree *BinarySearchTree) FindParent(value int64) *BinarySearchTreeNode {
  116. if tree.Root == nil {
  117. // 如果是空树,返回空
  118. return nil
  119. }
  120. // 如果根节点等于该值,根节点其没有父节点,返回nil
  121. if tree.Root.Value == value {
  122. return nil
  123. }
  124. return tree.Root.FindParent(value)
  125. }
  126. func (node *BinarySearchTreeNode) FindParent(value int64) *BinarySearchTreeNode {
  127. // 外层没有值相等的判定,因为在内层已经判定完毕后返回父亲节点。
  128. if value < node.Value {
  129. // 如果查找的值小于节点值,从节点的左子树开始找
  130. leftTree := node.Left
  131. if leftTree == nil {
  132. // 左子树为空,表示找不到该值了,返回nil
  133. return nil
  134. }
  135. // 左子树的根节点的值刚好等于该值,那么父亲就是现在的node,返回
  136. if leftTree.Value == value {
  137. return node
  138. } else {
  139. return leftTree.FindParent(value)
  140. }
  141. } else {
  142. // 如果查找的值大于节点值,从节点的右子树开始找
  143. rightTree := node.Right
  144. if rightTree == nil {
  145. // 右子树为空,表示找不到该值了,返回nil
  146. return nil
  147. }
  148. // 右子树的根节点的值刚好等于该值,那么父亲就是现在的node,返回
  149. if rightTree.Value == value {
  150. return node
  151. } else {
  152. return rightTree.FindParent(value)
  153. }
  154. }
  155. }
  156. // 删除指定的元素
  157. func (tree *BinarySearchTree) Delete(value int64) {
  158. if tree.Root == nil {
  159. // 如果是空树,直接返回
  160. return
  161. }
  162. // 查找该值是否存在
  163. node := tree.Root.Find(value)
  164. if node == nil {
  165. // 不存在该值,直接返回
  166. return
  167. }
  168. // 查找该值的父亲节点
  169. parent := tree.Root.FindParent(value)
  170. // 第一种情况,删除的是根节点,且根节点没有儿子
  171. if parent == nil && node.Left == nil && node.Right == nil {
  172. // 置空后直接返回
  173. tree.Root = nil
  174. return
  175. } else if node.Left == nil && node.Right == nil {
  176. // 第二种情况,删除的节点有父亲节点,但没有子树
  177. // 如果删除的是节点是父亲的左儿子,直接将该值删除即可
  178. if parent.Left != nil && value == parent.Left.Value {
  179. parent.Left = nil
  180. } else {
  181. // 删除的原来是父亲的右儿子,直接将该值删除即可
  182. parent.Right = nil
  183. }
  184. return
  185. } else if node.Left != nil && node.Right != nil {
  186. // 第三种情况,删除的节点下有两个子树,因为右子树的值都比左子树大,那么用右子树中的最小元素来替换删除的节点,这时二叉查找树的性质又满足了。
  187. // 找右子树中最小的值,一直往右子树的左边找
  188. minNode := node.Right
  189. for minNode.Left != nil {
  190. minNode = minNode.Left
  191. }
  192. // 把最小的节点删掉
  193. tree.Delete(minNode.Value)
  194. // 最小值的节点替换被删除节点
  195. node.Value = minNode.Value
  196. node.Times = minNode.Times
  197. } else {
  198. // 第四种情况,只有一个子树,那么该子树直接替换被删除的节点即可
  199. // 父亲为空,表示删除的是根节点,替换树根
  200. if parent == nil {
  201. if node.Left != nil {
  202. tree.Root = node.Left
  203. } else {
  204. tree.Root = node.Right
  205. }
  206. return
  207. }
  208. // 左子树不为空
  209. if node.Left != nil {
  210. // 如果删除的是节点是父亲的左儿子,让删除的节点的左子树接班
  211. if parent.Left != nil && value == parent.Left.Value {
  212. parent.Left = node.Left
  213. } else {
  214. parent.Right = node.Left
  215. }
  216. } else {
  217. // 如果删除的是节点是父亲的左儿子,让删除的节点的右子树接班
  218. if parent.Left != nil && value == parent.Left.Value {
  219. parent.Left = node.Right
  220. } else {
  221. parent.Right = node.Right
  222. }
  223. }
  224. }
  225. }
  226. // 中序遍历
  227. func (tree *BinarySearchTree) MidOrder() {
  228. tree.Root.MidOrder()
  229. }
  230. func (node *BinarySearchTreeNode) MidOrder() {
  231. if node == nil {
  232. return
  233. }
  234. // 先打印左子树
  235. node.Left.MidOrder()
  236. // 按照次数打印根节点
  237. for i := 0; i <= int(node.Times); i++ {
  238. fmt.Println(node.Value)
  239. }
  240. // 打印右子树
  241. node.Right.MidOrder()
  242. }
  243. func main() {
  244. values := []int64{3, 6, 8, 20, 9, 2, 6, 8, 9, 3, 5, 40, 7, 9, 13, 6, 8}
  245. // 初始化二叉查找树并添加元素
  246. tree := NewBinarySearchTree()
  247. for _, v := range values {
  248. tree.Add(v)
  249. }
  250. // 找到最大值或最小值的节点
  251. fmt.Println("find min value:", tree.FindMinValue())
  252. fmt.Println("find max value:", tree.FindMaxValue())
  253. // 查找不存在的99
  254. node := tree.Find(99)
  255. if node != nil {
  256. fmt.Println("find it 99!")
  257. } else {
  258. fmt.Println("not find it 99!")
  259. }
  260. // 查找存在的9
  261. node = tree.Find(9)
  262. if node != nil {
  263. fmt.Println("find it 9!")
  264. } else {
  265. fmt.Println("not find it 9!")
  266. }
  267. // 删除存在的9后,再查找9
  268. tree.Delete(9)
  269. node = tree.Find(9)
  270. if node != nil {
  271. fmt.Println("find it 9!")
  272. } else {
  273. fmt.Println("not find it 9!")
  274. }
  275. // 中序遍历,实现排序
  276. tree.MidOrder()
  277. }

运行程序后,结果:

  1. find min value: &{2 0 <nil> <nil>}
  2. find max value: &{40 0 <nil> <nil>}
  3. not find it 99!
  4. find it 9!
  5. not find it 9!
  6. 2
  7. 3
  8. 3
  9. 5
  10. 6
  11. 6
  12. 6
  13. 7
  14. 8
  15. 8
  16. 8
  17. 13
  18. 20
  19. 40

八、总结

二叉查找树可能退化为链表,也可能是一棵非常平衡的二叉树,查找,添加,删除元素的时间复杂度取决于树的高度 h

  1. 当二叉树是满的时,树的高度是最小的,此时树节点数量 n 和高度 h 的关系为:h = log(n)
  2. 当二叉树是一个链表时,此时树节点数量 n 和高度 h 的关系为:h = n

二叉查找树的效率来源其二分查找的特征,时间复杂度在于二叉树的高度,因此查找,添加和删除的时间复杂度范围为 log(n)~n

为了提高二叉查找树查找的速度,树的高度要尽可能的小。AVL树和红黑树都是相对平衡的二叉查找树,因为特殊的旋转平衡操作,树的高度被大大压低。它们查找效率较高,添加,删除,查找操作的平均时间复杂度都为 log(n),经常在各种程序中被使用。

二叉查找树是后面要学习的高级数据结构AVL树,红黑树的基础。