Data-Structure18

Before：最近在看电影😋打算慢慢把一些经典的但是一直没抽空看的好片子看一遍。刚看完了Avatar，怎么说呢，票房不能说明一切吧（感觉全球票房前10可能只有Titanic和Avenger4确实高质量，个人观点勿喷）今天开始看了一部14年的经典奥斯卡获奖电影——《布达佩斯大饭店》，一直有朋友推荐我看，才看了一点，美学上极致的对称是我非常欣赏的，色调也很喜欢。

Data Structure 18 伸展树 散列表

伸展树的定义

伸展树也是一种二叉查找树。它支持二叉查找树的所有操作，但不需要维护平衡信息。因此，它不保证O(log N)的最坏情况下的时间性能。但从均摊的意义上看，它的时间性能还是对数的。

虽然平衡树对每个操作都提供了对数的最坏情况的运行时间的保证，但它们有一些限制。
(1)AVL的子树高度，红黑树的结点颜色，AA树的结点层次
(2)为保持平衡，插入删除操作非常复杂（11111😢😢😢）

其实可以有一个合理的折中：对单个访问的 O(N) 的时间是可接受的，只要不是经常发生。实际上，如果对于任何 M 个连续操作能够保证在最坏情况下的总时间为O(Mlog N)，那么均匀地分摊到序列中的每个操作的话，每个操作的时间是 O(log N) 的。这个运行时间被称为均摊的，即某些操作花的时间可能比对数要长，但能保证在序列中出现在它前面的某些执行时间较短的操作会给予补偿。

首先，在实际应用中，通常90％的访问都是针对 10％的数据。这个规则被称为90-10规则。通常只要保证这10％的数据能够快速访问。但平衡查找树没有利用这条规则的优势，它对所有的数据一视同仁。

Recall：BST的查找代价正比于深度，那么如果让一个经常被访问的数据元素靠近树根，将会节省以后查找这个元素的时间。将频繁访问的数据元素朝着根移动的最容易的方法，是连续地与它的父结点旋转，将该数据元素移得更接近根，该过程被称为向根旋转。但不幸的是，如果数据不满足90-10原则，而是雨露均沾，访问将会变得非常糟糕。

Recall Again：单旋转并不一定能使树的高度降低，但双旋转一定可以，所以我们考虑用双旋转，让元素不断靠近根，且整棵树的高度也在不断降低，我们将引入双旋转后的调整操作称作伸展操作。

伸展操作的实现

如果 X 是所要旋转的访问路径上的非根结点，根据 X 在树上的位置可以分成下列几种情况：（1）X的父结点是根结点（2）X是祖父结点的内部结点（3）X是祖父结点的外部结点让我们进行一个Case Analysis

情况一：X的父结点是根结点 —— zig情况

解决方案：一个单旋转如果是根结点的左孩子，进行一个LL，如果是根结点的右孩子，进行一个RR。

情况二：X是祖父结点的内部结点 —— zig-zag情况

解决方案：一个双旋转 LR or RL（与AVL中完全相同）
Result：高度降低！Win!

情况三：X是祖父结点的外部结点 —— zig-zig情况

解决方案：设X的父结点为P，祖父结点为G，现在P和G之间进行一次旋转，然后在X和P之间进行一次旋转。
Result：高度降低！Win!

伸展树总结

对伸展树的分析很困难，因为树的结构经常变化，但伸展树的编程要比 AVL 树和红黑树简单得多，几乎和 AA 树一样简单。（是的确实简单，但也和AA树一样无法证明为何需要这么做，就很神秘了）如果访问的模式是非随机的，伸展树似乎更好。非随机访问包括那些遵循 90-10 规则的情况以及一些特殊的情况，如顺序访问，双向访问和在某些事件模拟中的优先级队列等经典的具有明确的访问模式的访问。当访问序列是随机的且均匀分布时，伸展树没有其他的平衡树好。

散列表定义

在BST中，查找一个元素需要一系列的比较，查找的效率取决千查找过程中的比较次数。散列表提供了一种完全不同的存储和查找方法：通过将关键字值直接映射到表中的某个位置，将该关键字对应的数据元素存储在这个位置中。查找时，可以直接根据被查找的关键字值找到存储该数据元素的地址，从而获得这个数据元素。真的可以O(1)嘛？

尽管关键字的变化范围很大，例如可能达到 40 亿，但一个集合中并不一定有那么多的数据元素。如果为这个集合准备了一个 40 亿个元素的数组，数组中的很多单元都将为空，这样会造成大址的空间浪费。散列表的思想是用一个比集合规模略大的数组来存储这个集合，将数据元素关键字映射到这个数组的下标。这个映射称为散列函数。

