红黑树

红黑树源码分享

Posted on

本人开学后花了三天终于在昨天3.10(也是本人的阳历生日)完成了红黑树的实现

自认为没有bug……

不过感觉接口设计上不是很好,觉得得学习一下stl

源码在github上,点这里

上面那个是看思路自己意淫出来的,这里有个模仿STL的版本

但是没有改好。。还有几个error……

除此之外,特别想说一个知识点,就是在模板实现上,其声明和定义是不能卸载两个文件里的,因为在编译的时候,编译器就必须知道类的大小(好吧,其实我也解释不大来……

非要写在两个文件里的话,我只知道特化,当然,这不是很可取。

完。

红黑树

红黑树入门(2)——删除操作

Posted on

自从上一次写完红黑树入门已经过去一个多月了……当时天真的我觉得就算再难只要花个一个下午就可以把删除操作搞懂,然而………………

阅前须知

但是我现在在这里申明一点,其实红黑树的删除操作也算不上太难,有一点是因为分类情况太多了。而我迟迟没有理解的一个主要原因在于

我们讨论的删除节点并不是我们在红黑树删除操作中传入的删除的节点,而是被删除节点的替换节点

因为在二叉查找树的删除过程中,被删除的节点实际上会被一个前驱最大节点或者是后继最小节点来替代。
而我们在红黑树中,可以在替换节点的同时,替换节点的颜色改成删除节点的颜色,那么我们的修复目标一下子缩小到了几乎是最下面的子树层,并且对删除节点处的性质并没有任何改变。实在是妙极!

另外感谢这篇文章,我是通过这个博文学习的,并且图片也来自这个博客,写的很好,推荐。

正文

由前文所得,我们的删除操作可以分为两部分,一个是删除,一个是修复。
当然插入的时候也可以分为插入和修复两部分,而且很有条理性,但是插入太简单了,也没细说。

在这里仍然需要提一个大前提:在二叉查找树的删除操作中,对于替换节点,其实是有两个选择的,要么是左孩子一直向右走得到最大前驱,要么是右孩子一直向左走得到最小后继,这里我们统一讨论最小后继

符号化节点

  • D 表示要被删除的节点(其实是替换节点啦,在修复过程中我们视为删除节点)。即:取 Delete 的首字母
  • P 表示父节点。即:取 Parent 的首字母;
  • S 表示兄弟节点。即:取 Sibling的首字母;
  • U 表示叔伯节点。即:取Uncle的首字母;
  • G 表示祖父节点。即:取 Grandfather的首字母;
  • L 表示左树。即:取Left的首字母;
  • R 表示右树。即:取Right的首字母;
  • Nil表示叶子节点。即所谓的空节点;注意:红黑树中的叶子节点与其他树中所述说的叶子节点不是同一概念。而且红黑树中的叶子节点(即:Nil节点)永远是被定义为黑色的。

除此之外也会有一些组合表示,这里用的有 DR,删除节点的右孩子,SL,SR,兄弟节点的左右孩子。

分类总览

  1. D 为红色
  2. D 为黑色,DR为红色
  3. D 为黑色,DR为nil,S 为 红色
  4. D 为黑色,DR为nil,S 为 黑色,SL 为红色,SR颜色任意
  5. D 为黑色,DR为nil,S 为 黑色,SR 为红色,SL颜色任意
  6. D 为黑色,DR为nil,S 为 黑色,SL、SR都为黑;P为红色
  7. D 为黑色,DR为nil,S 为 黑色,SL、SR都为黑;P为黑色

而其中我把 第4种到第7种情况合并为 ** 第 D 种情况**:D 为黑色,DR为nil,S 为 黑色
这样归类的目的在于,第3种情况可以转化为第 D 种情况。

分类讨论

D 为红色

因为我们当前的替换节点是最小后继,所以这个替换节点是没有左孩子的,因此当前节点为根的子树黑高为 0 。从而可得,DR不是红色就是nil。
因此操作为直接将DR替换到 D 的位置即可。

D 为黑色,DR为红色

因为D的左子树的黑高为 0 ,所以DR的两个孩子节点必然为 nil 。
只需将DR替换到D的位置,并将DR染成黑色即可。原D子树的黑高也保持不变。

D 为黑色,DR为nil,S 为 红色

D子树的原黑高为1,删除后为0,而DR为nil,也就是说已经完全没有节点提供我们调整与修复了,所以我们只能去上一层P子树进行调整。
继续分类,可以分为S为红色,或者S为黑色,这里先讨论S为红色。
因为D子树的黑高为 1 ,那么S子树的黑高也同样为1。而S为红色,SL,SR必然为黑色,并且其子孙节点不会有黑色节点。另外,由于红黑树的性质,S为红色,那么P必然为黑色。
如图。

而我们对其的操作如下:

先对P子树进行左旋并交换S和P的颜色,如图。

但是这样操作之后实际上并没有平衡,看上图的P子树,其实DR是nil,而SL必然不是nil(上面有解释)。
但是实际上,这样操作之后也就进入了 第 D 种情况,也就是以下四种情况。

D 为黑色,DR为nil,S 为 黑色,SL 为红色,SR颜色任意

正如之前所说的,SL,SR要么是红色,要么是nil,因此SL与SR都是不影响黑高的。而假定SL为红色,为的是确保这个节点的存在性。

那么修复方法如下:

  1. 将S子树右旋
  2. 将SL染成与P一样的颜色 //为的是确保原子树黑高不变
  3. 将P染成黑色
  4. 将P子树左旋。

D 为黑色,DR为nil,S 为 黑色,SR 为红色,SL颜色任意

跟上一种情况类似,直接说修复方法:

  1. 将S染成P的颜色
  2. 将P染成黑色,SR染成黑色
  3. 对P子树左旋

D 为黑色,DR为nil,S 为 黑色,SL、SR都为黑;P为红色

SL与SR都为黑色,实际上他们都是nil(看到现在就别问我为什么了)
因为P为红色,那么原P子树的黑高为 1 ,只需要将S染成红色,P染成黑色即可。

D 为黑色,DR为nil,S 为 黑色,SL、SR都为黑;P为黑色

这是最麻烦的情况了,因为它的原P子树的黑高是 2 ,而现在的P子树只有两个节点,在这个P子树上操作是不可能达到 2 的黑高的。

怎么办呢,我们只能将S染红色,将P子树作为一个新的待平衡的点向上递归。
说起来简单,但我感觉实现起来有些困难。

红黑树

红黑树入门

Posted on

刚看完网易公开课上算法导论中的平衡搜索树,传送门,讲的真的炒鸡好,这里就稍微总结一下。
另一方面,视频是英文板书,在一些地方讲述有点慢,这时候就凸显了文章的优势了。

红黑树性质

红黑树的性质判定红黑树的充要条件,性质见下:

  1. 每个节点不是红色就是黑色。
  2. 根节点和叶子节点必须为黑色。
  3. 每个红色节点的父亲节点必须为黑色节点。
  4. 对于每个节点,在它到每一个子树的叶子节点的所有路径中,所经过的黑色节点数量相同。并定义这个数量为黑高(black height)。

补充一条推论,由性质3易得,一颗红黑树的红色节点不会超过总节点数的一半。
而对于第2条性质,我们一般会使最后指向的空节点染色成黑色即可。

红黑树的树高

先说结论,红黑树的树高 height 不会超过 2log_2{(n+1)},即 height \leq 2 log_2{(n+1)}

证明如下:
将所有红色节点合并到其父亲节点,同时使该节点的孩子节点也合并成为其父亲节点的孩子节点。
这时候我们会得到一棵特别的树,它也是一棵平衡搜索树,称为2-3-4树。(建议在纸上画画)

2-3-4树有如下两条性质:
1. 对于每个非叶子节点,它的孩子节点数量范围为[2,4]
2. 对于每个叶子节点,它的深度都相同。

我们设由红黑树所得的2-3-4树的树高为 h',其叶子节点的数量为 leaf_num。可得不等式

    \[2^{h'} \leq leaf\_num \leq 4^{h'}\]

进而推导出 h' \leq log_2{leaf\_num}

就剩下我们的leaf_num了,其实leaf_num和红黑树的叶子节点的数量是一样的,而一棵树的叶子节点的数量是这棵树的非叶子节点数量 + 1,这是显而易见的。而在我们的红黑树中,非叶子节点数量就是我们插入的元素数量 n
将其代入得h' \leq log_2{(n+1)}
最后再联系到我们最开始的目标,红黑树的树高height,因为我们只合并了红色节点,根据红黑树性质3的推论可得

    \[2height \geq h'\]

因此,height \leq 2log_2{(n+1)} 得证。

红黑树的查询

因为树高是在 log 级别,所以只要按照二叉搜索树的查找方法来即可。
复杂度上限为一个树高,即一个 log 。

红黑树的插入

省去引入与例子,直接讲解法。

首先插入时按照二叉搜索树的方法插入,将其染色为红色,这样不会影响树高,易修复,但可能会破坏性质3。

现在假设插入节点 x与其父亲节点p[x]都为红色,即破坏了性质3。

其修复步骤主要分2种情况,这里将之称为两个主要情况:
1. 父亲节点是祖父节点的左孩子
2. 父亲节点是祖父节点的右孩子

这两种主要情况下又分为三种次要情况,这里以上述主要情况1的条件下分类讨论:
1. 祖父节点的右孩子p[p[x]].right,即叔叔(uncle)节点也为红色。此时让父亲节点和叔叔节点都染色成黑色,祖父节点染色成红色,将当前节点变更到祖父节点,进入下一个循环。
2. 叔叔(uncle)节点为黑色,当前节点x为父亲节点p[x]的右孩子。此时将父亲节点左旋,使得进入情况3。
3. 叔叔(uncle)节点为黑色,当前节点x为父亲节点p[x]的左孩子。可由情况2旋转得来。此时将祖父节点右旋并重新染色。染色方案为,新的祖父节点为黑色,新的父亲节点和新的叔叔节点为红色。退出循环。

而对于主要情况2,只要对主要情况1的3种次要情况做类似操作即可,唯一不同的就是方向反一下。
即 “左”--> “右”,“右”--> “左”。

红黑树的删除

视频没讲,有点晚了,明天看,并且补上C++代码实现。

哈夫曼树

CodeForces 226 B Naughty Stone Piles

Posted on

遇到的第二道哈夫曼树,这个哈夫曼树有些特别,当你将两个结点组合的时候,你只需要付出权值较小的花费。
简单说,结点权值组合的时候并不会产生新的结点!!
这就可以完全摒弃优先队列,直接用数组实现以求更为高效。

上次意外地发现两个队友都不会哈夫曼树……真是惊了……

题意:
有几堆石头,要你将他们堆成一堆。两堆石头堆成一堆的花费是石头堆较小的石头数量。q个询问,每次询问限制一堆石头,被其他石头合并的次数。

思路:
这道题,若是转化成图来说就是一个k叉哈夫曼树,然而不会产生新结点,也就是说所有结点的权值和位置都已经可以直接求得了。
将他降序排序,每次将同一层的权值乘以他的深度就是该层的花费。

: 下表很容易爆 int 自己想想很容易想到……
然而RE了好几发……

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 5;
int n;
ll ans[maxn], sum[maxn], ary[maxn];

void solve(int q)
{
    ll dep = 1, idx = 1, nxt;
    ll tmp, res = 0, d = q;
    while (idx <= n) {
        nxt = idx + d <= n ? idx + d : n;
        tmp = sum[nxt] - sum[idx];
        res += tmp * dep;
        idx += d, dep++, d *= q;
    }
    printf("%lld ", ans[q] = res);
}

int main()
{
    int qn, q;
    scanf("%d", &n);
    range(i, 1, n) scanf("%lld", ary + i);
    sort(ary + 1, ary + 1 + n, greater<int>());
    range(i, 1, n) sum[i] = ary[i] + sum[i - 1];
    scanf("%d", &qn);
    while (qn--) {
        scanf("%d", &q);
        if (ans[q])
            printf("%lld ", ans[q]);
        else
            solve(q);
    }
    return 0;
}
Trie

Trie入门与模板

Posted on

简介

Trie ,又称前缀树或者是字典树,不仅在字符串的应用广泛,在数据结构中也有很多相应的题目,是数据结构中用空间兑换时间的典型。

下面是两个入门题

HDU 1251 统计难题

题意:
给定多个字符串,多个询问,问你以所询问字符串为前缀的字符串数量。

思路:
构造Trie,插入的时候打个顺便再对前缀计数即可。

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000005;
int ch[N][30], val[N], sz;

void insert(char *s) 
{
    int u = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int k = s[i] - 'a';
        if (!ch[u][k]) {
            memset(ch[sz], 0, sizeof(ch[sz]));
            val[sz] = 1;
            ch[u][k] = sz++;
        }
        else
            val[ch[u][k]]++;
        u = ch[u][k];
    }
}

int query(char *s) 
{
    int u = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int k = s[i] - 'a';
        if (!ch[u][k])
            return 0;
        u = ch[u][k];
    }
    return val[u];
}

