数据结构-查找

一、基本术语

二、线性结构

ASL：平均查找长度  

1、顺序查找

1.1、代码实现

typedef struct {int* elem;int TableLen;
}SSTable;int Search_Seq(SSTable ST, int key) {ST.elem[0] = key;   //哨兵，使得循环不用判断数组是否会越界int i;for (i = ST.TableLen; ST.elem[i] != key; i--);return i;
}

           

1.2、优缺点

                缺：当n较大时，平均查找长度较大，效率低

                优：对数据元素的存储没有要求，顺序存储或链式存储都可以，对链表只能顺序查找

                对有序线性表的顺序查找，查找失败时不需要完整遍历整个线性表，从而降低查找失败的平均查找长度。

1.3、应用-有序顺序表上的顺序查找判定树

到达失败节点时所查找的长度等于它上面的一个圆形节点的所在层数

2、折半查找

2.1、代码实现

int Binary_Search(SSTable L, int key) {int low = 0, high = L.TableLen - 1, mid;while (low <= high) {mid = (low + high) / 2;if (L.elem[mid] == key)return mid;else if (L.elem[mid] > key)high = mid - 1;else low = mid + 1;}return -1;
}

2.2、折半查找判定树

①结点的值为该记录的关键字值，树的叶节点为方形，表示查找失败的区间。

②查找成功时的查找长度为从根结点到目的结点的路径上的结点数

③查找失败时的查找长度为从根节点到对应失败节点的父节点的路径上的结点数

④若有序序列有n个元素，则对应判定树有n个圆形叶节点和n+1个方型的叶节点

⑤若，则对于任何一个结点，右子树结点数-左子树结点数=0或1，即右子树结点个数多于或等于左子树结点个数。下取反之

⑥折半查找的判定树是一棵平衡二叉树

⑦元素个数为n时，树高为，比较次数最多不会超过树高

3、分块查找

又称索引顺序查找，块内无序，块间有序(第一个块中的最大关键字小于第二个块中的所有记录)

typedef struct {int MaxValue;int low, high;//区间范围
};

顺序查找：   长度为n，分为b块，每块s个记录

若，平均查找长度取到最小值

三、树形查找

1、二叉排序树

1.1、目的及定义

        ①目的：提高查找，插入和删除关键字的速度

        ②定义：左(右)子树上的所有节点均小于(大于)根节点的值  (对二叉排序树进行中序遍历，可以得到一个递增的有序序列)

1.2、二叉排序树的查找

//非递归
BiTNode* BTS_Search(BiTree T, int key) {while (T && T->data != key) {if (key < T->data)T = T->lchild;else T = T->rchild;}return T;
}
//递归
BiTNode* BTS_Search(BiTree T, int key) {if (T == NULL)return;if (T->data == key)return T;else if (T->data > key)return BTS_Search(T->lchild, key);else return BTS_Search(T->rchild, key);
}

1.3、二叉排序树的插入

二叉排序树是一种动态树表，其特点是树的构造通常不是一次生成的，而是在查找过程中，当树不存在关键字值等于给定值的结点时再进行插入

int BTS_Insert(BiTree& T, int key) {if (T == NULL) {T = (BiTNode*)malloc(sizeof(BiTNode));T->data = key;T->lchild = NULL;T->rchild = NULL;return 1;}else if (T->data == key)return 0;//插入失败else if (T->data > key)return BTS_Insert(T->lchild, key);elsereturn BTS_Insert(T->rchild, key);
}

1.4、二叉排序树的构造

void Creat_BST(BiTree& T, int str[], int n) {T = NULL;int i = 0;while (i < n) BTS_Insert(T, str[i++]);
}

1.5、二叉排序树的删除

删除某结点后，该树必须还是一棵二叉排序树

步骤：①若被删的结点z是叶节点，直接删除

           ②若结点z只有一棵左子树或者右子树，让z的子树成为z父节点的子树，代替z的位置

           ③若结点z有两棵子树，让z的直接后继(右子树的min，右子树左走到头)(或直接前驱(左子树max，左子树右走到头))代替z，然后从二叉排序树中删除这个直接后继(或直接前驱)，从而转化为①②

1.6、查找效率分析

取决于树的高度。若二叉排序树的左右子树的高度只差的绝对值不超过1，则。若该树为单支树，则ALS=O(n)

1.7、二分查找判定树和二叉排序树的区别

①查找过程：差不多

②平均时间性能：差不多

③唯一性：二分判定树唯一，但二叉排序树不唯一

④维护表的有序性：二叉排序树无需移动结点，只需修改指针即可完成插入和删除，平均执行时间为，二分查找的对象是有序顺序表，插入删除平均执行时间为O(n)

⑤若有序表是静态查找表：宜用顺序表作为存储结构，而采用二分查找实现查找

⑥若有序表是动态查找便：采用二叉排序树作为逻辑结构

2、平衡二叉树AVL

2.1、目的及定义

        ①目的：避免树的高度增长过快，降低二叉排序树的性能，适用于以查为主，很少删/插的场景

        ②定义：左子树和右子树的高度之差的绝对值不超过1

2.2、平衡二叉树的插入

若插入导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，调整。

调整方法：

①LL(A的L的L插入新结点导致不平衡)：右旋一次，将A的左孩子B作为根，而A成为B的右孩子，B原来的右子树作为A的左子树

②RR(A的R的R插入新结点导致不平衡)：左旋一次，将A的右孩子B作为根，而A成为B的左孩子，B原来的左子树作为A的右子树

③LR(A的L的R插入新结点导致不平衡)：先左旋再右旋。左旋：以A的左子树B为根，进行一次左旋操作，使B的右孩子C提升到B的位置。再进行右旋，使C提升到A的位置

④RL(A的R的L插入新结点导致不平衡)：先右旋再左旋。右旋：以A的右子树B为根，进行一次右旋操作，使B的左孩子C提升到B的位置。再进行左旋，使C提升到A的位置

2.3、平衡二叉树的构造

在构造过程中不断调整使树平衡

2.4、平衡二叉树的删除

先以二叉排序树的方法对结点z删除

步骤：①若被删的结点z是叶节点，直接删除

           ②若结点z只有一棵左子树或者右子树，让z的子树成为z父节点的子树，代替z的位置

           ③若结点z有两棵子树，让z的直接后继(右子树的min，右子树左走到头)(或直接前驱(左子树max，左子树右走到头))代替z，然后从二叉排序树中删除这个直接后继(或直接前驱)，从而转化为①②

            ④若导致了不平衡，对结点z向上回溯，找到第一个不平衡的结点w，再进行调整

2.5、平衡二叉树的查找

①与二叉排序树相同，进行关键字的比较次数不超过树的高度

②深度为h的平衡二叉树中含有最少结点数，其中n0=0,n1=1,n2=2,n3=4,n4=7......

③含有n个结点的平衡二叉树的最大高度为，因此平均查找效率为

3、红黑树

3.1、目的及定义

①目的：为了保持AVL树的平衡性，在插入和删除操作后，会非常频繁地调整全树整体拓扑结构，代价较大，为放款条件，而引入。适用于频繁删/插操作

②定义：一棵红黑树是满足红黑性质的二叉排序树

        根节点是黑色的

        虚构的外部节点是黑色的(null结点)

        不存在两个相邻的红结点

        对每个结点，从该结点到任意一个外部节点的简单路径上，所含黑节点的数量相同

        引入n+1个外部节点，保证每个内部节点子树非空

        黑高(bh)：从某结点出发(不包含该结点)到达一个外部节点的任意一个简单路上上的黑节点的总数

3.2、结论

①从根到外部节点的最长路径不大于最短路径的2倍

②有n个内部节点的红黑树的高度

③根节点黑高为h的红黑树中，内部结点至少有多少个？

        最少：总共h层黑节点的满树：

3.3、红黑树的插入

先以二叉排序树的方法对结点z插入，然后调整：新插入的结点初始为红色

①如果z的父节点是黑色，无需调整

②如果z是根节点，z为黑色，树的黑高增1

③如果z不是根节点，且父节点z.p为红色

        Ⅰ、z的叔结点y是黑色，且z是一个右孩子：LR，左旋再右旋 或 RL，右旋再左旋；

        Ⅱ、z的叔结点y是黑色，且z是一个左孩子：LL，右旋一次 或 RR，左旋一次。以上两者旋转后，将z的爷父结点交换颜色

        Ⅲ、z的叔结点u是红色：父叔都是红色的，爷是黑色的。先将父叔染为黑色，爷染为红色。然后把爷结点作为z重复循环，指针z在树上上移两层。知道满足z为根节点或ⅠⅡ的情况

3.4、红黑树的删除

4、B树和B+树

四、散列表