精华内容
下载资源
问答
  • RBTree

    2020-10-03 00:22:28
    按照RR红的情况处理 代码 RBTree.java /* * 1.创建RBTree,定义颜色 * 2.创建RBNode * 3.辅助方法定义 parentOf(node), isRed(node), setRed(node), setBlack(node), inorderPrint(node) * 4.左旋方法 leftRotate...

    二叉查找树

    情况1

    在这里插入图片描述
    此时查找的时间复杂度为 O(logn)

    情况2

    在这里插入图片描述
    此时查找的时间复杂度为 O(n), 不符合二叉查找树的设计的初衷。所以引出了平衡二叉树,左右子树高度差不超过1,可以避免出现线性结构的情况,但是还不够理想。
    为什么有了AVL树还会有红黑树

    因为AVL树要求左右子树高度差不超过1,这个要求太严格 ,导致插入、删除时
    ,很大几率破坏高度差为1的规则,进而需要通过左旋、右旋来调整,导致性能大打折扣。
    为了解决这个问题,就出现了红黑树。
    

    红黑树

    底层数据结构就是一个特殊的二叉查找树
    特征

    • 每个节点不是黑色就是红色
    • 不可能有连在一起的红色节点
    • 根节点都是黑色
    • 每个红色节点的两个子节点都是黑色,叶子节点都是黑色的
    • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

    为了满足红黑树的性质,有三种操作

    1. 改变颜色
    2. 左旋
    3. 右旋

    插入

    插入节点必须为红色, 保证不破坏黑色数量平衡
    

    情景1, 为空树

    插入节点为根节点,并设置为黑色
    

    情景2, 插入节点的key已存在

    更新节点
    

    情景3: 插入节点的父节点为黑色

    直接插入
    

    情景4: 插入节点的父节点为红色

    根据红黑树性质,既然父节点为红色 ,则爷爷节点必为黑色 
    

    情景4.1: U存在且U为红色

    1. P和U改为黑色
    2. PP改为红色
    3. 将PP设置为当前节点,进行后续处理
    

    情景4.2: U不存在或为黑色 ,插入节点的P是PP的左子节点

    情景4.2.1: currnet为P的左子节点(LL红)
    1.P设为黑色 ,PP为红色
    2.对PP右旋
    

    在这里插入图片描述

    情景4.2.2: currnet为P的右子节点(LR红)
    1.对P左旋
    2.P设为current,得到LL红情况
    3.按照LL红的情况处理
    

    在这里插入图片描述

    情景4.3: U不存在或为黑色 ,插入节点的P是PP的右子节点

    在这里插入图片描述

    情景4.3.1: currnet为P的右子节点(RR红)
    1.P设为黑色 ,PP为红色
    2.对PP左旋
    

    在这里插入图片描述

    情景4.3.2: currnet为P的左子节点(RL红)
    1.对P右旋
    2.P设为current,得到RR红情况
    3.按照RR红的情况处理
    

    在这里插入图片描述

    代码

    RBTree.java
    
    /*
     * 1.创建RBTree,定义颜色
     * 2.创建RBNode
     * 3.辅助方法定义 parentOf(node), isRed(node), setRed(node), setBlack(node), inorderPrint(node)
     * 4.左旋方法 leftRotate(node)
     * 5.右旋方法 rightRotate(node)
     * 6.公开插入接口 insert(K key, V value)
     * 7.内部插入接口 insert(RBNode node)
     * 8.修正平衡术插入导致的失衡 insertFixUp(RBNode)
     * 9.测试正确性
     */
    public class RBTree<K extends Comparable<K>, V> {
        private final static boolean RED = true;
        private final static boolean BLACK = false;
        private RBNode root = null;
    
        public RBNode getRoot() {
            return root;
        }
    
        private RBNode parentOf(RBNode node) {
            if (node != null) {
                return node.parent;
            }
            return null;
        }
    
        private boolean isRed(RBNode node) {
            if (node != null) {
                return node.color == RED;
            }
            return false;
        }
    
        private boolean isBlack(RBNode node) {
            if (node != null) {
                return node.color == BLACK;
            }
            return false;
        }
    
        private void setRed(RBNode node) {
            if (node != null) {
                node.color = RED;
            }
        }
    
        private void setBlack(RBNode node) {
            if (node != null) {
                node.color = BLACK;
            }
        }
    
        public void inorderPrint(RBNode node) {
            if (node != null) {
                inorderPrint(node.left);
                System.out.println("Key: " + node.key + ", value:" + node.value);
                inorderPrint(node.right);
            }
        }
    
        private void leftRotate(RBNode x) {
            RBNode y = x.right;
            x.right = y.left;
            if (y.left != null) {
                y.parent = x;
            }
            y.parent = x.parent;
            if (y.parent == null) {
                root = y;
            } else {
                if (x == x.parent.left) {
                    x.parent.left = y;
                } else {
                    x.parent.right = y;
                }
            }
            y.left = x;
            x.parent = y;
        }
    
        private void rightRotate(RBNode y) {
            RBNode x = y.left;
            y.left = x.right;
            if (x.right != null) {
                x.right.parent = y;
            }
            x.parent = y.parent;
            if (x.parent == null) {
                root = x;
            } else {
                if (y == y.parent.left) {
                    y.parent.left = x;
                } else {
                    y.parent.right = x;
                }
            }
            x.right = y;
            y.parent = x;
        }
    
        public void insert(K key, V value) {
            RBNode node = new RBNode();
            node.setValue(value);
            node.setKey(key);
            node.setColor(RED);
            insert(node);
        }
    
        private void insert(RBNode node) {
            // 查找当前node父节点
            RBNode parent = null;
            RBNode x = this.root;
            while (x != null) {
                parent = x;
                int cmp = node.key.compareTo(x.key);
                if (cmp < 0) {
                    x = x.left;
                } else if (cmp > 0) {
                    x = x.right;
                } else {
                    x.setValue(node.value);
                    return;
                }
            }
            node.parent = parent;
            if (parent != null) {
                int cmp = node.key.compareTo(parent.key);
                if (cmp < 0) {
                    parent.left = node;
                } else {
                    parent.right = node;
                }
            } else {
                this.root = node;
            }
            insertFixUp(node);
        }
    
        private void insertFixUp(RBNode node) {
            this.root.setColor(BLACK);
            RBNode parent = parentOf(node);
            RBNode gParent = parentOf(parent);
            if (parent != null && isRed(parent)) {
                RBNode uncle = null;
                if (parent == gParent.left) { // P是PP的左子节点
                    uncle = gParent.right;
                    // 4.1 U存在且U为红色
                    if (uncle != null && isRed(uncle)) {
                        //1. P和U改为黑色
                        //2. PP改为红色
                        //3. 将PP设置为当前节点,进行后续处理
                        setBlack(parent);
                        setBlack(uncle);
                        setRed(gParent);
                        insertFixUp(gParent);
                        return;
                    }
                    // 情景4.2: U不存在或为黑色
                    if (uncle == null || isBlack(uncle)) {
                        // 情景4.2.1: currnet为P的左子节点(LL红)
                        //1.P设为黑色 ,PP为红色
                        //2.对PP右旋
                        if (node == parent.left) {
                            setBlack(parent);
                            setRed(gParent);
                            rightRotate(gParent);
                            return;
                        }
                        // 情景4.2.2: currnet为P的右子节点(LR红)
                        //1.对P左旋
                        //2.P设为current,得到LL红情况
                        //3.按照LL红的情况处理
                        if (node == parent.right) {
                            leftRotate(parent);
                            insertFixUp(parent);
                            return;
                        }
                    }
    
                } else { // 插入节点的P是PP的右子节点
                    uncle = gParent.left;
                    // 4.1 U存在且U为红色
                    if (uncle != null && isRed(uncle)) {
                        //1. P和U改为黑色
                        //2. PP改为红色
                        //3. 将PP设置为当前节点,进行后续处理
                        setBlack(parent);
                        setBlack(uncle);
                        setRed(gParent);
                        insertFixUp(gParent);
                        return;
                    }
                    //  U不存在或为黑色
                    if (uncle == null || isBlack(uncle)) {
                        //情景4.3.1: currnet为P的右子节点(RR红)
                        //1.P设为黑色 ,PP为红色
                        //2.对PP左旋
                        if (node == parent.right) {
                            setBlack(parent);
                            setRed(gParent);
                            leftRotate(gParent);
                            return;
                        }
                        //情景4.3.2: currnet为P的左子节点(RL红)
                        //1.对P右旋
                        //2.P设为current,得到RR红情况
                        //3.按照RR红的情况处理
                        if (node == parent.left) {
                            rightRotate(parent);
                            insertFixUp(parent);
                            return;
                        }
                    }
                }
    
            }
        }
    
        static class RBNode<K extends Comparable<K>, V> {
            private RBNode parent;
            private RBNode left;
            private RBNode right;
            private boolean color;
            private K key;
            private V value;
    
            public RBNode() {
            }
    
            public RBNode(RBNode parent, RBNode left, RBNode right, K key, V value) {
                this.parent = parent;
                this.left = left;
                this.right = right;
                this.key = key;
                this.value = value;
            }
    
            public RBNode getParent() {
                return parent;
            }
    
            public void setParent(RBNode parent) {
                this.parent = parent;
            }
    
            public RBNode getLeft() {
                return left;
            }
    
            public void setLeft(RBNode left) {
                this.left = left;
            }
    
            public RBNode getRight() {
                return right;
            }
    
            public void setRight(RBNode right) {
                this.right = right;
            }
    
            public K getKey() {
                return key;
            }
    
            public void setKey(K key) {
                this.key = key;
            }
    
            public V getValue() {
                return value;
            }
    
            public void setValue(V value) {
                this.value = value;
            }
    
            public boolean getColor() {
                return this.color;
            }
    
            public boolean isColor() {
                return color;
            }
    
            public void setColor(boolean color) {
                this.color = color;
            }
        }
    }
    
    TreeOperation.java
    
    // TreeOperation.java
    public class TreeOperation {
        /*
             Example of the structure of the tree:
                  1
                /   \
              2       3
             / \     / \
            4   5   6   7
        */
    
        // the number of layers used to get the tree
        public static int getTreeDepth(RBTree.RBNode root) {
            return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
        }
    
    
        private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
            // Ensure that the input tree is not empty
            if (currNode == null) return;
            // First save the current node to a two-dimensional array
            res[rowIndex][columnIndex] = String.valueOf(currNode.getKey()) +  "-" + (currNode.isColor() ? "R": "B" ) + "";
    
            // Calculate the current layer in the tree
            int currLevel = ((rowIndex + 1) / 2);
            // If it reaches the last level, it will return
            if (currLevel == treeDepth) return;
            // Calculate the interval between each element from the current line to the next line (the interval between the column index of the next line and the column index of the current element)
            int gap = treeDepth - currLevel - 1;
    
            // judge the left son, if there is a left son, record the corresponding "/" and the value of the left son
            if (currNode.getLeft() != null) {
                res[rowIndex + 1][columnIndex - gap] = "/";
                writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
            }
    
            // Make a judgment on the right son. If there is a right son, record the value of the corresponding "\" and the right son.
            if (currNode.getRight() != null) {
                res[rowIndex + 1][columnIndex + gap] = "\\";
                writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
            }
        }
    
    
        public static void show(RBTree.RBNode root) {
            if (root == null) System.out.println("EMPTY!");
            // Get the depth of the tree
            int treeDepth = getTreeDepth(root);
    
            // The width of the last line is 2 (n - 1) and the power is 3, plus 1
            // as the width of the entire two-dimensional array
            int arrayHeight = treeDepth * 2 - 1;
            int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
            // Use an array of strings to store the elements that should be displayed at each location
            String[][] res = new String[arrayHeight][arrayWidth];
            // Initialize the array, the default is a space
            for (int i = 0; i < arrayHeight; i ++) {
                for (int j = 0; j < arrayWidth; j ++) {
                    res[i][j] = " ";
                }
            }
    
            // Recursive processing of the entire tree from the root node
            // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
            writeArray(root, 0, arrayWidth/ 2, res, treeDepth);
    
            // At this point, all the elements that need to be displayed have been stored in a two-dimensional array, spliced ​​and printed.
            for (String[] line: res) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < line.length; i ++) {
                    sb.append(line[i]);
                    if (line[i].length() > 1 && i <= line.length - 1) {
                        i += line[i].length() > 4 ? 2: line[i].length() - 1;
                    }
                }
                System.out.println(sb.toString());
            }
        }
    }
    
    
    MyTest,java
    
    import java.util.Scanner;
    
    public class MyTest {
    
        public static void main(String[] args) throws Exception {
            Scanner scanner = new Scanner(System.in);
            RBTree<Integer, Object> rbt = new RBTree();
            while (true) {
                System.out.println("Please input key");
                String key = scanner.next();
                rbt.insert(new Integer(key), null);
                TreeOperation.show(rbt.getRoot());
            }
        }
    }
    

    在这里插入图片描述

    展开全文
  • 红黑树rbTree.c

    2020-05-12 10:12:04
    红黑树的遍历,查找过程,以及插入时对红黑树进行位置修复,修复包括左旋右旋,还有就是红黑树节点的删除,删除之后还要对节点修复
  • Linux 内核中提供了一个通用红黑树的实现(位于文件rbtree.h、rbtree.c和rbtree.txt),这里是ubuntu内核5.2.2版本的源码,用于算法研究和移植使用。
  • rbtree.tar.bz2

    2019-06-11 14:20:41
    Linux内核源码下的红黑树源码,进行封装处理,可以调用使用,在我的工作项目已经使用,没有什么问题,欢迎下载
  • rbtree

    2021-11-23 09:51:14
    // 3.2 } void rbtree_insert_fixup(rbtree *T, rbtree_node *z) { // if (z->parent->color == RED) { while (z->parent->color == RED) { if (z->parent == z->parent->parent->left) { rbtree_node *y = z->...

    为什么会有红黑树?

    是因为二叉查找树,最差的情况会退化成链表。查找效率就成了O(n)

    为了保证二叉查找树的查找效率,需要保持二叉树的平衡,引出了平衡二叉树,但是完全平衡的二叉查找树实现复杂,每个节点都需要维护一个高度。所以出现了红黑树,它是利用黑高来保持平衡。

    红黑树的定义

    1. 是一个二叉查找树;
    2. 每个节点都是黑色或者红色;
    1. 根节点是黑色的;
    2. 每个叶子节点是黑色的;
    1. 如果一个节点是红色的,那么它的两个儿子必须是黑色的;
    2. 从一个节点出发,到任意一个叶子节点,包含相同数目的黑色节点。

    红黑树的使用场景

    对于红黑树的使用,主要是基于它的两个特点:

    1. 查找效率O(logn), 适合用于key->value的查找;
    2. 中序遍历是顺序的。

    红黑树典型应用:

    1. map, 利用了特点1,将key作为索引存入红黑树,通过key可以查找到value。
    2. nginx中用于定时器等,利用特点2,将定时任务到期的timestamp存入红黑树,通过中序遍历,查找到红黑树中最小的节点,即最近要到期的定时任务。
    1. cfs(Completely Fair Scheduler, 完全公平调度),利用特点2,将进程调度的时间存入红黑树,查找到最小的节点,即调度时间最短的进程,进行调度,可以做到公平调度。
    2. 内存管理,利用特点1,可以快速查找到对应的内存块。

    内存管理的红黑树的key是内存首地址?

    一个内存块的表述方法:

    a. 首地址 + 长度

    b. 首地址 + 尾地址

    红黑树实现

    1. 定义rbtree_node、rbtree;
    2. 实现左旋、右旋,用于插入新节点后,继续符合红黑树的条件;

    需要动3根线,6个指针。

    1. 插入新节点,在插入之后进行修正,时的能够继续符合红黑树的定义

    新插入的节点,是红色的,所以只有它的父节点是红色的时候,需要修正。

    父节点是红色,分成以下case:

    1. 父节点是祖父节点左子树
    2. 父节点是祖父节点右子树

    上面两个case又可以分为3个小case:

    对于父节点是祖父节点左子树的情况,分为以下case:

    1. 叔父节点是红色;

    将父节点和叔父节点设置为黑色,祖父节点设置为红色,这样祖父节点往下就满足红黑树定义。

    接着将祖父节点作为当前节点,继续递归进行修正。

    1. 叔父节点是黑色,当前节点是父节点的右子树

    将父节点作为当前节点,并且以它为轴,进行左旋。

    1. 叔父节点是黑色,当前节点是父节点的左子树

    将父节点设置为黑色,祖父节点设置为红色,并以祖父节点为轴进行右旋。

    对于父节点是祖父节点右子树的情况,也可以分为3个case,将上面的代码copy一份,将left换成right,right换成left就可以了。

    左右子树高度最大相差多少?小于2倍。比如左子树高度为9,那么右子树最小为5,最大相差4

    ​​​​​​​#define RED 0
    #define BLACK 1
    
    
    typedef int KEY_TYPE;
    
    // int key_compare(KEY_TYPE a, KEY_TYPE b) {
    
    // }
    
    // 6项
    typedef struct _rbtree_node {
    
        unsigned char color;
        struct _rbtree_node *left;
        struct _rbtree_node *right;
        struct _rbtree_node *parent; // 用于旋转
    
        KEY_TYPE key;
        void *value;
        
    } rbtree_node;
    
    typedef struct _rbtree {
    
        rbtree_node *root;
        rbtree_node *nil; // 通用的叶子节点,很巧妙
    
    } rbtree;
    
    
    void _left_rotate(rbtree *T, rbtree_node *x) {
    
        // 3个方向,6根指针
    
        rbtree_node *y = x->right;
    
        // 1
        x->right = y->left; // 1.1
        if (y->left != T->nil) { // 1.2
            y->left->parent = x;
        }
    
        // 2
        y->parent = x->parent; // 2.1
        if (x->parent == T->nil) { // 2.2
            T->root = y;
        } else if (x == x->parent->left) {
            x->parent->left = y;
        } else {
            x->parent->right = y;
        }
    
        // 3
        y->left = x; // 3.1
        x->parent = y; // 3.2
    
    }
    
    void _right_rotate(rbtree *T, rbtree_node *y) {
    
        // 3个方向,6根指针
    
        rbtree_node *x = y->left;
    
        // 1
        y->left = x->right; // 1.1
        if (x->right != T->nil) { // 1.2
            x->right->parent = y;
        }
    
        // 2
        x->parent = y->parent; // 2.1
        if (y->parent == T->nil) { // 2.2
            T->root = x;
        } else if (y == y->parent->right) {
            y->parent->right = x;
        } else {
            y->parent->left = x;
        }
    
        // 3
        x->right = y; // 3.1
        y->parent = x; // 3.2
    
    }
    
    void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {
    
        // if (z->parent->color == RED) {
        while (z->parent->color == 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;
    
                    // 祖父节点的父节点可能是红色的,继续while处理
                    z = z->parent->parent; //将祖父节点作为当前节点,循环处理
    
                } else { 
                    if (z == z->parent->right) {
                        z = z->parent;
                        _left_rotate(T, z);
                    }
    
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    _right_rotate(T, z->parent->parent);
                }
            } else {
                
            }
    
        }
    
        T->root->color = BLACK; // 中间过程有可能把root节点变为红色了,最后需要将它变黑
    
    }
    
    
    void rbtree_insert(rbtree *T, rbtree_node *z) {
    
        rbtree_node *x = T->root;
        rbtree_node *y = T->nil;
    
        while (x != T->nil) {
            y = x; // y是x的父节点
            if (z->key < x->key) { // key的比较规则可以交给红黑树的使用者自定义
                x = x->left;
            } else if (z->key > x->key) {
                x = x->right;
            } else {
                return; // 是否插入相同的key,需要看应用场景
            }
    
        }
    
        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);
    
    }

    展开全文
  • RBTree ; /* * @Created with IntelliJ IDEA * @Description: 红黑树增加和删除操作演示 * @Package: com.AdvancedDataStructure.RBTree * @author: FLy-Fly-Zhang * @Date: 2019/7/10 * @Time: 18:42 */ ...

    概述:

    • 红黑树是不是一颗平衡树:
      不是,其高度差可以达到n
    • 红黑树结点左右子树高度差:
      长的不能超过短的二倍。因为需要保证所有路径上黑色节点数量相等,因此若一条节点路径全部是黑色,另一条路径红黑相间也只能插入2n个。
    • 红黑树的增删效率?
      高于AVL树,红黑树插入最多调整两次,删除调整三次。AVL树最多调整次数达到层数次。
    • 红黑树算法时间复杂度:O(log2N)

    红黑树特点:

    • 每个节点都有颜色,非黑即红。
    • 所有叶子节点都是黑色的,叶子节点是null节点,不存储实际数据。
    • 根节点必须是黑色。
    • 不能出现连续的红色节点。
    • 从根节点到达每个叶子节点的路径上黑色节点数量相同。

    红黑树插入的三种情况:最多两次插入旋转

    • 树是空的,第一个插入的根节点为黑色。
    • 树不为空,新插入节点颜色规定为红色,检查parent,parent为黑色,插入完成。
    • parent为红色(隐含爷爷节点为黑色),需要做插入调整,插入看叔叔节点颜色
    1. 叔叔节点为红色,将父亲节点和叔叔节点都置为黑色,将爷爷节点置为红色,然后将指针指向爷爷节点。
      在这里插入图片描述
    2. 叔叔节点为黑色,且我,父亲,爷爷在同一侧,将父亲节点调整为黑色,将爷爷节点调整为红色,在以爷爷节点为根节点进行旋转(当前节点在爷爷左子树,右旋,右子树,左旋)。
      在这里插入图片描述
    3. 叔叔节点为黑色,且我,父亲,爷爷不再同一侧,以父亲节点为根节点进行旋转(档期节点在爷爷左子树,左旋,右子树,右旋)。这样,爷爷,父亲,我在同一侧。执行情况2操作(注意:此时node节点已经变成父节点,为和情况2匹配,将node指向宣传后的父节点)。
      在这里插入图片描述

    红黑树删除的四种情况:最多三次旋转

    • 删除节点为红色节点直接删除。
    • 删除节点为黑色节点,删除节点补上来的孩子为红色,直接把孩子涂成黑色。
    • 若补上来的孩子为黑色节点,进行调整,向兄弟借黑色节点。
    1. 兄弟是黑色,兄弟的两个孩子也是黑色,不能接黑色节点。将兄弟节点置为红色,这样左右子树都缺一个黑色节点,等于parent缺一个黑色节点,指针上移父节点,重复操作。
      在这里插入图片描述
    2. 兄弟是黑色,和父亲,兄弟,在同一侧的兄弟的孩子(兄弟在左子树,孩子为左孩子,右子树,为右孩子)为红色节点时,将兄弟节点颜色置为父亲节点颜色,将父亲节点颜色置为黑色,将兄弟的红孩子置为黑色,再以父节点为根节点进行旋转(当前节点在为左孩子,左旋,右孩子,右旋)。
      在这里插入图片描述
    3. 兄弟是黑色,和父亲,兄弟不在同一侧的兄弟的孩子(兄弟为左子树,孩子为右孩子,右子树,为左孩子)为红色,将兄弟节点颜色和红孩子颜色互换,在以兄弟节点为根节点进行旋转(兄弟为左子树,左旋,右子树,右旋),这样就变成情况2。由情况2继续处理。
      在这里插入图片描述
    4. 当兄弟节点为红色时,将父节点置为红色,兄弟节点置为黑色。然后父节点为根节点进行旋转(当前节点为左孩子,左旋,右孩子,右旋),下来就会变成兄弟节点为黑色的情况。

    在这里插入图片描述

    代码演示:

    package com.AdvancedDataStructure.RBTree;
    
    /*
     * @Created with IntelliJ IDEA
     * @Description: 红黑树增加和删除操作演示
     * @Package: com.AdvancedDataStructure.RBTree
     * @author: FLy-Fly-Zhang
     * @Date: 2019/7/10
     * @Time: 18:42
     */
    enum Color{
        BLACK, RED;
    }
    
    class RBNode<T extends Comparable<T>>{
        private T data;
        private RBNode<T> left;
        private RBNode<T> right;
        private RBNode<T> parent;
        private Color color;
    
        public RBNode(T data, RBNode<T> left, RBNode<T> right, RBNode<T> parent, Color color) {
            this.data = data;
            this.left = left;
            this.right = right;
            this.parent = parent;
            this.color = color;
        }
    
        public T getData() {
            return data;
        }
    
        public void setData(T data) {
            this.data = data;
        }
    
        public RBNode<T> getLeft() {
            return left;
        }
    
        public void setLeft(RBNode<T> left) {
            this.left = left;
        }
    
        public RBNode<T> getRight() {
            return right;
        }
    
        public void setRight(RBNode<T> right) {
            this.right = right;
        }
    
        public RBNode<T> getParent() {
            return parent;
        }
    
        public void setParent(RBNode<T> parent) {
            this.parent = parent;
        }
    
        public Color getColor() {
            return color;
        }
    
        public void setColor(Color color) {
            this.color = color;
        }
    }
    
    class RBTree<T extends Comparable<T>>{
        private RBNode<T> root;
    
        public RBTree() {
            this.root = null;
        }
        public void insert(T data){
            //插入节点为根节点
            if(this.root==null){
                this.root=new RBNode<>(data,null,null,null,Color.BLACK);
                return;
            }
            RBNode<T> pre=null;
            RBNode<T> cur=this.root;
            //找到要插入的节点。
            while(cur!=null){
                pre=cur;
                if(cur.getData().compareTo(data)>0){
                    cur=cur.getLeft();
                }else if(cur.getData().compareTo(data)<0){
                    cur=cur.getRight();
                }else{
                    return;
                }
            }
            //已经确定父结点,并且将父结点与插入节点连接起来
            RBNode<T> node=new RBNode<>(data,null,null,pre,Color.RED);
            if(pre.getData().compareTo(data)>0){
                pre.setLeft(node);
            }else{
                pre.setRight(node);
            }
            //父结点为红色,需要调整。否则返回。
            if(pre.getColor()==Color.RED){
                fixAfterInsert(node);
            }
    
        }
    
        /**
         * 对父结点也是红色的情况进行调整。
         * @param node
         */
        private void fixAfterInsert(RBNode<T> node) {
            //注意,只要能进循环,那么肯定存在爷爷结点,因为根节点不能是红色,
            //所以父亲结点肯定不是根节点。
            //也不需要但是父结点是否为空,因为color函数经过处理,当传入结点为null时,默认为黑
            //因此直接退出循环。
            while(color(parent(node))==Color.RED){
                //父亲结点在爷爷的左子树
                if(left(parent(parent(node)))==parent(node)){
                    RBNode<T> uncle=right(parent(parent(node)));
                    //情况1
                    //叔叔结点和父亲结点都是红色。将他们都置为黑色,将爷爷结点为置为红色,并将node结点指向爷爷。
                    //爷爷结点之前肯定是黑色的。
                    if(color(uncle)==Color.RED){
                        setColor(parent(node),Color.BLACK);
                        setColor(uncle,Color.BLACK);
                        setColor(parent(parent(node)),Color.RED);
                        node=parent(parent(node)); //继续向上回溯。
                    }else{ //叔叔结点为黑色时
                        //我,父亲,爷爷不在同一侧,以父结点为根结点进行左旋
                        //情况3,前半部分
                        if(right(parent(node))==node){
                            node=parent(node);//为满足情况2,调整node。
                            leftRotate(node);
                        }
    
                        //我,父亲,爷爷在同一侧,爷爷为根节点右旋
                        //情况2和情况3后半部分
                        setColor(parent(parent(node)),Color.RED);
                        setColor(parent(node),Color.BLACK);
                        rightRotate(parent(parent(node)));
                        break;
                    }
                }else{ //父亲结点在爷爷的右子树
                    RBNode<T> uncle=left(parent(parent(node)));
                    //叔叔为黑色
                    if(color(uncle)==Color.RED){
                        setColor(uncle,Color.BLACK);
                        setColor(parent(node),Color.BLACK);
                        setColor(parent(parent(node)),Color.RED);
                        node=parent(parent(node)); //继续回溯
                    }else{//叔叔结点为黑色
                        //我,父亲,爷爷不再同一侧。以父亲结点为根节点右旋
                        if(left(parent(node))==node){
                            node=parent(node);//调整node结点
                            rightRotate(node);
                        }
                        //情况2,将父亲结点置为黑色,爷爷结点置为红色,以爷爷结点为根节点左旋
                        setColor(parent(parent(node)),Color.RED);
                        setColor(parent(node),Color.BLACK);
                        leftRotate(parent(parent(node)));
                        break;
                    }
                }
            }
            //退出循环可能是因为node已经到根节点了
            //将根节点置为black
            setColor(this.root,Color.BLACK);
        }
        /**
         * 左旋操作
         * @param node
         */
        public void leftRotate(RBNode<T> node){
            RBNode<T> child=node.getRight();
            child.setParent(node.getParent());
            if(node.getParent()==null){
                this.root=child;
            }else{
                //建立node节点的父结点与child的连接
                if(node.getParent().getLeft()==node){
                    node.getParent().setLeft(child);
                }else{
                    node.getParent().setRight(child);
                }
            }
            //建立node节点和child的左孩子连接
             //注意这句不能放到if里面,就算child.getleft为空,
             //但是node.setRight不为空,需要将其为null的。
            node.setRight(child.getLeft()); 
            if(child.getLeft()!=null){
                child.getLeft().setParent(node);
            }
            //建立node与child的连接
            child.setLeft(node);
            node.setParent(child);
        }
        public void rightRotate(RBNode<T> node){
            RBNode<T> child=node.getLeft();
            child.setParent(node.getParent());
            if(node.getParent()==null){
                this.root=child;
            }else{
                if(node.getParent().getLeft()==node){
                    node.getParent().setLeft(child);
                }else{
                    node.getParent().setRight(child);
                }
            }
            node.setLeft(child.getRight());
            if(child.getRight()!=null){
                child.getRight().setParent(node);
            }
            child.setRight(node);
            node.setParent(child);
        }
        public void remove(T data){
            if(this.root==null)
                return;
            RBNode<T> cur=this.root;
            while(cur!=null){
                if(cur.getData().compareTo(data)>0){
                    cur=cur.getLeft();
                }else if(cur.getData().compareTo(data)<0){
                    cur=cur.getRight();
                }else{
                    break;
                }
            }
            //未找到节点
            if(cur==null)
                return;
            //删除有两个孩子的节点
            if(cur.getLeft()!=null&&cur.getRight()!=null){
                RBNode<T> old=cur;
                cur=cur.getLeft();
                //找后继
                while(cur.getRight()!=null){
                    cur=cur.getRight();
                }
                old.setData(cur.getData());
            }
            RBNode<T> child=cur.getLeft();
            if(child==null)
                child=cur.getRight();
            //删除有一个孩子节点
            if(child!=null){
                child.setParent(parent(cur));
                //删除节点为根节点
                if(parent(cur)==null){
                    this.root=child;
                }else{
                    //将祖先节点和child连接起来
                    //要删除节点为当前节点左孩子
                    if(left(parent(cur))==cur){
                        parent(cur).setLeft(child);
                    }else{ //为右孩子
                        parent(cur).setRight(child);
                    }
                }
                //有孩子补上来,用孩子作为删除结点调整。
                if(color(cur)==Color.BLACK){
                    fixAfterRemove(child);
                }
            }else{//没有孩子的节点删除
                //删除节点为根节点
                if(parent(cur)==null){
                    this.root=null;
                }else{
                    //当没有孩子时,直接用删除结点进行调整,调整完再删除
                    if(color(cur)==Color.BLACK){
                        fixAfterRemove(cur);
                    }
                    //将祖先节点和child连接起来
                    //要删除节点为当前节点左孩子
                    if(left(parent(cur))==cur){
                        parent(cur).setLeft(null);
                    }else{ //为右孩子
                        parent(cur).setRight(null);
                    }
                }
            }
        }
        /*
         * 删除看兄弟
         */
        private void fixAfterRemove(RBNode<T> node) {
            //补上来节点为黑色,需要调整
            while(color(node)==Color.BLACK){
                //当前删除节点为左子树节点
                if(left(parent(node))==node){
                     //若兄弟节点为空,默认为黑色节点。
                     RBNode<T> brother=right(parent(node));
                     //情况四:兄弟节点为红色,将父节点调整为红色,兄弟节点调整为黑色。
                    //以父节点为根节点进行左旋。 情况就变成兄弟节点为黑色情况,继续其它情况处理
                     if(color(brother)==Color.RED){
                         parent(node).setColor(Color.RED);
                         brother.setColor(Color.BLACK);
                         leftRotate(parent(node));
                         //调整后brother成为祖先节点,重新找brother节点。
                         brother=right(parent(node));
                     }
                     //情况1:兄弟节点为黑色,兄弟节点两个孩子也是黑色,没法借,因此将兄弟涂成红色,这样父节点的左右子树都少一个黑色,
                    //等于父节点少一个黑色,若父节点是红色,直接涂成黑色,为黑色继续循环处理。
                     if(color(left(brother))==Color.BLACK && color(right(brother))==Color.BLACK){
                         brother.setColor(Color.RED);
                         node=parent(node);
                     }else{
                         //情况3前半段:兄弟的左孩子为红孩子,先将其调整为和父亲,兄弟一条线。
                         //将兄弟颜色和红孩子颜色互换,以兄弟节点为根节点,右旋。
                         //此时要注意,若两个孩子都为红色,那么直接进行情况2就可以了
                         if(color(right(brother))!=Color.RED){
                             brother.setColor(Color.RED);
                             left(brother).setColor(Color.BLACK);
                             rightRotate(brother);
                             brother=right(parent(node));//brother节点发生变化,重新定位
                         }
                         //情况2和情况三后半段
                         //兄弟的右孩子为红色,将兄弟节点颜色置为父亲节点颜色,将父亲节点颜色置为黑色。将红孩子置为黑色。
                         //以父亲结点为根节点进行左旋。
                         right(brother).setColor(Color.BLACK);
                         brother.setColor(color(parent(node)));
                         parent(node).setColor(Color.BLACK);
                         leftRotate(parent(node));
                         break;
                     }
                }else{ //要删除结点为右子树
                    RBNode<T> brother=left(parent(node));
                    //情况四,兄弟结点为红孩子,将父节点颜色和兄弟结点颜色互换,以父节点进行右旋
                    if(color(brother)==Color.RED){
                        brother.setColor(Color.BLACK);
                        parent(node).setColor(Color.RED);
                        rightRotate(parent(node));
                        brother=left(parent(node));//更新兄弟结点
                    }
                    //情况一,兄弟为黑色,两个孩子也为黑色,将兄弟涂成红色
                    //这样左右孩子都缺黑色,等于父节点缺黑色,指针上移,
                    if(color(left(brother))==Color.BLACK && color(right(brother))==Color.BLACK){
                        brother.setColor(Color.RED);
                        node=parent(node);
                    }else{
                        //情况三前半段:
                        //兄弟结点右子树为红孩子,将兄弟结点颜色和红孩子颜色互换,并以兄弟结点为根节点左旋。
                        if(color(left(brother))!=Color.RED){
                            brother.setColor(Color.RED);
                            right(brother).setColor(Color.BLACK);
                            leftRotate(brother);
                            brother=left(parent(node));
                        }
                        //情况2和情况三后半段,父亲,兄弟,红孩子在一条线
                        //将兄弟结点颜色置为父亲结点颜色,将父亲结点颜色置为黑色,将红孩子变成黑色。
                        //以父节点为根节点进行右旋。
                        brother.setColor(color(parent(node)));
                        parent(node).setColor(Color.BLACK);
                        right(brother).setColor(Color.BLACK);
                        rightRotate(parent(node));
                        break;
                    }
                }
            }
            //补上来节点为红色,直接涂成黑色。
            node.setColor(Color.BLACK);
        }
    
    
        private Color color(RBNode<T> node){
            return node == null ? Color.BLACK : node.getColor();
        }
    
        public void setColor(RBNode<T> node, Color color){
            node.setColor(color);
        }
    
        public RBNode<T> left(RBNode<T> node){
            return node.getLeft();
        }
    
        public RBNode<T> right(RBNode<T> node){
            return node.getRight();
        }
    
        public RBNode<T> parent(RBNode<T> node){
            return node.getParent();
        }
    }
    
    
    public class RBTreeDemo {
    
        public static void main(String[] args) {
            RBTree<Integer> rbTree=new RBTree<>();
            for (int i = 1; i <=10; i++) {
                rbTree.insert(i);
            }
            rbTree.remove(9);
            rbTree.remove(5);
            System.out.println();
        }
    }
    
    
    展开全文
  • 一个基于C++的红黑树实现, RedBlackTree, C++, 二叉树, 平衡二叉树
  • boost::intrusive::rbtree_algorithms用法的测试程序实现功能C++实现代码 实现功能 boost::intrusive::rbtree_algorithms用法的测试程序 C++实现代码 #include <boost/intrusive/rbtree_algorithms.hpp> #...

    boost::intrusive::rbtree_algorithms用法的测试程序

    实现功能

    boost::intrusive::rbtree_algorithms用法的测试程序

    C++实现代码

    #include <boost/intrusive/rbtree_algorithms.hpp>
    #include <cassert>
    struct my_node
    {
       
       my_node(in
    展开全文
  • nginx之ngx_rbtree

    2020-08-12 21:10:35
    nginx实现了一个红黑树的容器提供使用,定义在ngx_rbtree里面,这个容器相对简单,提供了插入,删除,初始化等方法。 ngx_rbtree.h: //ngx_rbtree_key为unsigned int或者int类型 typedef ngx_uint_t ngx_rbtree_key_...
  • rbtree:Go的红黑树-源码

    2021-05-04 02:46:14
    rbtree 请参阅分支以获取有争议的红黑树。 软件包rbtree实现了“算法简介”中引入的红黑树。 在当前语言规范下,有以下模式可以实现通用容器: 排序包使用的模式 type Interface interface { Compare ( ...
  • RBTree(红黑树)

    2017-06-05 13:33:04
    相对来说运用最多的还是RBTree。 红黑树的应用:  在C++ STL中,很多部分都运用了红黑树包括:Linux内核,java c# 还有(包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,...
  • Nginx源码分析之ngx_rbtree_t
  • RBTree — 红黑树

    2018-04-03 08:47:15
    RBTree — 红黑树 红黑树是一棵二叉搜索树,它在每个结点上增加了一个存储位来表示结点的颜色,可以是Red或Black。通过对任何一条从根到叶子简单路径上的颜色来约束,红黑树保证最长路径不超过最短路径的两倍,...
  • ngx_rbtree的基本使用方法

    千次阅读 2016-08-06 23:46:32
    ngx_rbtree 导语: 红黑树是一个常用的高级数据结构,它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的:它可以在O(log n)时间内做查找,插入和删除,这里的n是树中元素的数目. 一...
  • 了解一下B树 在实现红黑树之前先了解一下B树,因为红黑树的一些操作的实现和B树关系密切。 B树概念: m阶b树的性质(m>=2) ps:b树里面只有叶子节点和度>=2的节点 b树的搜索 b树的添加 m阶b树添加上溢 ...
  • rbtree 红黑树的 C 语言实现,主要是照搬了《算法导论》,红黑树是一种比较有实用意义的平衡树,不过也挻复杂,主要是利用其它兄弟节点再加以旋转来实现平衡,不过在并发上增删操作不太方便,这时用 skip list 跳跃...
  • linux内核分析之rbtree的使用

    千次阅读 2016-07-15 16:20:51
    我们真正关心的是key域,之所以要构建rbtree,就是为了尽量减少查找key域的时间,保证为O(logn)。 当然牺牲了些插入,删除的时间,为了保证rbtree的五大特性,每次插入或者删除一个node都必须 保证五大性质...
  • RBTree.rar

    2021-01-08 18:22:21
    红黑树 java 免费 但不保证正确性

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,752
精华内容 2,700
关键字:

rbTree