二叉搜索树（BST） ​

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。二叉搜索树的定义：

一棵二叉树，可以为空；如果不为空，满足以下性质：

1. 非空左子树的所有键值小于其根结点的键值；
2. 非空右子树的所有键值大于其根结点的键值；
3. 左、右子树都是二叉搜索树。

二叉搜索树相比于其他数据结构的优势在于查找、插入的时间复杂度较低为 O(logn) 。

二叉搜索树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。

重要特性：

1. 二叉搜索树的中序遍历的结果是有序的。
2. 在二叉搜索树中搜索值时，可以利用有序的特性判断左右的方向，从而决定递归的方向。

相关算法题 ​

• 二叉搜索树
  • 098. 验证二叉搜索树
  • 700. 二叉搜索树中的搜索
  • 530. 二叉搜索树的最小绝对差
  • 501. 二叉搜索树中的众数
  • 235. 二叉搜索树的最近公共祖先
  • 701. 二叉搜索树中的插入操作
  • 450. 删除二叉搜索树中的节点
  • 669. 修剪二叉搜索树
  • 108. 将有序数组转换为二叉搜索树
  • 538. 把二叉搜索树转换为累加树