二叉搜索树的概念 

二叉搜索树又称二叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:

• 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值。 • 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值。 • 它的左右⼦树也分别为二叉搜索树

示例： 

2，二叉搜索树性能分析 

N为节点个数 最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其高度为： O(logN) 最差情况下，⼆叉搜索树退化为单⽀树(或者类似单支)，近似于链表，其高度为： O(N）

所以，综合而言二叉搜索树增删查改时间复杂度为： O(N) 。我们知道数组的增删查改的效率也是O(N),因此这个二叉搜索树的效率是无法满足我们需求的。在后面的文章中，会介绍二叉搜索树的变形，平衡二叉搜索树AVL和红黑树，才能适⽤于我们在内存中存储和搜索数据。

•另外需要说明的是，⼆分查找也可以实现 O(logN) 级别的查找效率，但是⼆分查找有两⼤缺陷：

1. 需要存储在⽀持下标随机访问的结构中，并且有序。 2. 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数据。