二叉搜索树

二叉搜索树(Binary Search Tree)是二叉树的一种，是应用非常广泛的一种二叉树，又被称为二叉查找树、二叉排序树，简称：BST；
二叉搜索树可以大大提高搜索数据的效率；

  • 任意一个节点的值都大于其左子树所有节点的值
  • 任意一个节点的值都小于其右子树所有节点的值
  • 它的左右子树也是一颗二叉搜索树
  • 二叉搜索树没有索引的概念

二叉搜索树复杂度

添加顺序或删除情况都可能造成其复杂度的变化：

  • 情况1-复杂度为：O(h) == O(logn)，复杂度根据高度而定，如下图：

image.png

  • 情况2-复杂度为：O(h) == O(n)，同样以高度决定，但是近似于链表，如下图：

image.png

平衡二叉搜索树

平衡二叉搜索树(Balanced Binary Search Tree)，简称：BBST
平衡：当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡（树高度越低）
理想平衡：最理想的平衡，就是像完全二叉树、满二叉树那样，高度是最小的
经典常见的平衡二叉搜索树，一般也称为自平衡的二叉搜索树(Self-balancing Binary Search Tree)：

  • AVL树：
    • Windows NT 内核中广泛使用
  • 红黑树：
    • C++ STL (比如：map、set)
    • Java的TreeMap、TreeSet、HashMap、HashSet
    • Linux的进程调度
    • Nginx的timer管理