1.二叉排序树
二叉排序树可以提高查找、插入和删除的效率。
（1）二叉排序树（BST）的定义
定义比较简单，左子树所有结点<根节点<右子树所有结点
同时左右子树也分别都是二叉排序树
特点：对二叉排序树进行中序遍历，可以得到一个递增有序序列。
（2）二叉排序树的插入
BST的插入是为了其构造而使用的一个操作
给定的查找表不会直接给出BST的树形结构，而是给出一个线性的序列，所以在使用BST进行查找时，要先根据原始的线性查找表构造出BST的树形结构，这个过程的方法就是将关键字按二叉排序树的定义挨个插入到树中。
插入方法就是：
当树为空时，直接插入；当树不为空时，将待插入关键字逐层与根节点的值进行比较，如果待插入关键字小于当前根节点，则向左子树深入；反之则向右子树深入。直到到达最后一层，将这个关键字插入为BST的一个新的叶结点。
BST的插入算法是一个递归算法。
（3）二叉排序树的删除
删除某个结点分为两种情况，当删除的节点为叶结点时，则直接删除；否则需要用其子树上的结点进行重新连接。
删除非叶节点时，如果这个节点的左/右子树为空，则直接把另一边的子树替补到当前位置即可，比较简单。
如果该结点的左右子树都不为空，则需要找到其右子树上最小的节点k（即右子树中序序列中第一个结点）。用结点k替补到当前位置后，还需要对结点k进行删除操作。
（4）二叉排序树的查找效率分析。
（注意二叉排序树与二分查找的对比）
其查找效率受到树高的影响
在平衡二叉树的情况下，平均查找长度为O(log2n)
在最坏的单支树的情况下，平均查找长度为O(n)
2，平衡二叉树
平衡二叉树是一种特殊的BST，为了提高BST的查找效率。