数据结构中的红黑树详细解析

2021-06-28  本文已影响0人  攻城狮Chova
Red-black_tree_example.svg.png

树

二叉搜索树

初始化

typedef struct TREENODE
{
    struct TREENODE *father;
    struct TREENODE *left;
    struct TREENODE *right;
    int value;
}tNode;

void insertNode(tNode* root, int val) {
    tNode* new = (tNode*)malloc(sizeof(tNode));
    new -> value = val;
    new -> left = NULL;
    new -> right = NULL;
    while (true) {
        if (root -> value < val)
            if (root -> right != NULL)
                root = root -> right;
            else {
                // 右子节点不存在,则新节点成为右子节点
                new -> father = root;
                root -> right = new;
                return;     // 完成赋值之后函数结束
            }
        else 
            if (root -> !=NULL)
                root = root -> left
            else {
                new -> father = root;
                root -> left = new;
                return;
            }
    }
}

// 打印二叉搜索树,输入的值为节点和节点序
void printBST(tNode* root, int start) {
    printf("the %dth node is %d\n",start, root -> value);
    // 如果当前节点有子节点,则继续打印这个子节点和节点序
    if (root -> left != NULL) 
        printBST(root -> left, start + 1);
    if (root -> right) 
        printBST(root -> right, start + 1)
}

int main() {
    tNode* root;
    root -> left = NULL;
    root -> right = NULL;
    root -> value = 10;

    int init[10] = {1, 11, 5, 12, 2, 4, 19, 11, 8, 7}
    for (int i = 0; i < 10; i ++)
        inserNode(root, init[i]);

    printBST(root, 0);
    return 0; 
}
在这里插入图片描述

查找节点

// 通过节点的值搜索节点的位置,其中root为根节点
tNode* searchBST(tNode* root, int val) {
    while (root -> value != val) {
        if (root -> value < val && root -> right != NULL)
            root = root -> right;
        else if (root -> value > val && root -> left != NULL)
            root = root -> left;
        else
            return FALSE;
    }
    return root;
}

删除节点

// 删除节点的值,root为根节点,delNode为待删除节点
void deleteNode(tNode* delNode) {
    if (delNode -> left == NULL && delNode -> right == NULL) {
        if (delNode -> value > pNode -> value)
            pNode -> right = NULL;
        else
            pNode -> left = NULL;
    }
    else if (delNode -> left == NULL && delNode -> right == NULL) {
        int val = delNode -> value;
        // 交换当前节点与右子节点的值
        delNode -> value = delNode -> right -> value;
        delNode -> right -> value = val;
        deleteNode(delNode -> right);   // 删除右节点
    }
    else {
        tNode* pNode = (delNode -> left == NULL) ? delNode -> right : delNode ->left;
        delNode -> value = pNode -> value;
        delNode -> right = pNode -> right;
        delNode -> left = pNode -> left;
    }
}

int main() {
    tNode* root;
    root -> left = NULL;
    root -> right = NULL;
    root -> value = 10;
    int init[10] = {1, 11, 5, 12, 2, 4, 19, 11, 8, 7}
    for (int i = 0; i < 10; i++)
        insertNode(root, init[i]);
    tNode* sNode = searchBST(root, 5);
    deleteNode(sNode);
    printBST(root, 0);
    return 0;
}
在这里插入图片描述

旋转节点

假设y是x的右子节点,而x的左子结点很少,y的右子节点很多,如果把y的子节点过继给x,或者取代x,逆转父子关系,就可以使得整个树变得均匀

  • x, y的转置过程和旋转类似,这个操作称之为旋转
  • 父节点变成子节点的左子节点叫做左旋,这样的逆过程叫做右旋
#define RIGHT 1
#define LEFT 0

// 二叉树的传统旋转节点操作
// flag为LEFT时为左旋,flag为RIGHT时为右旋
void rotNode(tNode* xNode, int flag) {
    tNode* yNode;
    if (flag == LEFT) {
        yNode == xNode -> right;
        xNode -> father -> right = yNode;   // y成为x父节点的右子节点
    } else {
        yNode == xNode -> left;
        xNode -> father -> left = yNode;     
    }   

    yNode -> father = xNode -> father;      // x的父节点成为y的父节点
    xNode -> father = yNode;                // y成为x的父节点

    if (flag == LEFT) {
        yNode -> left -> father = xNode;    // y的左子节点成为x的子节点
        xNode -> right = yNode -> left;
        yNode -> left = xNode;
    } else {
        yNode -> right -> father = xNode;
        xNode -> left = yNode -> right;
        yNode -> right = xNode;
    }
    
} 

