BST and AVL-tree
BST
【二叉排序树】或者是一棵空树；或者是具有如下性质的二叉树：
- 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树。
二叉排序树也称为二叉搜索树，通常取二叉链表作为二叉排序树的存储结构。
中序遍历BST可以得到一个关键字的有序序列。
这句话的意思是，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
BST的插入
新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
插入过程中，每次插入的新结点都是BST上新的叶子结点，则在进行插入操作时，不必移动其他结点，仅需移动某个结点的指针，由空边为非空即可。这就相当于在一个有序序列上插入一个记录而不用移动其他记录。它表明，BST既拥有类似折半查找的特性，又采用了链表作为存储结构，因此是动态查找表的一种适宜表示。
BST的删除
BST结点的删除分为三种情况：
- 待删除结点为叶结点；
- 待删除结点只有左子树或者右子树；
- 待删除结点既有左子树也有右子树。
BST的查找分析
假设在含有n(n>=1)个关键字的序列中，i个关键字小于第一个关键字，n-i-1个关键字大于第一个关键字，则由此构造而得的BST在n个记录的查找记录概率相等的情况下，其平均查找长度为
其中P(i)为含有i个结点的二叉排序树的平均查找长度，则P(i)+1为查找左子树中每个关键字时所用比较次数的平均值，P(n-i-1)+1为查找右子树中每个关键字时所用比较次数的平均值。又假设表中n个关键字的排列是“随机”的，即任一个关键字在序列中将是第1个，或第2个，…，或第n个的概率相同…然后各种化简计算得到如下结果：
则，当n>=2时，。
在随机的情况下，BST的平均查找长度和logn是等数量级的。然而，在某些情况下(有人研究证明，这种情况出现的概率约为46.5%)，尚需在构成二叉排序树的过程进行“平衡化”处理，成为二叉平衡树。
AVL树
【定义】它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF(Balance Factor)定义为该结点的左子树深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1，0，1.
只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a(即a是离插入点最近，且平衡因子绝对值超过1的祖先结点)，则时取平衡后进行调整的规律可归纳为下列4种情况：
- 单向右旋LL
- 单向左旋RR
- 双向旋转(先左后右)LR
- 双向旋转(先右后左)RL
LL：左子树根结点的左子树上插入结点； LR：左子树根结点的右子树上插入结点； RL：右子树根结点的左子树上插入结点； RR：右子树根结点的右子树上插入结点；
四种调整方法如下图所示：
用Nh表示深度为h的平衡树中含有的最少结点树。显然N[0]=0,N[1]=1,N[2]=2，并且N[h] = N[h-1] + N[h-2] + 1。
如此可推后面的。有些类似于斐波那契数列的感觉。
含有n个结点的平衡树的最大深度为，其中
。因此，在平衡树上进行查找的时间复杂度为
O(logn)。
上述对二叉排序树和二叉平衡树的查找性能的讨论都是在等概率的前提下进行的，若查找概率不等，则类似之前静态树表的查找中的讨论(需要对待查记录序列先进行排序，使其关键字递增(或递减)有序，然后按算法构造一棵次优查找树)。
显然，次优查找树也是一棵二叉排序树，但次优查找树不能在查找过程中插入结点生成。BST是动态树表，最优或次优查找树是静态树表。