何谓二叉查找树？

二叉查找树又名有序二叉树,排序二叉树。
二叉查找树是一种具有特殊结构的二叉树或空树。它具有以下性质：

1. 若任意节点的左子树不空，则左子树所有节点的值均小于它的根节点的值。
2. 若任意节点的右子树不空，则右子树所有节点的值均大夫它的根节点的值。
3. 任意节点的左、右子树也分别为二叉查找树。

二叉查找树的优势在于查找,插入的时间复杂度比较低，为O(logn)。因为二叉查找树不一定是一个完全二叉树，所以并不能像堆一样用数组表示，需要使用链表表示。中序遍历二叉树可得到一个关键字的有序序列，一个无序序列可以通过建构一棵二树查找树变成一个有序序列，建构树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上的新的叶子结点，在进行插入操作时，不必移动其它结点，只需要改个某个结点的指针，由空变为非空即可。
搜索,插入和删除的复杂度等于树高，期望值为O(logn),最坏为O(n)即数列有序，树退化为线性表。也就是说此时的二叉查找树的所有结点都集中在左子树或右子树上。为了尽量避免出现树退化为线性表的情况，人们对在二叉查找树的基础上，对其进行也改进，于是出现了AVL树、红黑树等。