int main() {
    tNode* root;
    root -> left = NULL;
    root -> right = NULL;
    root -> value = 10;
    int init[10] = {1, 11, 5, 12, 2, 4, 19, 11, 8, 7}
    for (int i = 0; i < 10; i++)
        insertNode(root, init[i]);
    tNode* sNode = searchBST(root, 5);
    rotNode(sNode, LEFT);
    printBST(root, 0);
    return 0;
}

// 替换意义上的旋转操作,sNode为子节点,pNode为父节点
void turnNode(tNode *sNode, tNode* pNode) {
    if (sNode == pNode -> right) {
        sNode -> left -> father = pNode;
        pNode -> right = sNode ->left;
        sNode -> left = pNode;
    } else {
        sNode -> right -> father = pNode;
        pNode -> left = sNode -> right;
        sNode -> right = pNode;
    }

    sNode -> father = pNode -> father;
    pNode -> father = sNode;
}

红黑树

调整节点

  • 让每个节点都包含辈分信息,设计让每一个家族的辈分相差不要太过悬殊
  • 这种方案存在的问题:
    • 如果改变一个父节点的辈分,那么这个父节点的所有子孙,都会受到影响
  • 需要找到某中共衡量树高的某个参数,并且使得这个参数易于保持
  • 由于树的节点数目并不固定,所以不同子孙所构成链表的长度必然不等
  • 不可能要求每个家族的最小辈分完全相等
  • 让每个家族在抽离一些特殊的子女后,达到的辈分相等
#define RED 0
#define BLACK 0
typedef struct rbNODE
{
    struct rbNODE* father;
    struct rbNODE* left;
    struct rbNODE* right;
    int value;
    int color;
}rbNODE;
  • 红黑树的两点要求:
    • 任意父节点到这个父节点最后一代子孙节点的所有简单路径中,黑色节点数目相同
    • 红色节点的左右子节点都是黑色节点
  • 第一点要求等价于:
    • 任何一个末代孙节点到根节点的简单路径中,黑色节点数目相同
    • 任何两个末代孙节点抵达任意一个相同父节点的简单路径中,黑色节点数目相同
  • 如果叔节点Q存在且为红色,则将父节点P和叔节点Q同时设为黑色,将祖父节点G设为红色,然后将指针指向祖父节点
  • 如果叔节点Q不存在或者为黑色:
    • 如果插入节点与父节点在同侧(插入节点为左节点,父节点也为左节点):
      • 将父节点P设为黑色,将祖父节点G设为红色,旋转P, G
    • 如果插入节点与父节点在异侧:
      • 旋转P和插入节点,然后将指针移向P,此时P与这个节点的父节点成为同侧节点
// 调整红黑树节点
void adjust(rbNode* node) {
    rbNode* pNode = node -> father; // 父节点
    rbNode* qNode;

    while (pNode -> color = RED) {
        int flag = pNode == pNode -> father -> left ? LEFT : RIGHT;
        qNode = flag == LEFT ? pNode -> father -> right : pNode -> father -> left;  // 叔节点
        // 如果叔节点存在且为红色
        if (qNode != NULL || qNode -> color == RED) {
            pNode -> color = BLACK;
            qNode -> color = BLACK;
            pNode -> father -> color = RED;
            node = pNode -> father;
            pNode = node -> father;
        } else {
            if (flag != (node == pNode -> left ? LEFT : RIGHT)) {
                turnRbNode(node, pNode);    // 此时插入节点与父节点在异侧
                node = pNode;
                pNode = node -> father;
            }
            // 执行上面的操作,插入节点和父节点变为同侧
            pNode -> color = BLACK;
            pNode -> father = RED;
            turnRbNode(pNode,pNode -> father);
        } 
    } 
}

插入节点

  • 红黑树的核心算法adjustRBT引用的旋转操作存在很大问题:
    • 默认在树中间进行操作,所涉及到的所有节点元素都不为null
    • 一旦涉及到根节点或者末代节点,会引起系统崩溃
    • 所以必须在变化之前进行节点判断
