手写红黑树
Dreams
|
219
|
0

2823 字
|
44 分钟

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。红黑树具有以下特性：

  1. 每个节点要么是红色，要么是黑色。
  2. 根节点是黑色。
  3. 每个NULL节点看作黑色。
  4. 如果一个节点是红色，则它的子节点必须是黑色（红色节点不能连续出现相邻）。
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（即保持黑色平衡）。

注意NULL节点看作黑色，所以下图不是红黑树，如图一个NULL节点路径只包含2个黑色节点

 

红黑树通过这些性质保证了树的平衡，从而在进行插入、删除等操作时能够保持较好的性能。

先创建个红黑树基本类

package com.dreams.Tree;

public class RedBlackTree {
 
    enum Color {
        RED, BLACK;
    }
 
    Node root;
 
    static class Node {
        int key;
        Object value;
        Node left;
        Node right;
        Node parent; // 父节点
        Color color = Color.RED; // 颜色
 
        public Node(int key, Object value) {
            this.key = key;
            this.value = value;
        }
 
        public Node(int key) {
            this.key = key;
        }
 
       public Node(int key, Color color) {
           this.key = key;
           this.color = color;
       }
 
        public Node(int key, Color color, Node left, Node right) {
            this.key = key;
            this.color = color;
            this.left = left;
            this.right = right;
            if (left != null) {
                left.parent = this;
            }
            if (right != null) {
                right.parent = this;
            }
        }
    }
}

完善

public class RedBlackTree {

    enum Color {
        RED, BLACK;
    }

    Node root;

    static class Node {
        int key;
        Object value;
        Node left;
        Node right;
        Node parent; // 父节点
        Color color = RED; // 颜色

        public Node(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public Node(int key) {
            this.key = key;
        }

       public Node(int key, Color color) {
           this.key = key;
           this.color = color;
       }

        public Node(int key, Color color, Node left, Node right) {
            this.key = key;
            this.color = color;
            this.left = left;
            this.right = right;
            if (left != null) {
                left.parent = this;
            }
            if (right != null) {
                right.parent = this;
            }
        }

        // 是否是左孩子
        boolean isLeftChild() {
            return parent != null && parent.left == this;
        }

        // 叔叔
        Node uncle() {
            if (parent == null || parent.parent == null) {
                return null;
            }
            if (parent.isLeftChild()) {
                return parent.parent.right;
            } else {
                return parent.parent.left;
            }
        }

        // 兄弟
        Node sibling() {
            if (parent == null) {
                return null;
            }
            if (this.isLeftChild()) {
                return parent.right;
            } else {
                return parent.left;
            }
        }
    }
}

 

上述代码为了方便操作，定义了几个内部类的函数

判断是否是左孩子，因为已经维护了一个属性parent，所以简单判断即可。

// 是否是左孩子
boolean isLeftChild() {
    return parent != null && parent.left == this;
}

 

在红黑树中，叔叔节点是指当前节点的父节点的兄弟节点。

// 叔叔
Node uncle() {
    if (parent == null || parent.parent == null) {
        return null;
    }
    if (parent.isLeftChild()) {
        return parent.parent.right;
    } else {
        return parent.parent.left;
    }
}

 

同样返回兄弟节点

// 兄弟
Node sibling() {
    if (parent == null) {
        return null;
    }
    if (this.isLeftChild()) {
        return parent.right;
    } else {
        return parent.left;
    }
}

 

上面的都是内部类方法，主要为了方便操作

下面的才是红黑树方法

 

因为可能会出现传入的是空指针，所以定义个方法获取是红节点还是黑节点

 // 判断红
boolean isRed(Node node) {
    return node != null && node.color == RED;
}

// 判断黑
boolean isBlack(Node node) {
    return node == null || node.color == BLACK;
}

 

对指定节点进行左旋转以保持红黑树的性质

左旋前，如图先忽略红色和黑色节点颜色

左旋后

同样要注意pink节点不是根节点

代码如下

// 右旋 1. parent 的处理 2. 旋转后新根的父子关系
private void rightRotate(Node pink) {
    Node parent = pink.parent;
    Node yellow = pink.left;
    Node green = yellow.right;
    if (green != null) {
        green.parent = pink;
    }
    yellow.right = pink;
    yellow.parent = parent;
    pink.left = green;
    pink.parent = yellow;
    if (parent == null) {
        root = yellow;
    } else if (parent.left == pink) {
        parent.left = yellow;
    } else {
        parent.right = yellow;
    }
}

// 左旋
private void leftRotate(Node pink) {
    Node parent = pink.parent;
    Node yellow = pink.right;
    Node green = yellow.left;
    if (green != null) {
        green.parent = pink;
    }
    yellow.left = pink;
    yellow.parent = parent;
    pink.right = green;
    pink.parent = yellow;
    if (parent == null) {
        root = yellow;
    } else if (parent.left == pink) {
        parent.left = yellow;
    } else {
        parent.right = yellow;
    }
}

 

红黑树的插入操作是一个复杂但关键的过程，需要遵循一定的规则和步骤，以确保插入后的树仍然保持红黑树的性质。基本步骤如下：

