数据结构-动态查找
动态查找
当查找表以顺序存储结构存储且需要保持有序时，若对查找表进行插入、删除或排序操作，就必须移动大量的记录，当记录数很多时，这种移动的代价很大。
若查找表无序，则插入删除可无需移动大量记录，但于查找不利。
利用树的形式组织查找表，可以对查找表进行动态高效的查找。
二叉排序树
二叉排序树(Binary Sort Tree或Binary Search Tree) 的定义为：二叉排序树或者是空树，或者是满足下列性质的二叉树。
(1) ：若左子树不为空，则左子树上所有结点的值(关键字)都小于根结点的值；
(2) ：若右子树不为空，则右子树上所有结点的值(关键字)都大于根结点的值；
(3) ：左、右子树都分别是二叉排序树。
结论：若按中序遍历一棵二叉排序树，所得到的结点序列是一个递增序列。
BST树的查找
1 查找思想
①若根结点为空，则表示查找失败；
②根节点非空，将给定的K值与二叉排序树的根结点的关键字进行比较
若相等： 则查找成功；
③ 给定的K值小于BST的根结点的关键字：继续在该结点的左子树上进行查找；
④ 给定的K值大于BST的根结点的关键字：继续在该结点的右子树上进行查找。
2 算法实现
BSTNode *BST_Serach(BSTNode *T , KeyType key)
{ if (T==NULL) return(NULL) ;
else
{ if (T->key==key) ) return(T) ;
else if (key< T->key) )
return(BST_Serach(T->Lchild, key)) ;
else return(BST_Serach(T->Rchild, key)) ;
}
}
BST树的插入
插入的过程与查找类似，只是当查找不成功时，根据关键字与根结点的大小，将新结点（关键字的值）插入根结点的相应孩子的位置（左或者右）. 在BST树中插入一个新结点，要保证插入后仍满足BST的性质。
1 插入思想
在BST树中插入一个新结点x时，若BST树为空，则令新结点x为插入后BST树的根结点；否则，将结点x的关键字与根结点T的关键字进行比较：
① 若相等： 不需要插入；
② 若x.keykey：结点x插入到T的左子树中；
③ 若x.key>T->key：结点x插入到T的右子树中。
算法实现
⑴ 递归算法
⑵ 非递归算法
void Insert_BST (BSTNode *T , KeyType key)
{ BSTNode *x, *p , *q ;
x=(BSTNode *)malloc(sizeof(BSTNode)) ;
X->key=key; x->Lchild=x->Rchild=NULL ;
if (T==NULL) T=x ;
else
{ p=T ;
while (p!=NULL)
{ if (p->key==x->key ) return ;
q=p ; /*q作为p的父结点 */
if (x->key< p->key) ) p=p->Lchild ;
else p=p->Rchild ;
}
if (x->key<q->key ) q->Lchild=x ;
else q->Rchild=x ;
}
}
对于一个无序序列可以通过构造一棵BST树而变成一个有序序列。
由算法知，每次插入的新结点都是BST树的叶子结点，即在插入时不必移动其它结点，仅需修改某个结点的指针。
利用BST树的插入操作，可以从空树开始逐个插入每个结点，从而建立一棵BST树
二叉排序树性能
二叉排序树查找关键字的比较次数，等于该结点所在的层次数（查找成功）； 若查找不成功，其比较次数最多为树的深度。
对于一棵具有n个结点的树来说，其深度介于㏒2n+1与n之间。
二叉排序树的形态对于查找效率至关重要，或者说，一棵二叉排序树不一定就能提高查找的速度，而是要看这棵树的形态。
平衡二叉排序树
如果能构造出一棵左右子树相对“均衡”的树，则树的深度就会比较小，就能体现出二叉排序树的良好性质，查找时能得到最好的效率，这就是平衡二叉排序树。
平衡二叉排序树(Balanced Binary Tree或Height-Balanced Tree)是在1962年由俄罗斯数学家Adelson-Velskii和Landis提出的，又称AVL树。
平衡二叉树的定义
平衡二叉树或者是空树，或者是满足下列性质的二叉树。
⑴ 左子树和右子树深度之差的绝对值不大于1；
⑵ 左子树和右子树也都是平衡二叉树。
平衡因子(Balance Factor) ：二叉树上结点的左子树的深度减去其右子树深度。
平衡二叉树上每个结点的平衡因子只可能是-1、0和1，如果有一个结点的平衡因子的绝对值大于1， 该二叉树就不是平衡二叉树。
如果一棵二叉树既是二叉排序树又是平衡二叉树，称为平衡二叉排序树(Balanced Binary Sort Tree) 。
结点类型定义如下：
typedef struct BNode
{ KeyType key ; /* 关键字域 */
int Bfactor ; /* 平衡因子域 */
… /* 其它数据域 */
struct BNode *Lchild , *Rchild ;
}BSTNode ; 在平衡二叉排序树上执行查找的过程与二叉排序树上的查找过程完全一样，即在AVL树上执行查找时，和给定的K值比较的次数不超过树的深度。
具有n个结点的AVL树，最大深度是多少？
含义n个结点的平衡二叉树的最大深度是O(㏒2n)
在平衡二叉排序树上进行查找的平均查找长度和
㏒2n同一个数量级，平均时间复杂度为O(㏒2n)。
平衡二叉排序树的构造
基本思想
在构建二叉排序树的过程中，每当插入（删除）一个结点时，
先检查是否因插入而破坏了平衡，
若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。