沃梦达 / 编程技术 / 编程语言 / C/C++开发 / 正文

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

C/C++开发
2022-12-14

红黑树它一种特殊的二叉查找树,这意味着它满足二叉查找树的特征,但是也有许多自己的特性,这篇文章主要给大家介绍了关于C++实现红黑树的相关资料,需要的朋友可以参考下

红黑树的应用：

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

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

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

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

3、nginx定时器

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

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

二叉排序树（bstree）

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

红黑树性质

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

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

  • 采用归纳法

左旋与右旋

  • 改变三个方向，六根指针

红黑树的插入：

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

插入有三种情况：

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

平衡二叉树：

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

红黑树的删除：

  1. 什么是删除节点? y-> y是z的后继节点
  2. 什么是轴心节点? 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++实现红黑树应用实例代码

上一篇： C++构造函数的一些注意事项总结
下一篇： C/C++ 原生API实现线程池的方法

基础教程推荐

学习HTML
学习jQuery
学习Laravel
学习CSS3
学习Vue.js
学习Bootstrap5
学习ThinkPHP
学习AJAX
猜你喜欢
最新文章
热门文章
编程基础
热门标签
网站首页 HTML/CSS 菜单 Layui Yii2