int main() 
{
    char str[15];
    memset(ch[0], 0, sizeof(ch[0]));
    sz = 1;
    while (gets(str) && strlen(str) != 0)
        insert(str);
    while (scanf("%s", str) == 1)
        printf("%d\n", query(str));
    return 0;
}

HDU 1075 What Are You Talking About

题意:
给定字符串以及映射的字符串,再给定另几个字符串,让你把映射后的写出来。

思路:
大致的思路都是有的,构建Trie,再对每个单词进行查询。
但是!!!有非常非常多的坑!!!我觉得字符串的坑都这么多!!!
但是我写这篇博文实际上是我A题一周后了,具体哪些我也忘了……想知道,就看代码或者discuss吧。
真的是坑哭了…… 交了22发才A……

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 500010;
const int sigma_size = 27;

struct Trie {
    int ch[maxn][sigma_size];
    char trans[maxn][12];
    bool isEnd[maxn];
    int sz;
    Trie()
    {
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        isEnd[0] = false;
    }
    int getIdx(const char& c) { return c - 'a'; }

    void insert(char* s, char* tar)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                memset(ch[sz], 0, sizeof ch[sz]);
                isEnd[sz] = false;
                ch[u][idx] = sz++;
            }
            u = ch[u][idx];
        }
        memcpy(trans[u], tar, sizeof trans[u]);
        isEnd[u] = true;
    }

    void query(char* s)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                printf("%s", s);
                return;
            }
            u = ch[u][idx];
        }
        if (isEnd[u])
            printf("%s", trans[u]);
        else
            printf("%s", s);
    }
};

