C++实现红黑树应用实例代码

2024-07-29 14:55:40

红黑树的应用：

1、利用key_value对，快速查找，O(logn)

socket与客户端id之间，形成映射关系(socket, id)
内存分配管理
1. 一整块内存，不断分配小块
2. 每分配一次，就加入到红黑树
3. 释放的时候，在红黑树找到相应的块，然后去释放

2、利用红黑树中序遍历是顺序的特性

进程的调度
1. 进程处于等待状态，每个进程都有等待的时间，在未来某个时刻会运行，将这些进程利用红黑树组织起来
2. 在某个时刻，找到对应时刻的节点，然后中序遍历，就可以把该节点之前的节点全部运行到。

3、nginx定时器

为什么使用红黑树不使用哈希表？

极少情况下，需要key是有序的，如定时器

二叉排序树（bstree）

左子树 < 根 < 右子树
中序遍历结果是顺序的
极端情况下，如果顺序插入，结果就成了链表
1. 为了解决这个问题，引入了红黑树

红黑树性质

每个节点是红色的或黑色的
根节点是黑色的
叶子节点是黑色的
红色节点的两个子节点必须是黑色的
对每个节点，该节点到其子孙节点的所有路径上的包含相同数目的黑节点（黑高相同）
1. 最短路径就是全黑
2. 最长路径就是黑红相间

如何证明红黑树的正确性？

采用归纳法

左旋与右旋

改变三个方向，六根指针

红黑树的插入：

插入节点的时候，原先的树是满足红黑树性质的
插入节点的颜色是红色更容易满足红黑树的性质
插入的节点是红色，且其父节点也是红色的时候，需要调整

插入有三种情况：

叔父节点是红色
叔父节点是黑色，且祖父节点，父节点和插入节点不是一条直线
叔父节点是黑色，且祖父节点，父节点和插入节点是一条直线

平衡二叉树：

内部不是color，而是一个high记录高度，如果左右子树高度相差超过1，就需要调整。

红黑树的删除：

什么是删除节点? y-> y是z的后继节点
什么是轴心节点? x是y的右子树
1. 如果x是红色，把x变成黑色
2. 如果x是黑色，需要进行调整

删除y节点，是什么颜色的时候需要调整？

黑色需要调整，删除黑色破坏了黑高

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define RED                1
#define BLACK             2

typedef int KEY_TYPE;

typedef struct _rbtree_node {
    unsigned char color;
    struct _rbtree_node *right;
    struct _rbtree_node *left;
    struct _rbtree_node *parent;
    KEY_TYPE key;
    void *value;
} rbtree_node;

typedef struct _rbtree {
    rbtree_node *root;
    rbtree_node *nil;
} rbtree;

rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) {
    while (x->left != T->nil) {
        x = x->left;
    }
    return x;
}

rbtree_node *rbtree_maxi(rbtree *T, rbtree_node *x) {
    while (x->right != T->nil) {
        x = x->right;
    }
    return x;
}

rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x) {
    rbtree_node *y = x->parent;

    if (x->right != T->nil) {
        return rbtree_mini(T, x->right);
    }

    while ((y != T->nil) && (x == y->right)) {
        x = y;
        y = y->parent;
    }
    return y;
}

void rbtree_left_rotate(rbtree *T, rbtree_node *x) {

    rbtree_node *y = x->right;  // x  --> y  ,  y --> x,   right --> left,  left --> right

    x->right = y->left; //1 1
    if (y->left != T->nil) { //1 2
        y->left->parent = x;
    }

    y->parent = x->parent; //1 3
    if (x->parent == T->nil) { //1 4
        T->root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }

    y->left = x; //1 5
    x->parent = y; //1 6
}

void rbtree_right_rotate(rbtree *T, rbtree_node *y) {

    rbtree_node *x = y->left;

    y->left = x->right;
    if (x->right != T->nil) {
        x->right->parent = y;
    }

    x->parent = y->parent;
    if (y->parent == T->nil) {
        T->root = x;
    } else if (y == y->parent->right) {
        y->parent->right = x;
    } else {
        y->parent->left = x;
    }

    x->right = y;
    y->parent = x;
}

void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {

    while (z->parent->color == RED) { //z ---> RED
        if (z->parent == z->parent->parent->left) {
            rbtree_node *y = z->parent->parent->right;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;

                z = z->parent->parent; //z --> RED
            } else {

                if (z == z->parent->right) {
                    z = z->parent;
                    rbtree_left_rotate(T, z);
                }

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rbtree_right_rotate(T, z->parent->parent);
            }
        }else {
            rbtree_node *y = z->parent->parent->left;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;

                z = z->parent->parent; //z --> RED
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rbtree_right_rotate(T, z);
                }

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rbtree_left_rotate(T, z->parent->parent);
            }
        }

    }

    T->root->color = BLACK;
}

