【数据结构】第9章 查找！ (二叉搜索树BST AVL树 B-(+)树 字典树
|
难产的笔记。。。本来打算用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 二叉排序树和平衡二叉树①二叉排序树及其查找过程 /** 递归实现二叉搜索树的查找操作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)
return BST;//如果没有左孩子就是最小值
else return FindMin( BST->Left );//沿左分支继续查找
}
/** 迭代找二叉搜索树元素最大值 */
Position FindMax( BinTree BST )
{
if( BST ) {
while(BST->Right) BST = BST->Right;
}
return BST;
}
②二叉排序树的插入和删除 一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。 ⑶BST中结点的删除 Status DeleteBST(BiTree &T,KeyType key)
{
//若二叉排序树T中存在关键字等于key的数据元素时，
//则删除该数据元素结点，并返回TRUE，否则返回FALSE
if(!T) return FALSE;//不存在关键字等于key的数据元素
if(EQ(key,T->data.key)) return Delete(T);//找到关键字等于key的数据元素
else if(LT(key,T->data.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 ->data = s ->data;//s指向被删除结点的前驱
if(q != p) q ->rchild = s->lchild;//重接*q的右子树
else q -> lchild = s -> lchild; //重接*q的左子树
delete s;
}
return TRUE;
}
③二叉排序树的查找分析 ④平衡二叉树(AVL树) 在AVL树中，插入一个新结点很有可能意味着失去平衡。在这种情况下要找出失去平衡的最小树根结点的指针，然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无序调整，整个二叉排序树就又成为一颗平衡二叉树。 ⑴RR旋转 ⑵LL旋转 ⑶RL旋转 ⑤平衡树查找的分析 9.2.2 B-树和B+树B树待补充…. ②B-树查找分析 ③B-树的插入和删除 ④B+树 9.2.3 键树键树又称数字查找树(DST)。它是一棵度>=2的树，树中的每个节点中不是包含一个或几个关键字，而是只含有组成关键字的符号。 我们约定，键树是有序树 ①孩子兄弟表示法的双链树 #define MAXKEYLEN 16 //关键字的最大长度
typedef struct {
char ch[MAXKEYLEN];//关键字
int num;//关键字长度
}KeysType;//关键字类型
typedef enum {LEAF,BRANCH} NodeKind;//结点种类:{叶子,分支}
typedef struct DLTNode {
char symbol;
struct DLTNode *next;//指向兄弟结点的指针
NodeKind kind;
union {
Record *infoptr;//叶子结点的记录指针
struct DLTNode *first;//分支结点的孩子链指针
};
}DLTNode,*DLTree;//双链树的类型
双链树的查找代码 Record *SearchDLTree(DLTree T,KeysType K)
{
//在非空双链树T中查找关键字等于K的记录，若存在，则
//返回指向该记录的指针，否则返回空指针
p = T->first;
i = 0;//初始化
while(p && i < K.num) {
while(p && p -> symbol != K.ch[i]) p = p->next;//查找关键字的第i位
if(p && i < K.num-1) p = p->first;//准备查找下一位
++ i;
}//查找结束
if(!p) return NULL;//查找不成功
else return p->infoptr;//查找成功
}//Search DLTree
键树中每个节点的最大度d和关键字的”基”有关，若关键字是单词，则d=27；若关键字是数值，则d=11。键树的深度h则取决于关键字中字符或数位的个数。 ②多重链表表示的Trie树(字典树) 如下图就是一个Trie树 Trie树的性质： 在Trie树上进行查找的过程为： typedef struct TrieNode {
NodeKind kind;
union {
struct {KeysType K; Record *infoptr;} lf;//叶子结点
struct {TrieNode *ptr[27]; int num;} bh;//分支结点
};
}TrieNode,* TrieTree;
Record *SearchTrie(TrieTree T,KeysType K)
{
//在字典树T中查找关键字等于K的记录
for(p = T,i = 0;//对K的每个字符逐个查找
p && p -> kind == BRANCH && i < K.num;//*p为分支结点
p = p->bh.ptr[ord(K.ch[i])],++i;);//ord求字符在字母表中序号
if(p && p->kind == LEAF && p->lf.K == K) return p -> lf.infoptr;//查找成功
else return NULL;//查找不成功
}//SearchTrie
§9.3 哈希表9.3.1 什么是哈希表根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集(区间)上，并以关键字在地址集中的”像”作为记录在表中的存储位置，这种表变称为哈希表。这一映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。 9.3.2 哈希函数的构造方法①直接定址法 ②数字分析法 ③平方取中法 ④折叠法 ※⑤除留余数法 ⑥随机数法 9.3.3 处理冲突的方法①开放定址法 ②再哈希法 ③链地址法(拉链法) (第二常用) △④建立一个公共溢出区 9.3.4 哈希表的查找及其分析在哈希表上进行查找的过程和哈希造表的过程基本一致。 【至此第9章整理完毕】 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |