数据结构6

数据结构6 集合 动态查找表

查找操作

静态查找表 & 动态查找表

• 静态查找表：元素个数不变，元素值不变一般使用C++ 的原始数组
• 动态查找表：允许插入删除的查找表不能用线性表存储，会造成大量数据的移动

无序表&有序表的查找

无序表查找的复杂度是O(n)的。有序表查找可以采用顺序查找、二分查找、插值查找、分块查找。

顺序查找

与无序表查找唯一的不同在于若元素不存在无需查到表头

二分查找

时间复杂度是O(log N)

插值查找

适用于数据分布比较均匀的情况，但缺点是计算量较大

分块查找

块内的数据元素可以是有序存储，也可以是无序的，但块之间必须是有序的。

二叉查找树 BST

左子树元素都小于根结点，右子树元素都大于根结点

数据成员：一个指向根结点的指针公有成员函数：find，insert，remove，构造函数，析构函数私有成员函数：find，insert，remove（递归函数的实现）

insert、remove函数采取引用传递，直接修改原树的结构

删除操作分几种情况讨论：

1. 删除叶结点：直接删除

2. 删除只有一个儿子的结点

3. 删除有2个儿子的结点：选取替身结点（这样可以尽可能的不让树变高）我们选取左子树的最大值或右子树的最小值

性能上，在最坏的情况下，BST 会退化成一个单链表，时间复杂度是O(N)
可以证明，平均情况下，时间复杂度是O(logN)

平均性能
n个结点二叉查找树可能有n种形态，如果这些形态出现的概率相等。得到：
P(n) = 1.38logN

平衡二叉树（平衡树）

满足一定条件的二叉查找树，保证树的高度是O(logN)
常用的平衡树：AVL 红黑树 AA树

AVL树

平衡因子：结点的平衡度是左右子树的高度差平衡因子为+1，-1，0

AVL插入操作

自插入结点开始，向根回溯。如果没有破坏平衡，则只修改平衡因子。但如果平衡被破坏，我们需要调整平衡。

通过旋转：LL LR RL RR

AVL删除操作

检查失衡：（假设都在左子树删除）分以下几种初始状态进行讨论：

• T是平衡的没有失衡，高度没变，不需要向上继续调整

• T左高右低没有失去平衡，但整棵树变矮了，所以需要向上调整

• T左低右高失去平衡（1）T右子树平衡，RR旋转，不需向上调整（2）T右子树左高右低，RL旋转，需要向上调整（3）T右子树左低右高，RR旋转，需要向上调整

remove函数设计为bool类型，若返回值为true，表示这棵树没有变矮，无需进一步向上调整。但如果返回值为false，则需要向上调整，调用adjust函数。

红黑树

红黑树的插入

方法：通过旋转和重新着色调整过程可能回溯到根结点（反正根结点一定是黑色的）

当出现了连续红色节点时，我们需要进行
平衡调整：如果你的叔叔是红色的，那么进行一次重新着色，然后矛盾上交，继续向上回溯。

如果你的叔叔是黑色的，那么进行LL or RR or LR or RL旋转，可以维护根结点的黑色，同时不会再出现连续红色节点。（认为空结点是黑结点）

综上可见，红黑树的插入操作并不复杂。

与其他各种树一样，红黑树的插入同样也是递归函数，借助于私有成员函数来实现。

红黑树的删除

被删结点的情况：

• 红色叶结点：直接删除

• 只有一个儿子的叶结点：肯定是黑结点，儿子是红结点，修改儿子为黑节点

• 黑色叶结点：导致该路径上少了一个黑结点，需要调整

调整的思想是让兄弟的某个红孩子转移到这条路径上，并改为黑结点（借一个）

鉴于笔者并没有听懂翁阿姨课上的各种《红孩子》《黑孩子》《脱贫》，于是在课上打开了OIWIKI，发现出人意料地清晰，于是附上链接：
OIWIKI红黑树删除操作

删除操作：
case0：只有一个结点
case1：删除结点既有左又有右结点，找到直接前驱或直接后继进行替换。
case2：删除结点只有一个叶结点，则该结点一定为黑色，其孩子一定为红色，则将其删除，用子结点替换，并将该结点染成黑色。
case3：删除结点为红色叶结点，直接删除。
**case4：**删除结点为黑色叶结点，需要进行调整（唯一一个需要调整的情况）

删除调整操作：（情况太多不做罗列的，对着图写就好呜呜呜）

AA树

定义：左孩子不能为红色的红黑树用结点层次表示平衡信息，水平链表示法：将指向红结点的链画成水平的，可以看出所有叶子结点的高度都是相同的。

不可以出现水平左链和连续水平右链！！！

AA树插入操作

• 水平左链的解决：对结点执行一个LL旋转但是这可能会产生连续水平右链，需要继续调整

• 连续水平右链的解决：对结点执行一个RR旋转但是会导致层次的增长，需要继续调整

AA树插入的调整可能会一直回溯到根结点（提高了一个层次）

AA树的删除操作

最终总能归结到删除第一层的结点

被删结点情况：

• 被删结点是红结点：直接删除

• 被删结点有一个红结点的儿子：将此红结点替换为被删结点

• 被删结点是黑结点：会影响平衡，需进行调整

删除调整：

• 被删结点是黑色的右孩子（最简单情况）：删除后产生水平左链，进行LL旋转，后向上调整

• 被删结点是黑色的右孩子（最复杂情况）：删除后父节点LL，根右孩子LL，对根执行RR，无需向上调整

• 若被删结点是黑色的左孩子（更加复杂）：删除后根结点右儿子LL，对根右儿子的右儿子LL，对根RR，对根右儿子RR

综上分析，我们只需要在BST的删除操作上增加如下调整即可实现AA树的删除：

LL(t);
if(t -> right != nullptr){
    LL(t -> right);
}
if(t -> right != nullptr && t -> right -> right != nullptr){
    LL(t -> right -> right);
}
RR(t);
if(t -> right != nullptr){
    RR(t -> right);
}
XL