散列函数的应用带来了一个复杂的问题：因为散列函数的定义域的范围比值域大，两个或更多的不同数据元素可能被映射到同一个位置，这种情况称为 冲突或碰撞。这种情况是不可避免的。因此，实现散列表的两个最基本的问题是，如何设计散列函数，以及如何解决碰撞。

散列函数

  1. 直接定址法设关键字值为x，那么其散列地址为H(x) = x或H(x) = ax + b(a,b为常数)

  2. 除留余数法如果M是散列表的大小，关键字为x的数据元素的散列地址为：
    H(x) = x mod M
    显然如果M选取不当，会造成大量碰撞和空间的浪费。经验表明，选取M为素数时，散列函数的函数值的分布会比较均匀。

  3. 数字分析法在某些应用中，关键字之间的区别集中在某些位上面。比如IP地址由网络号和主机号两个部分组成。如果在某个网络中要将自己的子网中的所有主机的信息管理起来，可以将 IP 地址作为关键字，如果采用散列的方法来保存这个集合，可以选择选取 IP 地址的主机号部分作为存储地址。

分析关键字中的每一位数字的分布规律，并从中提取出分布均匀的若干位或它们的组合作为地址。

  1. 平方取中法如果关键字中各位的分布都比较均匀，但关键字的值域比数组规模大，则可以将关键字平方后，取其结果的中间各位作为散列函数值。

  2. 折叠法如果关键字相当长，以至于和散列表的单元总数相比大得多时，可采用此法。如果数字的分布大体上是均匀的，通常的做法是选取一个长度后，将关键字按此长度分组相加。

碰撞的解决

哈希冲突不可避免常用的解决哈希冲突的办法有2种：（1）将溢出数据元素存放到散列表中没有使用过的单元中去。此方法是封闭式的，不再使用额外的单元。因此称为闭散列表。（2）将映射到同一地址的数据元素组织成一个线性表（通常采用链表的方式）。散列表本身仅保存一个指向各自链表中第一个结点的指针。这种方式的空间是开放式的，因此被称为开散列表，也称为拉链法。

线性探测法

最简单可行，首先找到该数组中散列到的位置，接着开始顺序搜索，直到发现一个空位置。只要数组够大，总能找到一个空单元。操作上，find和insert几乎是走一样的路径，但删除操作则稍有区别。如果物理意义上删除，将会导致find、insert操作出现错误，所以我们采用迟删除，即将这些元素标记为删除而不是物理地从表中删除（增加一个字段）。

代码实现较容易，不做实现了（太懒了😅）

二次探测法

在线性探测法中，碰撞会引起连锁反应，使表中形成一些较长的连续被占单元，从而使散列表的性能下降。这些连续被占的单元称为初始聚集。初始聚集越长，insert、find操作耗时就长，性能就差。消除初始聚集的一种方法是二次聚集法。

二次探测法也是一个碰撞解决方法。当发生碰撞时，它不是直接检查下一单元而是检查远离初始探测点的某一单元来消除线性探测中的初始聚集的问题。

当散列函数计算出 H 的值，并且搜索单元 H 没有成功，将依次尝试单元H + $1^2$，H + $2^2$，H + $3^2$，…，H + $i^2$(包括回绕)，这样不太容易产生连续被占单元，使得数据相对分布均匀。

下证明一个定理：如果采用二次探测法，并且表的大小是一个素数，那么，如果表至少有一半空单元，新的元素总能被插入。而且，在插入过程中，没有一个单元被探测两次。
PF：只要说明前[M/2]个替换单元是不同的，就证明了该定理。我们采用反证：不妨设这些单元中的某2个单元是H + $i^2$(mod M) 和 H + $j^2$(mod M)，其中，0 $\leq$ i,j $\leq$ [M/2] ，i $\neq$ j.
那么：

H + $i^2$ $\equiv$ H + $j^2$(mod M)

$i^2$ $\equiv$ $j^2$(mod M)

$i^2$ - $j^2$ $\equiv$ 0(mod M)

(i - j)(i + j) $\equiv$ 0(mod M)

Since i $\neq$ j , i + j $<$ M, Contradict!

QED.

再证一个定理：不需要昂贵的乘法和除法就能实现二次探测法。设$H_{i-1}$是最近计算到的探测点，$H_i$是要计算的新的探测点，那么可以有：
$H_i$ = $H_0$ + $i^2$(mod M)

$H_{i - 1}$ = $H_0$ + $(i - 1)^2$(mod M)

两式相减，得到：
$H_i$ = $H_{i - 1}$ + 2i - 1(mod M)

所以不需要对i进行平方计算就能得到新的H_i的值。

最后一个要考虑的问题是动态扩展。在二次探测法中，必须保持数组中有一半单元是空的。如果负载因子超过了 0.5 ，需要将数组扩大一倍。

再散列法

