1 什么是二叉搜索树？

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

二叉搜索树规则是：

（1）在查找和插入上很有效率，时间复杂度不超过O（logN）；

（2）任何节点的键值一定大于其左子树中的每一个节点的键值，一定小于其右子树节点的键值。

2 平衡二叉搜索树的优点是什么？

它除了具备二叉查找树的基本特征之外，还具有一个非常重要的特点：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度相差最多为1（平衡因子 ）。

而不同的平衡条件会造成不同的效率；平衡二叉树的性能优势：

很显然，平衡二叉树的优势在于不会出现普通二叉查找树的最差情况。其查找的时间复杂度为O(logN)。二叉查找树会因某些插入和删除操作使得二叉树不平衡，从而导致元素访问的效率低下，因此，平衡二叉搜索树的元素搜索（访问）时间平均而言也就比较小，一般而言其搜寻时间可节省25%左右，因为平衡二叉搜索树没有极度不平衡的情况发生。

平衡二叉树的缺陷：

(1) 平衡二叉搜索树实现比二叉搜索树复杂（要维持平衡），因此，插入节点及删除节点的平均时间要长。

(2) 所有二叉查找树结构的查找代价都与树高是紧密相关的，能否通过减少树高来进一步降低查找代价呢。我们可以通过多路查找树的结构来做到这一点。

(3) 在大数据量查找环境下(比如说系统磁盘里的文件目录，数据库中的记录查询等)，所有的二叉查找树结构(BST、AVL、RBT)都不合适。如此大规模的数据量（几G数据），全部组织成平衡二叉树放在内存中是不可能做到的。那么把这棵树放在磁盘中吧。问题就来了：假如构造的平衡二叉树深度有1W层。那么从根节点出发到叶子节点很可能就需要1W次的硬盘IO读写。大家都知道，硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。查找效率在IO读写过程中将会付出巨大的代价。在大规模数据查询这样一个实际应用背景下，平衡二叉树的效率就很成问题了。