void rbtree_insert(rbtree *T, rbtree_node *z) {

    rbtree_node *y = T->nil;
    rbtree_node *x = T->root;

    while (x != T->nil) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else if (z->key > x->key) {
            x = x->right;
        } else { //Exist
            return ;
        }
    }

    z->parent = y;
    if (y == T->nil) {
        T->root = z;
    } else if (z->key < y->key) {
        y->left = z;
    } else {
        y->right = z;
    }

    z->left = T->nil;
    z->right = T->nil;
    z->color = RED;

    rbtree_insert_fixup(T, z);
}

void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {

    while ((x != T->root) && (x->color == BLACK)) {
        if (x == x->parent->left) {

            rbtree_node *w= x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;

                rbtree_left_rotate(T, x->parent);
                w = x->parent->right;
            }

            if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
                w->color = RED;
                x = x->parent;
            } else {

                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rbtree_right_rotate(T, w);
                    w = x->parent->right;
                }

                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                rbtree_left_rotate(T, x->parent);

                x = T->root;
            }

        } else {

            rbtree_node *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rbtree_right_rotate(T, x->parent);
                w = x->parent->left;
            }

            if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
                w->color = RED;
                x = x->parent;
            } else {

                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    rbtree_left_rotate(T, w);
                    w = x->parent->left;
                }

                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rbtree_right_rotate(T, x->parent);

                x = T->root;
            }

        }
    }

    x->color = BLACK;
}

rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) {

    rbtree_node *y = T->nil;
    rbtree_node *x = T->nil;

    if ((z->left == T->nil) || (z->right == T->nil)) {
        y = z;
    } else {
        y = rbtree_successor(T, z);
    }

    if (y->left != T->nil) {
        x = y->left;
    } else if (y->right != T->nil) {
        x = y->right;
    }

    x->parent = y->parent;
    if (y->parent == T->nil) {
        T->root = x;
    } else if (y == y->parent->left) {
        y->parent->left = x;
    } else {
        y->parent->right = x;
    }

    if (y != z) {
        z->key = y->key;
        z->value = y->value;
    }

    if (y->color == BLACK) {
        rbtree_delete_fixup(T, x);
    }

    return y;
}

rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) {

    rbtree_node *node = T->root;
    while (node != T->nil) {
        if (key < node->key) {
            node = node->left;
        } else if (key > node->key) {
            node = node->right;
        } else {
            return node;
        }
    }
    return T->nil;
}

void rbtree_traversal(rbtree *T, rbtree_node *node) {
    if (node != T->nil) {
        rbtree_traversal(T, node->left);
        printf("key:%d, color:%d\n", node->key, node->color);
        rbtree_traversal(T, node->right);
    }
}

int main() {

    int keyArray[20] = {24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15};

    rbtree *T = (rbtree *)malloc(sizeof(rbtree));
    if (T == NULL) {
        printf("malloc failed\n");
        return -1;
    }

    T->nil = (rbtree_node*)malloc(sizeof(rbtree_node));
    T->nil->color = BLACK;
    T->root = T->nil;

    rbtree_node *node = T->nil;
    int i = 0;
    for (i = 0;i < 20;i ++) {
        node = (rbtree_node*)malloc(sizeof(rbtree_node));
        node->key = keyArray[i];
        node->value = NULL;

        rbtree_insert(T, node);

    }

    rbtree_traversal(T, T->root);
    printf("----------------------------------------\n");

    for (i = 0;i < 20;i ++) {

        rbtree_node *node = rbtree_search(T, keyArray[i]);
        rbtree_node *cur = rbtree_delete(T, node);
        free(cur);

        rbtree_traversal(T, T->root);
        printf("----------------------------------------\n");
    }

}

总结

到此这篇关于C++实现红黑树的文章就介绍到这了,更多相关C++实现红黑树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C语言实现红黑树的实例代码

因为看内核的时候感觉红黑树挺有意思的,所以利用周末的时间来实现一下玩玩.红黑树的操作主要是插入和删除,而删除的时候需要考虑的情况更多一些.具体的操作就不在这里罗嗦了,百度文库里面有一个比较有好的文章,已经说的很明白了. 在看具体的操作的时候有的人可能感觉有些情况是没有考虑到的(如果没有这种感觉的人很有可能根本没有仔细地想).但是那些"遗漏"的情况如果存在的话,操作之前的红黑树将违反那几个规则. 写代码的时候很多次因为少考虑情况而导致错误,细节比较多,刚开始rb_node中没有指向父节点
C++实现红黑树应用实例代码

