0 树表的查找

前面的Blog记录了二分查找，但是二分查找要求的是有序的，才能完成。有时非有序的不太方便，就可以采用动态查找表，也就是树表。

1 二叉排序树

二叉排序树（Binary Sort Tree）又称为二叉搜索树、二叉查找树。
定义:
二叉排序树或是空树，或是满足如下性质的二叉树：

1. 若其左子树非空，则左子树上所有结点的值均小于根结点的值
2. 若其右子树非空，则右子树上所有结点的值均大于等于根结点的值
3. 其左右子树本身又各是一棵二叉排序树

左小右大，左 < 根 < 右

第一个图是二叉排序树，左子树上的节点的值都小于根节点45，右子树上的节点都大于根节点45。第二幅图当中，左子树没有，右子树中所有单词的首字母都是大于等于根节点，所以也是二叉排序树。第三个和第四个例子当中，因为下面的一个节点大于根节点，所以不满足条件。

中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。

1.1 二叉排序树的操作

假如所需要查找的对象比当前的根节点来的小，就只需要查找左子树，比根节点来的大，就去右子树找，等于根节点，就直接返回根节点。

1.1.1 二叉排序树的存储

typedef struct
{
    KeyType key; //关键字项
    InfoType otherinfo; //其他数据域
}ElemType;

typedef struct BSTNode
{
    ElemType data; //数据域
    struct BSTNode *lchild, *rchild; //左孩子右孩子指针
}BSTNode, *BSTree;

BSTree T;//定义二叉排序树
1
2
3
4
5
6
7
8
9
10
11
12
13

1.1.2 二叉排序树的递归查找

左右子树都是调用自身的算法去查找。

BSTree SearchBST(BSTree T, KeyType key)
{
	if((!T)||key == T->data.key)
	{
		return T;
	}
	else if(key < T->data.key)
	{
		return SearchBST(T->lchild, key);//在左子树中继续查找
	}
	else
	{
		return SearchBST(T->rchild, key);//在右子树中继续查找
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.1.3 二叉排序树的插入

要插入的节点比根节点小，就放在左孩子，之后再与左孩子当中的根节点继续进行比较。比根节点大，则放入右孩子，再继续进行比较。
思想

插入的节点一定是在叶节点上。

1.1.4 二叉排序树的生成

一个无序序列可通过构道二叉排序树而变成一个有序序列，构造树的过程就是对无序序列进行排序的过程（中序遍历）。
插入的结点均为叶子结点，故无需移动其他结点。相当于在有序序列上插入记录而无需移动其他记录。
但是：
关键字的输入顺序不同，建立的不同的二叉排序树。

形态不一样，那么查找效率就不一样。

1.1.5 二叉排序树的删除

最重要的就是最后两条。

删除的是叶子节点的话，直接删除。


20和88直接删除，，修改双亲的左右孩子即可。
把其双亲结点中相应指针域的值改为“空“。

被删除的结点只有左子树或者只有右子树，用其左子树或者右子树替换它（结点替换）


直接修改双亲指针，使双亲直接指向被删除节点的左右孩子即可。

被删除的结点既有左子树，也有右子树

这种情况，仍然要保持中序遍历是有序的，该怎么做？
一种方法就是用其中序遍历的前驱节点来代替他。这样仍然能保持中序遍历不变，所以去找其左子树，与其挨得最近的一个节点进行代替，这里也就是用40来代替50。

当然了，也可以用其后继替换之，然后再删除该后继结点。后继是右子树中最小的结点。这里就是把80替换50，80成为根节点后直接一条线指向90。

一些例子。

1.2 二叉排序树的查找性能分析

每一个节点需要查找几次，与这个节点所在二叉排序树的层次有关。二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。
综上得出，比较的关键字次数 = 此节点所在的层次数。

层数上的规定，最好不要超过$lo{g}_{2}n+1$层，最坏的情况大为$n$层，即为右边图的那种情况。

层数最多的情况下，ASL是与顺序查找时是一样的。

2 平衡二叉树（AVL树）

问题：如何提高形态不均衡的二叉排序树的查找效率？
解决办法：做“平衡化”处理，即尽量让二叉树的形状均衡！这就是平衡二叉树的由来。

为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子(BF)。
平衡因子=结点左子树的高度-结点右子树的高度

根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1,0,1。
绝对值小于等于1 ，不超过1。

对于一棵有$n$个结点的AVL树，其高度保持在$O(lo{g}_{2}n)$数量级，ASL也保持在$O(lo{g}_{2}n)$量级。

2.1 失衡二叉排序树的分析与调整

如果在一棵AVL树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡。（上图的53节点就失衡了）

如果发现插入节点后，不止一个失衡的结点时，就找一个最小失衡子树的根节点作为失衡节点。


调整原则：

1. 降低高度
2. 保持二叉排序树性质（左子树比根节点小，右子树比根节点大），所以最小的放在最左边。

2.1.1 LL型调整

LL型就是插入一个新节点，这个新节点的插入位置就是在失衡节点的左子树的左子树上面。

调整：
将A节点降下来，B节点升上去。
或者是平衡旋转的方法，直接转下来。

2.1.2 RR型调整

RR型就是插入一个新节点，这个新节点的插入位置就是在失衡节点的右子树的右子树上面。

思路还是降高度。



举例：

解答：

2.1.3 LR型调整

LR型就是插入一个新节点，这个新节点的插入位置就是在失衡节点的左子树的右子树上面。

调整还是按照原则。



第三步这样放是为了保持AVL树的特性。

2.1.4 RL型调整

RL型就是插入一个新节点，这个新节点的插入位置就是在失衡节点的右子树的左子树上面。

与LR树类似。

3 根据以上几种类型构造AVL树

插入7时，发现是LR类型，所以根据LR类型进行调整，即7节点上升，之后3和16分别作为其左子树与右子树。

此时又出现了LL型，直接将中间节点11上升，然后一个作为其左孩子，一个作为其右孩子。
之后插入26节点，发现出现了RR失衡。


之后又出现了RL失衡。

RL与LR就是把处在中间值的提上去，然后其余两个作为左子树与右子树。


3个顶点失衡，调整最小的那一颗子树。，即红色颜色标注的，此为LR型失衡。
至此，AVL树构造完毕。