int main()
{
    Trie trie;
    char str[2][15];
    char buf[3005], ch;
    int id=0;
    scanf("%s", str[0]);
    while (scanf("%s", str[0]) && strcmp(str[0], "END") != 0) {
        scanf("%s", str[1]);
        trie.insert(str[1], str[0]);
    }
    scanf("%s", str[0]);
    getchar();
    while (scanf("%c", &ch)) {
        if (isalpha(ch))
            buf[id++] = ch;
        else {
            buf[id] = '\0';
            id = 0;
            if (strcmp(buf, "END") == 0)
                break;
            trie.query(buf);
            putchar(ch);
        }
    }
    return 0;
}

指针模板

query函数针对的是 hdu 1075

struct TrieNode {
    TrieNode* nxt[sigma_size];
    char* trans;
    char ch;
    bool isEnd;
    TrieNode()
    {
        trans = NULL;
        isEnd = false;
        memset(nxt, 0, sizeof ch);
    }
    ~TrieNode()
    {
        delete trans;
    }
};

struct Trie {
    TrieNode* root;
    Trie()
    {
        root = new TrieNode;
    }
    ~Trie()
    {
        freeTree(root);
    }
    int getIdx(const char& c) { return c - 'a'; }

    void insert(char* s, char* tar)
    {
        int len = strlen(s), idx;
        TrieNode *cur = root, *tmp;
        for (int i = 0; i < len; i++) {
            idx = getIdx(s[i]);
            if (cur->nxt[idx] == NULL) {
                tmp = new TrieNode;
                tmp->ch = s[i];
                cur->nxt[idx] = tmp;
            }
            cur = cur->nxt[idx];
        }
        cur->isEnd=true;
        cur->trans = new char[strlen(tar) + 2];
        memcpy((cur->trans), tar, strlen(tar) + 1);
    }