红黑树的应用: 1.利用key_value对,快速查找,O(logn) socket与客户端id之间,形成映射关系(socket, id) 内存分配管理一整块内存,不断分配小块每分配一次,就加入到红黑树释放的时候,在红黑树找到相应的块,然后去释放 2.利用红黑树中序遍历是顺序的特性进程的调度进程处于等待状态,每个进程都有等待的时间,在未来某个时刻会运行,将这些进程利用红黑树组织起来在某个时刻,找到对应时刻的节点,然后中序遍历,就可以把该节点之前的节点全部运行到. 3.nginx定时器
C语言实现红黑树详细步骤+代码

目录红黑树的概念红黑树的性质红黑树的定义与树结构插入新增结点插入后维护红黑树性质的主逻辑拆解讨论: 旋转验证红黑树与AVl树的比较红黑树的应用总结红黑树的概念红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的概念总结:红黑树是二叉搜索树的升级,结点里面存放的成员col标记当前结点的颜色,它的最长路径最多是最短
C语言实现手写Map(数组+链表+红黑树)的示例代码

目录要求结构红黑树和链表转换策略 hash 使用要求需要准备数组集合(List) 数据结构需要准备单向链表(Linked) 数据结构需要准备红黑树(Rbtree)数据结构需要准备红黑树和链表适配策略(文章内部提供,可以自行参考) 建议先去阅读我博客这篇文章C语言-手写Map(数组+链表)(全功能)有助于理解 hashmap使用红黑树的原因是: 当某个节点值过多的时候那么链表就会非常长,这样搜索的时候查询速度就是O(N) 线性查询了,为了避免这个问题我们使用了红黑树,当链表长度大于
C语言实现手写红黑树的示例代码

目录前沿红黑树代码测试前沿写C的红黑树前建议先看我博客这篇文章Java-红黑树主要看原理红黑树代码 #ifndef STUDY_RBTREE_H #define STUDY_RBTREE_H #include "charkvlinked.h" typedef int boolean;//定义一个布尔类型 #define TRUE 1 #define FALSE 0 enum COL{RED=0,BLACK=1}; typedef struct rBNode { char
PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】

本文实例讲述了PHP实现绘制二叉树图形显示功能.分享给大家供大家参考,具体如下: 前言: 最近老师布置了一个作业:理解并实现平衡二叉树和红黑树,本来老师是说用C#写的,但是我学的C#基本都还给老师了,怎么办?那就用现在最熟悉的语言PHP来写吧! 有一个问题来了,书上在讲解树的时候基本上会给出形象的树形图.但是当我们自己试着实现某种树,在调试.输出的时候确只能以字符的形式顺序地输出.这给调试等方面带来了很大的不便.然后在各种百度之后,我发现利用PHP实现二叉树的图形显示的资源几乎是零!好吧,那我就
Java数据结构之红黑树的真正理解

真正的帮助大家理解红黑树: 一.红黑树所处数据结构的位置: 在JDK源码中, 有treeMap和JDK8的HashMap都用到了红黑树去存储红黑树可以看成B树的一种: 从二叉树看,红黑树是一颗相对平衡的二叉树二叉树-->搜索二叉树-->平衡搜索二叉树--> 红黑树从N阶树看,红黑树就是一颗 2-3-4树 N阶树-->B(B-)树故我提取出了红黑树部分的源码,去说明红黑树的理解看之前,理解红黑树的几个特性,后面的操作都是为了让树符合红黑树的这几个特性,从而满足对查找效率的O
利用Java实现红黑树

目录 1.红黑树的属性 2.旋转 3.插入 4.删除 5.所有代码 6.演示 1.红黑树的属性红黑树是一种二分查找树,与普通的二分查找树不同的一点是,红黑树的每个节点都有一个颜色(color)属性.该属性的值要么是红色,要么是黑色. 通过限制从根到叶子的任何简单路径上的节点颜色,红黑树确保没有比任何其他路径长两倍的路径,从而使树近似平衡. 假设红黑树节点的属性有键(key).颜色(color).左子节点(left).右子节点(right),父节点(parent). 一棵红黑树必须满足下面有下面
java算法实现红黑树完整代码示例

红黑树定义红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组. 红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树: 红链接均为左链接:没有任何一个结点同时和两条红链接相连:该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同. 满足这样定义的红黑树和相应的2-3树是一一对应的. 旋转旋转又分为左旋和右旋.通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接.对比操作前后,可以看出,该操作
java中treemap和treeset实现红黑树

TreeMap 的实现就是红黑树数据结构,也就说是一棵自平衡的排序二叉树,这样就可以保证当需要快速检索指定节点. TreeSet 和 TreeMap 的关系为了让大家了解 TreeMap 和 TreeSet 之间的关系,下面先看 TreeSet 类的部分源代码: public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializab

C++实现红黑树应用实例代码

相关推荐

随机推荐