// 打印红黑树,显示节点的红黑特性
void printRBT(rbNode* root, int start) {
    printf("the %dth node : %d with %d\n", start, root -> value, root -> color);
    if (root -> left != NULL)
        printRBT(root -> left, start + 1);
    if (root -> right != NULL)
        printRBT(root -> right, start + 1);
}

    // 旋转红黑树的节点, sNode是被旋转的子节点
    // root为根节点,输出为旋转后的根节点
    rbNode* turnNode(rbNode* root, rbNode* sNode) {
        rbNode* pNode = sNode -> father;    // 被旋转的父节点
        if (sNode == pNode -> right) {      // sNode为右子节点
            if (sNode -> left != NULL) {
                sNode -> left -> father = pNode;    // sNode的左子节点过继给pNode
            pNode -> right = sNode -> left;     // pNode接收sNode的左子节点
            sNode -> left = pNode;      // pNode成为sNode的左子节点
            } else {
                if (sNode -> right != NULL)
                    sNode -> right -> father = pNode;
                    pNode -> left = sNode -> right;
                    sNode -> right = pNode;
            }
            sNode -> father = pNode -> father;
            pNode -> father = sNode;

            if (sNode -> father == NULL) 
                return sNode;
            if (pNode == pNode -> father -> right) 
                sNode -> father -> right = sNode;
            else
                sNode -> father -> left = sNode;
            return root;    
        }

        // 红黑树的插入算法
        rbNode* insertRbNode(rbNode* root, int val) {
            rbNode* new = (rbNode*)malloc(sizeof(rbNode));
            new -> val = value;
            new -> left = NULL, new -> right = NULL;
            new -> color = RED;

            rbNode* tmpRoot = root;     // 保护root节点数据
            rbNode* temp;
            while (temp = root -> value < val ? root -> right : root -> left, temp != NULL)
                root = temp;
            new -> father = root;
            if (root -> value < val)
                root -> right = new;
            else
                root -> left = new;
            return adjustRBT(tmpRoot, new);
        }

// 红黑树插入算法
int main() {
    rbNode* Root = {NULL, NULL, NULL, 11, 1};
    rbNode* root = &Root;
    int init[7] = {2, 14, 1, 7, 15, 5, 8}
    for (int i = 0; i < 7; i ++) {
        root = insertRbNode(root, init[i]);
    }
    root = insertRbNode(root, 4);
    printRBT(root, 0);
    return 0;
}

这里可以看出节点以及节点颜色的变化过程:


在这里插入图片描述

删除节点

// 红黑树查询, root为根节点,val为待查询值
// 返回值为节点的指针
rbNode* searchRBT(rbNode* root, int val) {
    if (root -> value == val) 
        return root;
    if (root -> value < val && root -> right != NULL)
        return searchRBT(root -> right, val);
    else if (root -> value > val && root -> left != NULL)
        return searchRBT(root -> left, val);
    else
        return false;
}

// 红黑树删除节点,输入为待删除的节点指针
void deleteRbNode(rbNode* dNode) {
    rbNode* pNode = dNode -> father;
    if (dNode -> left == NULL && dNode -> right == NULL) {
        if (dNode == pNode -> right)
            pNode -> right = NULL;
        else
            pNode -> left = NULL;
    } else {
        // 如果左子节点存在,则pNode为dNode的左子节点,否则为右子节点
        pNode = (dNode -> left == NULL) ? dNode -> right : dNode -> left;
        int val = dNode -> value;
        dNode -> value = pNode -> value;
        pNode -> value = val;
        deleteRbNode(pNode)
    }
}

// 主函数
int main() {
    rbNode Root = {NULL, NULL, NULL, 11, 1};
    rbNode* root = &Root;
    int init[10] = {2, 14, 1, 7, 15, 5, 8, 4, 13, 6}
    for (int i = 0; i < 10; i++) {
        root = insertRbNode(root, init[i]);
    }
    rbNode* delNode = searchRBT(root, 11);
    print(root, 0)
    deleteRbNode(delNode);
    printf("After delete node 11\n");
    printRBT(root, 0);
    return 0;
}

顺序统计树

while (temp = root -> value < val ? root -> right : root -> left, temp != NULL) {
    root -> size += 1;
    root = temp;
}

if (dNode -> left == NULL && dNode -> right == NULL) {
    if (dNode == pNode -> right)
        pNode -> right = NULL;
    else
        pNode -> left = NULL;
    while (pNode.size -= 1, pNode -> father != NULL) {
        pNode = pNode -> father;
    }
}

rbNode* searchRBTN(rbNode* root, int n) {
    int low = 0;    // 左开右闭
    int high = root -> size;
    if (n > high)
        return NULL;
    
    while (1) {
        // 左子节点存在并且size < n - low
        if (root -> left != NULL && root -> left -> size < n-low) {
            root = root -> left;
            high = low + root -> size;
        } else {
            root = root -> right;
            low = high - root -> size;
        }
        if (root -> right != NULL && root -> right -> size == high - root -> size)
            return root;
        if (root -> left != NULL && root -> left -> size == low + root -> size - 1)
            return root;
    }
}
上一篇下一篇

猜你喜欢

热点阅读