  1. 将新节点插入到红黑树中，通常将新节点插入为红色节点。
  2. 插入节点为根节点，变为黑。
  3. 检查插入后的红黑树是否仍然满足红黑树的性质，红节点的子节点不能是红节点就是不能相邻。
  4. 插入节点为红色，父节点为黑色，不需要变化。
  5. 插入节点的父节点和叔叔节点都是红色，则将父亲变为黑色，为了保证黑色平衡，连带的叔叔也变为黑色，祖父如果是黑色不变，会造成这颗于树黑色过多，因此祖父节点变为红色，祖父如果变成红色,可能会接着触发红红相邻，因此对将祖父进行递归调整。
  6. 插入节点的父节点是红色，而叔叔节点是黑色或NULL节点：这种情况下，父亲为左孩于，插入节点也是左孩于，此时即LL不平衡；父亲为左孩子，插入节点是右孩子，此时即LR不平衡；父亲为右孩子，插入节点也是右孩子，此时即RR不平衡；父亲为右孩子，插入节点是左孩于，此时即RL不平衡，需要通过旋转操作来保持红黑树的性质。比如LR不平衡就父亲变黑，祖父变红，再以左旋（父亲左旋成LL）再祖父右旋。
  7. 最终通过旋转和颜色调整，使得插入后的红黑树恢复平衡，并且满足红黑树的所有性质。
/**
* 新增
* 正常增、遇到红红不平衡进行调整
* @param key 键
* @param value 值
*/
public void put(int key, Object value) {
    Node p = root;
    Node parent = null;
    while (p != null) {
        parent = p;
        if (key < p.key) {
            p = p.left;
        } else if (p.key < key) {
            p = p.right;
        } else {
            p.value = value; // 更新
            return;
        }
    }
    Node inserted = new Node(key, value);
    if (parent == null) {
        root = inserted;
    } else if (key < parent.key) {
        parent.left = inserted;
        inserted.parent = parent;
    } else {
        parent.right = inserted;
        inserted.parent = parent;
    }
    fixRedRed(inserted);
}

在新增成功后需要调用修复函数fixRedRed(inserted)修复红黑树

LL操作：

来一次右旋操作

然后节点3（原父节点）变黑，节点5（原祖父节点）变红

 

 

LR操作：

先来一次左旋操作

节点4（原节点）变黑，节点5（原祖父节点）变红

在来一次右旋

代码：

void fixRedRed(Node x) {
    // case 1 插入节点是根节点，变黑即可
    if (x == root) {
        x.color = BLACK;
        return;
    }
    // case 2 插入节点父亲是黑色，无需调整
    if (isBlack(x.parent)) {
        return;
    }
    /* case 3 当红红相邻，叔叔为红时
    需要将父亲、叔叔变黑、祖父变红，然后对祖父做递归处理
    */
    Node parent = x.parent;
    Node uncle = x.uncle();
    Node grandparent = parent.parent;
    if (isRed(uncle)) {
        parent.color = BLACK;
        uncle.color = BLACK;
        grandparent.color = RED;
        fixRedRed(grandparent);
        return;
    }

    // case 4 当红红相邻，叔叔为黑时
    if (parent.isLeftChild() && x.isLeftChild()) { // LL
        parent.color = BLACK;
        grandparent.color = RED;
        rightRotate(grandparent);
    } else if (parent.isLeftChild()) { // LR
        leftRotate(parent);
        x.color = BLACK;
        grandparent.color = RED;
        rightRotate(grandparent);
    } else if (!x.isLeftChild()) { // RR
        parent.color = BLACK;
        grandparent.color = RED;
        leftRotate(grandparent);
    } else { // RL
        rightRotate(parent);
        x.color = BLACK;
        grandparent.color = RED;
        leftRotate(grandparent);
    }
}

 

 

接下来是删除操作

首先需要一个方法查找删除节点

// 查找删除节点
private Node find(int key) {
    Node p = root;
    while (p != null) {
        if (key < p.key) {
            p = p.left;
        } else if (p.key < key) {
            p = p.right;
        } else {
            return p;
        }
    }
    return null;
}

 

删除之后需要查找替代节点，如果传入的被删除节点没有左右子节点，那么直接返回null。如果只有一个子节点，则返回该子节点作为替代节点。如果有两个子节点，则找到右子树中最小的节点（后继节点）作为替代节点。

private Node findReplaced(Node deleted) {
    if (deleted.left == null && deleted.right == null) {
        return null;
    }
    if (deleted.left == null) {
        return deleted.right;
    }
    if (deleted.right == null) {
        return deleted.left;
    }
    Node s = deleted.right;
    while (s.left != null) {
        s = s.left;
    }
    return s;
}

 

删除函数，如果节点为空，直接返回，否则进入doRemove函数递归

public void remove(int key) {
    Node deleted = find(key);
    if (deleted == null) {
        return;
    }
    doRemove(deleted);
}

 

逻辑在doRemove函数递归

这段代码实现了红黑树的删除操作：

