二叉查找树

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

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

二叉查找树 - 图1

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

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

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

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

一、添加元素

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

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

一个节点代表一个元素，节点的 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.     }
  9.     // 将值添加进去
  10.     tree.Root.Add(value)
  11. }
  13. func (node *BinarySearchTreeNode) Add(value int64) {
  14.     if value < node.Value {
  15.         // 如果插入的值比节点的值小，那么要插入到该节点的左子树中
  16.         // 如果左子树为空，直接添加
  17.         if node.Left == nil {
  18.             node.Left = &BinarySearchTreeNode{Value: value}
  19.         } else {
  20.             // 否则递归
  21.             node.Left.Add(value)
  22.         }
  23.     } else if value > node.Value {
  24.         // 如果插入的值比节点的值大，那么要插入到该节点的右子树中
  25.         // 如果右子树为空，直接添加
  26.         if node.Right == nil {
  27.             node.Right = &BinarySearchTreeNode{Value: value}
  28.         } else {
  29.             // 否则递归
  30.             node.Right.Add(value)
  31.         }
  32.     } else {
  33.         // 值相同，不需要添加，值出现的次数加1即可
  34.         node.Times = node.Times + 1
  35.     }
  36. }

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

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

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

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

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

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

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

三、查找指定元素

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

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

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

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

四、查找指定元素的父亲

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

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

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

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

五、删除元素

删除元素有四种情况：

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

代码实现如下：

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

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

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

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

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

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

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

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

七、完整代码

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

运行程序后，结果：

  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树，红黑树的基础。