二叉搜索树有以下特点：

1. 每个节点有唯一的搜索关键值；
2. 任意节点，如果存在着左子节点，那么左子节点的关键值小于此节点的关键值；
3. 任意节点，如果存在着右子节点，那么右子节点的关键值大于此节点的关键值；

另外，搜索树可以带索引，在每个节点中加入字段，其值为其左子树的节点数目加1。此方式的索引，可以明确地知道节点在此树中的从小到大的排序位置。

    10
   ／ \
   6 16
  / \ \
  3 8 18

关键值:索引字段值
10:4,6:2,16:1,3:1,8:1,18:1

对于此索引字段，我一直未找到其有什么作用。查找搜索，加了此索引字段就不用比较？也要比较，比较次数也不见得少。删除／插入也要查找，那么加入此索引字段作肾吗？唯一的我能看到的作用是查看当前节点的状态，给出稍微详细的信息，而不是查找。个人觉得还不如完全二叉树，直接线性表索引显然更好些。

查找

由于二叉搜索树的性质，是查找元素时，只要比较搜索的关键值与当前节点的关键值，小于继续搜索左子树，大于则搜索右子树，即可。时间复杂度为O(h)，由于树不一定是完全二叉树，可能存在着左、右斜二叉树，所以不一定保证O(logn)。

插入

按查找的思路，可以把要插入的元素的关键值看作查找此关键值。当从根节点一直往下找，如果真有此关键值，证明要插入的元素关键值重复，不能进行插入；如果查找不到，必然会最终碰到左子节点或者右子节点为空，只要将查找路径上的这个为空的左子节点或者右子节点，设置为要插入的新元素即可，成为新的节点。复杂度也是O(h)

删除

对于叶子节点，查找成功后，可直接删除，不影响树的结构。对于非叶子节点，需要用此节点的左子树的最大节点代替已删除的节点，或者用此节点的右子树的最小节点代替。这最大节点和最小节点应该都是叶子节点。复杂度为O(h)。

如，

     20
    /  \
   10  30
   /\   | \
  9 14 24 32

     14
    /  \
   10   30
   /    | \
  9    24 32

     24
    / \
   10 30
   /\   \
  9 14   32

删除20时，需要将其左子树的14上升到原根节点的位置；或者将其右子树的24上升到原根节点的位置。

AVL树

首先，AVL树是一种平衡树。平衡树是指节点数为n且高度为logn级别的树。AVL树是根据提出人的姓名命名的。

AVL树就是任意节点的左右子树的高度绝对差为1。通常会定义其平衡因子＝左子树的高度 - 右子树的高度，平衡因子可能是-1、0、1。

查找

过程如二叉搜索树一样，但AVL树的高度是logn，所以可以确定其时间复杂度是O(logn)

插入

插入的操作可能采用二叉搜索树的插入方法，当不平衡时，再调整节点。

首先，插入之前，它应该是AVL树。插入新节点之后，树可能依然是AVL树，也可能不是AVL树。而不能成为AVL树，其原因必然是：树的某些节点的平衡因子从-1变为-2，或者从1变为2。而平衡因子变化的节点，也一定是从新节点到根节点这一路径上的节点。

在这些新插入的节点到树的根节点这一路径中，可能存在着离新节点最近的原平衡因子为1或者为-1的A节点。从A节点到新节点之间的所有节点的平衡因子原来都应该是0。因为，如果不是0，而是1或者-1，那么A节点就找错了。

其次，调整。对于插入操作后不平衡的树，需要调整使得插入后的平衡因子为2或者-2的节点变回为1、0、-1。

基本的操作步骤：

1. 在树中搜索新节点的关键值，如果关键值不存在，插入并记录原树中的A节点；如果存在，退出。

2. 如果没有所谓的A节点，那么修改新节点到树根节点的平衡因子，从0修改为1或者-1。

3. 如果存在A节点，需要分情况：

   • 如果新插入的节点在A节点的左子树上，而A节点原平衡因子为-1，那么插入后的树也是平衡的，可直接修改从新节点到A节点上的平衡因子即可；
   • 如果新插入的节点在A节点的左子树上，而A节点原平衡因子为1，那么A节点的平衡因子会变为2，需要调整；
   • 如果新插入的节点在A节点的右子树上，而A节点原平衡因子为-1，那么A节点的平衡因为会变为-2，需要调整；
   • 如果新插入的节点在A节点的右子树上，而A节点原平衡因子为1，那么插入后的树也是平衡的，可直接修改从新节点到A节点上的平衡因子即可；

下面对需要调整的3.2和3.3进行进一步的说明。

3.2

新节点在A的左子树上，又可以分两种情况：新节点在左子树的左子树上(LL)，新节点在左子树的右子树上(LR):

LL：对于LL情况，由于A节点的原平衡因子为1，所以必定存在B节点且其平衡因子为0。假设BL的高度为h，则BR和AR的高度应该也为h，以A为根节点的子树高度为h+2。插入后BL高度变为h+1，A节点平衡因子变为2，B节点平衡因子变为1。BL中可能有更多的节点的平衡因子从0变为1，但这里只讨论1个B，因为只有从新插入的节点到树的根节点中的节点有变化。

为了减少各节点平衡因子的变化，就尽量使以A为子树的高度在调整之后仍然为h+1。这里可以将B节点上移，A节点转而当作B节点的右子节点，并将BR当作A节点的左子树。对于调整的整个子树来说，原来的高度是h+2，调整后保持不变，也就不用调整A节点以上的节点的平衡因子了，但需要再次调整A和B的平衡因子。

LR：对于LR情况，BR在插入新节点后，高度为h+1，也就是说，插入后必定存在C节点。而且，CL和CR的高度只可能是h或者h-1，且不能同为h-1。

对于此情况，不能采用LL的方法。因为把BL当作已经下沉的A的左子树，只会引起新的不平衡。

所以，需要把C上移，并替代原来的A节点，而A节点下沉，然后分别将CL和CR作为B和A的右子树和左子树。对于调整的整个子树来说，原来的高度是h+2，调整后保持不变，也就不用调整A节点以上的节点的平衡因子了，但需要再次调整A、B、C的平衡因子。

3.3

新节点在A的右子树上，又可以分两种情况：新节点在左子树的左子树上(RL)，新节点在左子树的右子树上(RR):

RL、RR的调整方法基本与LR、LL一样，只是方向变化了而已，不多叙述。