2个散列函数：H1(x),H2(x)
探测序列为：H1(x)(mod M),(H1(x) + H2(x))(mod M),(H1(x) + 2H2(x))(mod M)…

开散列表

将具有同一散列地址的元素都存储在一个单链表中，散列表的k号单元保存。

首先，作为一只程序设计学的不咋样的鼠鼠，我先来回忆一下函数指针！

  • 函数指针是指向函数的指针变量。

  • 通常我们说的指针变量是指向一个整型、字符型或数组等变量，而函数指针是指向函数。

  • 函数指针可以像一般函数一样，用于调用函数、传递参数。

函数指针的声明语法：

1
返回类型 (*指针变量名)(参数列表);

For example:

1
int (*funcPtr)(int, int);  // 声明一个指向函数的指针，该函数接受两个int参数并返回int

接着，作为一只程序设计学的不咋样的鼠鼠，我再来回忆一下静态成员函数！

  • 静态成员函数只能访问对应类内部的静态数据成员。

  • 不依赖于类的实例，可以直接通过类名调用（如 ClassName::staticFunc()）

  • 没有this指针

《开始》《手搓》

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
template<class KEY,class OTHER>
class openHashTable:public dynamicSearchTable<KEY,OTHER> {
private:
    struct node {
        SET<KEY,OTHER> data;
        node *next;
        node(SET<KEY,OTHER> d,node *n = nullptr):data(d),next(n){}
        node():next(nullptr){}
    };

    node **array;
    int Size;
    int (*key)(const KEY &x);  // 函数指针成员变量
    static int defaultKey(const int &x) { return x; }  // 静态成员函数

public:
    openHashTable(int s = 101,int (*f)(const KEY &x));
    ~openHashTable();
    SET<KEY,OTHER>*find(const KEY &x)const;
    void insert(const SET<KEY,OTHER> &x);
    void remove(const KEY &x);
};

template<class KEY,class OTHER>
openHashTable<KEY,OTHER>::openHashTable(int s ,int (*f)(const KEY &x)) {
    Size = s;
    array = new node*[Size];
    key = f;
    for(int i = 0;i < Size;i ++) {
        array[i] = nullptr;
    }
}

template<class KEY,class OTHER>
openHashTable<KEY,OTHER>::~openHashTable() {
    for(int i = 0;i < Size;i ++) {
        node *p = array[i];
        while(p != nullptr) {
            node *q = p -> next;
            delete p;
            p = q;
        }
    }
    delete []array;
}

template<class KEY, class OTHER>
SET<KEY, OTHER> *openHashTable<KEY, OTHER>::find(const KEY &x) const {
    int pos;
    pos = key(x)%Size;
    node *p = array[pos];
    while(p != nullptr) {
        if(p -> data.KEY == x) {
            break;
        }
    }
    return p -> data;
}

template<class KEY, class OTHER>
void openHashTable<KEY, OTHER>::insert(const SET<KEY, OTHER> &x) {
    int pos;
    pos = key(x.KEY)%Size;
    /*node *p = array[pos];
    if(p == nullptr) {
        array[pos] = new node(x,nullptr);
    }else {
        while(p -> next!= nullptr) {
            p = p -> next;
        }
        p -> next = new node(x,nullptr);
    }
    */
    //事实上你会发现，这种插入方法是自己给自己上复杂度
    //所以我们更应该进行
    array[pos] = new node(x,array[pos]);
}

template<class KEY, class OTHER>
void openHashTable<KEY, OTHER>::remove(const KEY &x) {
    int pos;
    pos = key(x)%Size;
    node *p = array[pos];
    if(p -> next == nullptr) {
        delete p;
        array[pos] = nullptr;
    }else {
        if(p -> data.KEY == x) {
            array[pos] = p -> next;
            delete p;
        }else {
            while(p -> next != nullptr) {
                if(p -> next -> data.KEY == x) {
                    p -> next = p -> next -> next;
                    delete p -> next;
                    break;
                }else {
                    p = p -> next;
                }
            }
        }
    }
}

STL中的动态查找表

STL中的动态查找表——关联容器，最基本的2个关键容器是set和map。set中的数据元素仅能包括一个字段，就是数据元素的关键字，它能有效地支待关于某个关键字是否存在的查询。map 的数据元素以（关键字，值）对的形式组织，如本书定义的集合元素类型。关键字用作为 map 中的索引，值表示所存储和读取的数据。

STL中采用红黑树实现（苯人其实认为AVL树并不比RBT慢，如果对这一点感兴趣可以参考这个repo）

在此感谢小狗@zcychar发现的这个repo
🥰🥰🥰

Data Structure
#Data Structure #C++
Data-Structure18
http://example.com/2025/03/23/Data-Structure18/
Author
Yihan Zhu
Posted on
March 23, 2025
Updated on
March 30, 2025
Licensed under