1. 二叉搜索树（Binary Search Tree）
(1) 定义
二叉搜索树BST，又称 二叉查找树、二叉排序树
- 任意一个节点的值都 大于 其左子树 所有节点的值
- 任意一个节点的值都 小于 其右子树 所有节点的值
- 它的左右子树也是一棵二叉搜索树
二叉搜索树
(2) 复杂度
二叉搜索树可以大大提高搜索数据的效率
- 添加、删除、搜索的最坏时间复杂度均可优化至
)
(3) 限定条件
二叉搜索树存储的元素必须具备 可比较性
- 比如int、double等
- 如果是自定义类型，需要制定比较方式
- 不允许为null
2. 平衡二叉搜索树
(1) 二叉搜索树的复杂度
添加、删除节点时，可能会导致 二叉搜索树 退化成 链表
- 二叉搜索树复杂度可优化至：
- 链表的复杂度：
)
复杂度
(2) 平衡（Balance）
平衡
- 当节点数量固定时，左右子树的 高度 越接近，这颗二叉树就越平衡（高度越低）
理想平衡
- 像完全二叉树、满二叉树这样，高度是最小的
(3) 改进二叉搜索树
用尽量少的调整次数 达到适度平衡
- 在节点的添加、删除操作之后
- 操作二叉搜索树恢复平衡（减少树的高度）
平衡二叉搜索树：一棵达到适度平衡的二叉搜索树
(4) 平衡二叉搜索树BBST（Balance Binary Search Tree）
平衡二叉搜索树BBST，又称为 自平衡的二叉搜索树
常见的平衡二叉搜索树：
- AVL树
Windows NT 内核中广泛使用- 红黑树
C++ STL（比如map、set）
Java的TreeMap、TreeSet、HashMap、HashSet
Linux的进程调度
Ngix的timer管理