  1. 首先，通过 findReplaced 方法找到要删除节点的替代节点 replaced。
  2. 如果要删除的节点没有孩子，则分为两种情况处理：
    • 如果要删除的节点是根节点（deleted == root），则直接删除根节点。
    • 如果要删除的节点不是根节点，且为黑色节点，则需要进行复杂的调整（fixDoubleBlack）。
    • 如果要删除的节点是红色叶子节点，则可以直接删除，并更新父节点的引用。
  3. 如果要删除的节点只有一个孩子，则将该孩子节点替代要删除的节点，并进行相应的处理：
    • 如果要删除的节点是根节点，则直接用替代节点覆盖根节点。
    • 如果要删除的节点不是根节点，根据要删除节点在父节点的位置，将替代节点链接到父节点的相应位置。
    • 删的是黑色节点，剩下的是红色节点，剩下这个红节点变黑即可
    • 如果要删除的节点是黑色节点，并且替代节点也是黑色节点，则需要进行复杂的调整（fixDoubleBlack）。
    • 如果要删除的节点是红色节点，直接替换即可。
  4. 如果要删除的节点有两个孩子，则找到其后继节点（replaced），交换要删除节点和后继节点的值，然后继续在后继节点上进行删除操作，也就是递归，递归最后走没有孩子的路。

代码如下

private void doRemove(Node deleted) {
    Node replaced = findReplaced(deleted);
    Node parent = deleted.parent;
    // 没有孩子
    if (replaced == null) {
        // case 1 删除的是根节点
        if (deleted == root) {
            root = null;
        } else {
            if (isBlack(deleted)) {
                // 复杂调整
                fixDoubleBlack(deleted);
            } else {
                // 红色叶子, 无需任何处理
            }
            if (deleted.isLeftChild()) {
                parent.left = null;
            } else {
                parent.right = null;
            }
            deleted.parent = null;
        }
        return;
    }
    // 有一个孩子
    if (deleted.left == null || deleted.right == null) {
        // case 1 删除的是根节点
        if (deleted == root) {
            root.key = replaced.key;
            root.value = replaced.value;
            root.left = root.right = null;
        } else {
            if (deleted.isLeftChild()) {
                parent.left = replaced;
            } else {
                parent.right = replaced;
            }
            replaced.parent = parent;
            deleted.left = deleted.right = deleted.parent = null;
            if (isBlack(deleted) && isBlack(replaced)) {
                // 复杂处理 @TODO 实际不会有这种情况 因为只有一个孩子时 被删除节点是黑色 那么剩余节点只能是红色不会触发双黑
                fixDoubleBlack(replaced);
            } else {
                // case 2 删除是黑，剩下是红
                replaced.color = BLACK;
            }
        }
        return;
    }
    // case 0 有两个孩子 => 有一个孩子 或 没有孩子
    int t = deleted.key;
    deleted.key = replaced.key;
    replaced.key = t;

    Object v = deleted.value;
    deleted.value = replaced.value;
    replaced.value = v;
    doRemove(replaced);
}

 

fixDoubleBlack方法用于处理双黑情况，即删除节点后可能会出现的问题。根据兄弟节点的颜色和侄子节点的颜色，分为不同的情况处理：

  • Case 3：兄弟节点是红色，则两个侄子节点一定是黑色。
  • Case 4：兄弟节点是黑色，且两个侄子节点也都是黑色。
  • Case 5：兄弟节点是黑色，且至少有一个侄子节点是红色。

这段代码是红黑树中用于处理双黑节点的情况的方法 fixDoubleBlack：

