二叉搜索树（BST）
简述
二叉查找树（Binary Search Tree），又叫有序二叉树，具有以下3个性质：
- 左子树如果不为空，那么它所有的节点的值都小于它的根节点
- 右子树如果不为空，那么它所有的节点的值都大于它的根节点
- 任意节点的左、右子树都是二叉查找树。
复杂度
时间复杂度
由于二叉搜索树的查询、插入或删除的时间复杂度取决于目标节点到根节点的距离，即深度。
二叉搜索树可分为平衡树和非平衡树两大类，注：此处的平衡是指所有叶子的深度趋于平衡。
- 平衡度最高的二叉树是AVL树，其时间复杂度同二分查找一样为O(logN)
- 非平衡树最极端的情况是偏斜二叉树，即所有的节点都在根节点的一边，也就是链表结构。此时树的深度为n，其时间复杂度同顺序查找一样为O(n)
因此，二叉搜索树的时间复杂度介于O(logn)和O(n)之间。
空间复杂度
二叉搜索树的空间大小只与其节点的个数相关，所以其空间复杂度是O(n)。
遍历方式
二叉搜索树有三种遍历方式，分别是：
- 先序遍历：根节点→左节点→右节点。
- 中序遍历：左节点→根节点→右节点，结果是一个有序序列。
- 后序遍历：左节点→右节点→根节点。
优缺点
优点
二叉搜索树是介于数组和链表的一种折中方案，数组查找方便但是插入或删除麻烦，而链表则恰好与数组相反。
相较之下，二叉查找树在查找、插入或删除的时间复杂度都较低，适用于处理大批量的动态数据。
缺点
构建二叉搜索树本身或维护其平衡需要额外的时间或空间成本。
参考资料