    void query(char* s)
    {
        int len = strlen(s), idx;
        TrieNode* cur = root;
        for (int i = 0; i < len; i++) {
            idx = getIdx(s[i]);
            if (cur->nxt[idx] == NULL) {
                printf("%s", s);
                return;
            }
            cur = cur->nxt[idx];
        }
        if (cur->isEnd)
            printf("%s", cur->trans);
        else
            printf("%s", s);
    }

    void freeTree(TrieNode* cur)
    {
        for (int i = 0; i < sigma_size; i++)
            if (cur->nxt[i])
                freeTree(cur->nxt[i]);
        delete cur;
    }
};

数组模板

query函数针对的是 hdu 1075

struct Trie {
    int ch[maxn][sigma_size];
    char trans[maxn][12];
    bool isEnd[maxn];
    int sz;
    Trie()
    {
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        isEnd[0] = false;
    }
    int getIdx(const char& c) { return c - 'a'; }

    void insert(char* s, char* tar)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                memset(ch[sz], 0, sizeof ch[sz]);
                isEnd[sz] = false;
                ch[u][idx] = sz++;
            }
            u = ch[u][idx];
        }
        memcpy(trans[u], tar, sizeof trans[u]);
        isEnd[u] = true;
    }

    void query(char* s)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                printf("%s", s);
                return;
            }
            u = ch[u][idx];
        }
        if (isEnd[u])
            printf("%s", trans[u]);
        else
            printf("%s", s);
    }
};
前缀和

