难产的笔记。。。本来打算用1天 结果前前后后拖了5天
§9.1 静态查找表9.1.1 顺序表的查找
各种扫 自己脑补吧 复杂度O(n)
9.1.2 有序表的查找
若表是单调的，则可以利用二分查找。复杂度O(logn)
9.1.3 静态树表的查找
见
9.1.4 索引顺序表的查找
建立索引表查找
§9.2 动态查找表
动态查找表的特点是，表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。
9.2.1 二叉排序树和平衡二叉树
①二叉排序树及其查找过程 二叉排序树(BST)或者是一棵空树；或者是具有下列性质的二叉树： ⑴若它的左子树不空，则左子树上所有节点的值均小于它的根结点的值 ⑵若它的右子树不空，则右子树上所有节点的值均大于它的根结点的值 ⑶它的左右子树也分别为二叉排序树 查找代码如下
/** 递归实现二叉搜索树的查找操作Find */Position Find( ElementType X,BinTree BST){if(!BST) return NULL;//空树if(X > BST->Data) return Find(X,BST->Right);if(X < BST->Data) return Find(X,BST->Left);return BST;/**找到了*/}/** 迭代实现二叉搜索树的查找操作Find */Position Find( ElementType X,BinTree BST){while(BST) {if(X > BST->Data) {BST = BST->Right;}else if(X < BST->Data) {BST = BST->Left;}else return BST;//找到了}return NULL;//查找失败}/** 递归找二叉搜索树元素最小值 */Position FindMin( BinTree BST ){if(!BST) return NULL;else if(!BST->Left)FindMin( BST->Left );//沿左分支继续查找}/** 迭代找二叉搜索树元素最大值 */Position FindMax( BinTree BST ){if( BST ) {while(BST->Right) BST = BST->Right;}return BST;}
②二叉排序树的插入和删除 ⑴BST中结点的插入 新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或者右孩子。因此把查找算法改一下就可以了。
一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
⑶BST中结点的删除 分三种情况处理： 1.删除的是叶子结点，那么直接删除即可。 2.删除的结点只有左子树或右子树，那么直接删除然后把子树放到它父亲上即可。 3.删除的结点左子树和右子树均不空。有两种做法，一是左子树接上来，右子树放到左子树的最右边。二是用直接前驱(后继)代替它，然后删除它的直接前驱(后继)(具体见P230) 删除的代码如下
Status DeleteBST(BiTree &T, KeyType key){((key)) (key)) return DeleteBST(T->lchild,key);else return DeleteBST(T->rchild,key);}Status Delete(BiTree &p){//从二叉排序树中删除结点p，并重接它的左子树或右子树if(!p->rchild) {//右子树空则只需要重接它的左子树q = p;p = p->lchild;free(q);}else if(!p->lchild) {//只需重接它的右子树q = p;p = p->rchild;free(q);}else {//左右子树都不空q = p;s = p->lchild;while(s->rchild) {//转左，然后向右到尽头q = s;s = s->rchild;}p s (q != p) q ->rchild = s->lchild;//重接*q的右子树else q -> lchild = s -> lchild; //重接*q的左子树delete s;}return TRUE;}
③二叉排序树的查找分析 对ASL的计算发现，如果二叉树趋于”平衡”，那么它的ASL就可以有效降低，效率提高。在某些情况下，尚需在构成二叉排序树的过程中进行”平衡化”处理，称为二叉平衡树。
④平衡二叉树(AVL树) 平衡二叉树又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。 若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1,0,1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。 n层的AVL树的最小结点数符合类斐波那契。 1层的AVL树最小需要1个结点，2层的AVL树最小需要2个结点，3层的至少需要4个结点，4层的最小需要7个结点… 以此类推n层的最少结点=(n-1)层最少结点+(n-2)层最少结点+1
在AVL树中，插入一个新结点很有可能意味着失去平衡。在这种情况下要找出失去平衡的最小树根结点的指针，然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无序调整，整个二叉排序树就又成为一颗平衡二叉树。 失去平衡的最小子树是指以离插入节点最近且平衡因子异常(绝对值>1)的结点作为根的子树。 假设用A来表示失去平衡最小子树的根结点，则调整该子树的操作无外乎有下面4种情况
一个人的心胸宽阔，可以容不能容的事，可以赢难以赢的人。