  1. 首先判断传入的节点 x 是否为根节点，如果是根节点，则直接返回，因为根节点没有父节点。
  2. 获取节点 x 的父节点 parent 和兄弟节点 sibling。
  3. Case 3：兄弟节点是红色
    • 如果兄弟节点 sibling 是红色节点，根据节点 x 在父节点中的位置进行相应的旋转操作，将情况转化为后续处理的情况。
    • 将原来的父节点 parent 的颜色设为红色，原来的兄弟节点 sibling 的颜色设为黑色。
    • 这个时候情况转化为后续处理的情况了，递归调用 fixDoubleBlack(x) 处理新的情况。
  4. Case 4：兄弟是黑色，两个侄子也是黑色
    • 如果兄弟节点 sibling 是黑色，且其左右子节点都是黑色，则将兄弟节点 sibling 的颜色设为红色。
    • 如果父节点 parent 是红色，则将其颜色设为黑色，这样就补齐了对于其他路径该路径少了的黑色节点。
    • 但是如果父节点 parent 是黑色，这样就对于其他路径该路径少了一个黑色节点。所以递归调用 fixDoubleBlack(parent) 处理双黑节点的问题。
  5. Case 5：兄弟是黑色，侄子有红色
    • 根据兄弟节点 sibling 和侄子节点的颜色情况，进行不同的旋转操作和颜色调整，以解决双黑节点带来的问题。
    • 如果兄弟是左孩子，左侄子是红， LL不平衡
    • 如果兄弟是左孩子，右侄于是红，LR 不平衡
    • 如果兄弟是右孩于，右侄于是红，RR 不平衡
    • 如果兄弟是右孩子，左侄子是红，RL 不平衡
    • 分别处理 LL、LR、RL、RR 四种情况，并最终将父节点的颜色设为黑色。
    • 如果兄弟节点 sibling 是左孩子且其左孩子节点红色（LL情况），则以父节点进行右旋转操作，并将原父节点设为黑色，原兄弟节点的颜色设为原父节点的颜色，原兄弟节点的左孩子节点设为黑色。
    • 如果兄弟节点 sibling 是左孩子且其右孩子节点红色（LR情况），则先将原兄弟节点 sibling 的右孩子节点设为父节点的颜色（注意要这里先执行，否则旋转后右孩子就不是原来的节点了），然后进行以兄弟节点左旋转，再以父节点右旋转操作。原父节点变为黑。
    • 如果兄弟节点 sibling 是右孩子且其左孩子节点红色（RL情况），则先将原兄弟节点 sibling 的左孩子节点设为父节点的颜色（注意要这里先执行，否则旋转后右孩子就不是原来的节点了），然后进行以兄弟节点右旋转，再以父节点左旋转操作。原父节点变为黑。
    • 如果兄弟节点 sibling 是右孩子且其右孩子节点红色（RR情况），则以父节点进行左旋转操作，并将原兄弟节点 sibling 的右孩子节点设为黑色，原兄弟节点的颜色设为其原父节点的颜色。并将原父节点设为黑色。
  6. 最后，如果兄弟节点为 null 的情况，实际情况下不会出现，因为双黑节点的处理应该在有兄弟节点的情况下完成。因此，这里可以添加注释提醒可能的错误。

代码如下

// 处理双黑 (case3、case4、case5)
private void fixDoubleBlack(Node x) {
    if (x == root) {
        return;
    }
    Node parent = x.parent;
    Node sibling = x.sibling();
    // case 3 兄弟节点是红色
    if (isRed(sibling)) {
        if (x.isLeftChild()) {
            leftRotate(parent);
        } else {
            rightRotate(parent);
        }
        parent.color = RED;
        sibling.color = BLACK;
        fixDoubleBlack(x);
        return;
    }
    if (sibling != null) {
        // case 4 兄弟是黑色, 两个侄子也是黑色
        if (isBlack(sibling.left) && isBlack(sibling.right)) {
            sibling.color = RED;
            if (isRed(parent)) {
                parent.color = BLACK;
            } else {
                fixDoubleBlack(parent);
            }
        }
        // case 5 兄弟是黑色, 侄子有红色
        else {
            // LL
            if (sibling.isLeftChild() && isRed(sibling.left)) {
                rightRotate(parent);
                sibling.left.color = BLACK;
                sibling.color = parent.color;
            }
            // LR
            else if (sibling.isLeftChild() && isRed(sibling.right)) {
                sibling.right.color = parent.color;
                leftRotate(sibling);
                rightRotate(parent);
            }
            // RL
            else if (!sibling.isLeftChild() && isRed(sibling.left)) {
                sibling.left.color = parent.color;
                rightRotate(sibling);
                leftRotate(parent);
            }
            // RR
            else {
                leftRotate(parent);
                sibling.right.color = BLACK;
                sibling.color = parent.color;
            }
            parent.color = BLACK;
        }
    } else {
        // @TODO 实际也不会出现，触发双黑后，兄弟节点不会为 null
        fixDoubleBlack(parent);
    }
}

 

 

参考

黑马数据结构

暂无评论

发送评论 编辑评论

 
 
 
 
 
   
 
  
  
   
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
  
上一篇
下一篇 
  推荐文章
解决/A/:id 跳转到另一个/A/:id
 
git无法提交大文件
 
CSRF引起整合 SpringSecurity 发送POST请求出现 403