Karen and Coffee 前缀和区间计数

Posted on

题源 codeforces Round 816 B

题意
简单说就是给你一个大区间,每次给你一条线段,给出后线段上所有数计数 +1
询问若干个区间,问区间内大于等于给定常数k的个数有多少?

思路
扫描线可写,但是无论是数状数组和线段树写起来都非常麻烦……
最简单的正解就是很久很久没用的前缀和累加计数

前缀和累加计数
每次给定一个区间[l,r],则ary[l]++,ary[r+1]--
最后扫一边,累加ary[i] 即得当前下标 i 的数值。
很好理解我就不解释了

ACcode

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>

using namespace std;

const int maxn = 2e5 + 5;

int n, k, q, l, r, tmp;
int ary[maxn];
int sum[maxn];

int main()
{
    scanf("%d %d %d", &n, &k, &q);
    while (n--) {
        scanf("%d %d", &l, &r);
        ary[l]++;
        ary[r + 1]--;
    }
    for (int i = 1; i < maxn; i++) {
        tmp += ary[i];
        sum[i] = tmp >= k ? sum[i - 1] + 1 : sum[i - 1];
    }
    while (q--) {
        scanf("%d %d", &l, &r);
        printf("%d\n", sum[r] - sum[l - 1]);
    }
    return 0;
}
二叉查找树

关于传参的两种方式 传值与传址 的深入理解 (附 hdu3999

Posted on

真的真的真的真的好久没码了………………

最近因为要复习数据结构所以才兴起想要码一些跟考试相关的

于是找了一下 BST 和 AVL 的题做做 结果一下搜就找到了 hdu3999

解法很简单 只要建立一个 BST 再对其先序遍历即可
然而…………

问题出在这个代码上

int main()
{
    int tmp;
    while(scanf("%d",&n)!=EOF)
    {
        root=NULL;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&tmp);
            InsertNode(root,tmp);
            if(root==NULL)
                cout<<1111<<endl;
        }
        FirstOrderSearch(root);
        puts("");
    }
    return 0;
}

插入函数如下

void InsertNode(node* now,int value)
{
    if(now==NULL)
    {
        now = new node;
        now -> value = value;
        return ;
    }
    else if(value < now -> value)
        InsertNode(now->left,value);
    else if(value > now -> value)
        InsertNode(now -> right, value);
}

咋看下真的没什么问题 然而实际上还是会输出n个 1111
这就说明 root 它一直都没有变化

“纳尼不是只要传地址 , 那么这个变量就一定会随之改变的不是么。。。”

想了一下才想通 传参在本质上来说完全只有一种方法 就是传值

传址传址 也只是把指针这个变量的值 给传了过去 而如果我们对这个地址取值那么自然而然的就可以改变这个变量的值

以这里的代码为例 我在主函数中的 root变量初始化为 NULL 传给 InsertNode 变量now拥有了 NULL 但是在这里now的所有变化将根本不会影响到main中的root

换言之 对于指针的传参 只有 *指针(指针所指的值)才会能在全局变化

所以如果要继续我以上的写法 解法有二:

  1. 只要将这个root 这个指针的地址传给函数处理即可
  2. 当然 我也可以在最开始的时候就先把根节点给定义了 再对根节点传参也可

综上

传参在本质上只有将实参的值传给形参 而所谓的传址 我们只能理解成一个小技巧 否则会带来很多习惯性误导

AC Code

法 1 :(因为第一次这么写 运算符的等级忘了 所以保险点就都加了括号…………)

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
int n;

struct node
{
    int value;
    node *left;
    node *right;
    node():left(NULL),right(NULL) {}
};

void InsertNode(node** now,int value)
{
    if(*now==NULL)
    {
        *now=new node;
        (*now)->value=value;
        return ;
    }
    if(value < (*now) -> value)
        InsertNode(&((*now)->left),value);
    else if(value > (*now) -> value)
        InsertNode(&((*now) -> right), value);
}

void FirstOrderSearch(node* now,node* root)
{
    if(now==root)
        printf("%d",now->value);
    else printf(" %d",now->value);
    if(now->left)
        FirstOrderSearch(now->left,root);
    if(now->right)
        FirstOrderSearch(now->right,root);
    delete now;
}

int main()
{
    int tmp;
    while(scanf("%d",&n)!=EOF)
    {
        node* root=NULL;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&tmp);
            InsertNode(&root,tmp);
        }
        FirstOrderSearch(root,root);
        puts("");
    }
    return 0;
}