红黑树插入操作的java实现

jayce 发布于2019-08-16 13:24 / 1726人阅读

摘要：对红黑树不了解的建议先阅读文章再看实现。本红黑树实现不支持多线程环境。参考链接数据结构定义的红黑树的节点如下该作为的一个内部类存在。二者唯一的不同在于，默认插入的节点为红色，我们需要重新调整树结构从而确保红黑树重新达到平衡。

前言

网上有非常多的关于红黑树理论的描述，本文的重点将不在于此，但是会在文中给出优秀文章的链接。对红黑树不了解的建议先阅读文章再看实现。本红黑树实现不支持多线程环境。因为删除操作灰常复杂，所以后续更新。源码在文末可以查看。

参考链接

https://www.geeksforgeeks.org...
https://www.geeksforgeeks.org...
http://www.codebytes.in/2014/...
https://blog.csdn.net/eson_15...

数据结构

定义的红黑树的节点如下：

private static class Node{
        static final int RED = 0;
        static final int BLACK = 1;
        T value;
        int color = RED;
        Node leftChild;
        Node rightChild;
        Node parent;
        
        Node(T value) {
            this.value = value;
        }
    
        boolean isRoot() {
            return this.parent == null;
        }
        
        boolean isLeaf() {
            return this.leftChild == null && this.rightChild == null;
        }
        
        boolean isLeftChild() {
            return this.parent != null && this.parent.leftChild == this;
        }
        
        boolean isRightChild() {
            return this.parent != null && this.parent.rightChild == this;
        }
        
        Node getUncle() {
            if(this.parent == null || this.parent.parent == null) return null;
            if(this.parent.isLeftChild()) {
                return this.parent.parent.rightChild;
            } else {
                return this.parent.parent.leftChild;
            }
                        
        }
        
        Node getSibling() {
            if(this.parent == null) return null;
            return this.parent.leftChild == this ? this.parent.rightChild : this.parent.leftChild;
        }
    
        
        boolean isRed() {
            return this.color == RED;
        }
        
        boolean isBlack() {
            return this.color == BLACK;
        }
    }

该Node作为RedBlackTree的一个内部类存在。除了和普通的TreeNode相同给的左子节点和右子节点的引用，还额外引用了父节点，方便我们回溯。除此以外还封装了一些方法，比如获得自己的祖父节点，叔叔节点以及兄弟节点等。

旋转操作

因为额外持有了父节点，所以在执行旋转操作的时候需要额外注意空指针以及不恰当的赋值带来的循环引用。左旋和右旋的代码如下：

    private void rotateLeft(Node node) {
        if(node == null || node.rightChild == null) return;
        Node parent = node.parent;
        Node rightChild = node.rightChild;
        
        if(rightChild.leftChild != null) {
            node.rightChild = rightChild.leftChild;
            node.rightChild.parent = node;
        } else {
            node.rightChild = null;
        }
        
        rightChild.leftChild = node;
        node.parent = rightChild;
        
        if(parent != null) {
            rightChild.parent = parent;
            if(node == parent.leftChild) {
                parent.leftChild = rightChild;
            } else {
                parent.rightChild = rightChild;
            }
        } else {
            rightChild.parent = null;
            root = rightChild;
        }
    }
    
    private void rotateRight(Node node) {
        if(node == null || node.leftChild == null) return;
        Node parent = node.parent;
        Node leftChild = node.leftChild;
        
        if(leftChild.rightChild != null) {
            node.leftChild = leftChild.rightChild;
            node.leftChild.parent = node;
        } else {
            node.leftChild = null;
        }
        

        leftChild.rightChild = node;
        node.parent = leftChild;
        
        if(parent != null) {
            leftChild.parent = parent;
            if(node == parent.leftChild) {
                parent.leftChild = leftChild;
            } else {
                parent.rightChild = leftChild;
            }
        } else {
            leftChild.parent = null;
            root = leftChild;
        }
    }

插入

我们知道，在红黑树中插入一个节点相当于在一个二叉搜索树中插入一个节点。因此该节点一定是作为叶节点而插入的。二者唯一的不同在于，默认插入的节点为红色，我们需要重新调整树结构从而确保红黑树重新达到平衡。

    @Override
    public void insert(T t) {
        Node newNode = new Node(t);
        if(root == null) {
            root = newNode;
            root.color = Node.BLACK;
            size++;
        } else {
            Node tmp = root;
            while(tmp != null) {
                if(tmp.value.equals(t)) {
                    newNode = tmp;
                    break;
                } else if(tmp.value.compareTo(t) < 0) {
                    if(tmp.rightChild == null) {
                        tmp.rightChild = newNode;
                        newNode.parent = tmp;
                        size++;
                        break;
                    } else {
                        tmp = tmp.rightChild;
                    }
                } else {
                    if(tmp.leftChild == null) {
                        tmp.leftChild = newNode;
                        newNode.parent = tmp;
                        size++;
                        break;
                    } else {
                        tmp = tmp.leftChild;
                    }
                }
            }
        }
        adjust(newNode);
    }

    private void adjust(Node node) {
        if(node.isRoot()) {
            node.color = Node.BLACK;
            return;
        } else if(node.parent.isRed()) {
            //肯定存在祖父节点，因为根节点必须为黑色
            Node parent = node.parent;
            Node grandParent = node.parent.parent;
            Node uncle = node.getUncle();
            if(uncle!=null && uncle.isRed()) {
                parent.color = Node.BLACK;
                uncle.color = Node.BLACK;
                grandParent.color = Node.RED;
                adjust(grandParent);
            } else {
                if(node.isLeftChild() && node.parent.isLeftChild()) {
                    parent.color = Node.BLACK;
                    grandParent.color = Node.RED;
                    rotateRight(grandParent);
                } else if(node.isRightChild() && node.parent.isRightChild()) {
                    parent.color = Node.BLACK;
                    grandParent.color = Node.RED;
                    rotateLeft(grandParent);
                } else if(node.isLeftChild() && node.parent.isRightChild()) {
                    node.color = Node.BLACK;
                    grandParent.color = Node.RED;
                    rotateRight(parent);
                    rotateLeft(grandParent);
                } else {
                    node.color = Node.BLACK;
                    grandParent.color = Node.RED;
                    rotateLeft(parent);
                    rotateRight(grandParent);
                }
            }
        }
    }

删除

待更新

源码

public interface RedBlackTreeADT> {    
    boolean contains(T t);
    
    void insert(T t);
    
    void delete(T t);
    
    int size();
    
}


public class RedBlackTree> implements RedBlackTreeADT{

    private int size;
    private Node root;
    
    private static class Node{
        static final int RED = 0;
        static final int BLACK = 1;
        T value;
        int color = RED;
        Node leftChild;
        Node rightChild;
        Node parent;
        
        Node(T value) {
            this.value = value;
        }
    
        boolean isRoot() {
            return this.parent == null;
        }
        
        boolean isLeaf() {
            return this.leftChild == null && this.rightChild == null;
        }
        
        boolean isLeftChild() {
            return this.parent != null && this.parent.leftChild == this;
        }
        
        boolean isRightChild() {
            return this.parent != null && this.parent.rightChild == this;
        }
        
        Node getUncle() {
            if(this.parent == null || this.parent.parent == null) return null;
            if(this.parent.isLeftChild()) {
                return this.parent.parent.rightChild;
            } else {
                return this.parent.parent.leftChild;
            }
                        
        }
        
        Node getSibling() {
            if(this.parent == null) return null;
            return this.parent.leftChild == this ? this.parent.rightChild : this.parent.leftChild;
        }
    
        
        boolean isRed() {
            return this.color == RED;
        }
        
        boolean isBlack() {
            return this.color == BLACK;
        }
    }

    @Override
    public boolean contains(T t) {
        Node tmp = root;
        while(tmp != null) {
            int cmp = tmp.value.compareTo(t);
            if(cmp == 0) {
                return true;
            } else if (cmp < 0) {
                tmp = tmp.rightChild;
            } else {
                tmp = tmp.leftChild;
            }
        }
        return false;
    }

    @Override
    public void insert(T t) {
        Node newNode = new Node(t);
        if(root == null) {
            root = newNode;
            root.color = Node.BLACK;
            size++;
        } else {
            Node tmp = root;
            while(tmp != null) {
                if(tmp.value.equals(t)) {
                    newNode = tmp;
                    break;
                } else if(tmp.value.compareTo(t) < 0) {
                    if(tmp.rightChild == null) {
                        tmp.rightChild = newNode;
                        newNode.parent = tmp;
                        size++;
                        break;
                    } else {
                        tmp = tmp.rightChild;
                    }
                } else {
                    if(tmp.leftChild == null) {
                        tmp.leftChild = newNode;
                        newNode.parent = tmp;
                        size++;
                        break;
                    } else {
                        tmp = tmp.leftChild;
                    }
                }
            }
        }
        adjust(newNode);
    }

    private void adjust(Node node) {
        if(node.isRoot()) {
            node.color = Node.BLACK;
            return;
        } else if(node.parent.isRed()) {
            //肯定存在祖父节点，因为根节点必须为黑色
            Node parent = node.parent;
            Node grandParent = node.parent.parent;
            Node uncle = node.getUncle();
            if(uncle!=null && uncle.isRed()) {
                parent.color = Node.BLACK;
                uncle.color = Node.BLACK;
                grandParent.color = Node.RED;
                adjust(grandParent);
            } else {
                if(node.isLeftChild() && node.parent.isLeftChild()) {
                    parent.color = Node.BLACK;
                    grandParent.color = Node.RED;
                    rotateRight(grandParent);
                } else if(node.isRightChild() && node.parent.isRightChild()) {
                    parent.color = Node.BLACK;
                    grandParent.color = Node.RED;
                    rotateLeft(grandParent);
                } else if(node.isLeftChild() && node.parent.isRightChild()) {
                    node.color = Node.BLACK;
                    grandParent.color = Node.RED;
                    rotateRight(parent);
                    rotateLeft(grandParent);
                } else {
                    node.color = Node.BLACK;
                    grandParent.color = Node.RED;
                    rotateLeft(parent);
                    rotateRight(grandParent);
                }
            }
        }
    }
    
    private void rotateLeft(Node node) {
        if(node == null || node.rightChild == null) return;
        Node parent = node.parent;
        Node rightChild = node.rightChild;
        
        if(rightChild.leftChild != null) {
            node.rightChild = rightChild.leftChild;
            node.rightChild.parent = node;
        } else {
            node.rightChild = null;
        }
        
        rightChild.leftChild = node;
        node.parent = rightChild;
        
        if(parent != null) {
            rightChild.parent = parent;
            if(node == parent.leftChild) {
                parent.leftChild = rightChild;
            } else {
                parent.rightChild = rightChild;
            }
        } else {
            rightChild.parent = null;
            root = rightChild;
        }
    }
    
    private void rotateRight(Node node) {
        if(node == null || node.leftChild == null) return;
        Node parent = node.parent;
        Node leftChild = node.leftChild;
        
        if(leftChild.rightChild != null) {
            node.leftChild = leftChild.rightChild;
            node.leftChild.parent = node;
        } else {
            node.leftChild = null;
        }
        

        leftChild.rightChild = node;
        node.parent = leftChild;
        
        if(parent != null) {
            leftChild.parent = parent;
            if(node == parent.leftChild) {
                parent.leftChild = leftChild;
            } else {
                parent.rightChild = leftChild;
            }
        } else {
            leftChild.parent = null;
            root = leftChild;
        }
    }
    

    @Override
    public int size() {
        return size;
    }
    

    public void printTree() {
        this.printTree(this.root);
    }
    
    private void printTree(Node root) {
        if(root == null) {
            System.out.print("nil(BLACK)");
            return;
        }
        printTree(root.leftChild);
        System.out.print(root.value + "(" + (root.color==Node.RED ? "RED" : "BLACK") + ")");
        printTree(root.rightChild);
    }

    @Override
    public void delete(T t) {
        // TODO Auto-generated method stub
        
    }
}

有任何问题，欢迎指出！

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

私有云专线服务红黑树 python 红黑树 linux 红黑树 linux红黑树代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71676.html

数据结构与算法（十四）深入理解红黑树和JDK TreeMap和TreeSet源码分析

摘要：很多文章或书籍在介绍红黑树的时候直接上来就是红黑树的个基本性质插入删除操作等。这也不奇怪，算法的作者就是红黑树的作者之一。所以，理解树对掌握红黑树是至关重要的。本文主要包括以下内容：什么是2-3树 2-3树的插入操作红黑树与2-3树的等价关系《算法4》和《算法导论》上关于红黑树的差异红黑树的5条基本性质的分析红黑树与2-3-4树的等价关系红黑树的插入、删除操作 JDK ...

curlyCheng 2019-08-16 15:16 评论0 收藏0
Map集合、散列表、红黑树介绍

摘要：并且，我们的底层都是红黑树来实现的。红黑树是一种平衡二叉树因此它没有节点。前言声明，本文用得是jdk1.8 前面已经讲了Collection的总览和剖析List集合： Collection总览 List集合就这么简单【源码剖析】原本我是打算继续将Collection下的Set集合的，结果看了源码发现：Set集合实际上就是HashMap来构建的！ showImg(https:/...

2json 2019-08-15 15:20 评论0 收藏0
树 - （二叉查找树，红黑树，B树）- 红黑树

摘要：需要执行的操作依次是首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除然后，通过旋转和重新着色等一系列来修正该树，使之重新成为一棵红黑树。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党关于二叉树的基本知识，可以参见：Java 实现基本数据结构 2(树) 以下是算法导论第13章的学...

yangrd 2019-08-14 12:05 评论0 收藏0
数据结构 - 收藏集 - 掘金

面试旧敌之红黑树（直白介绍深入理解） - Android - 掘金读完本文你将了解到：什么是红黑树黑色高度红黑树的 5 个特性红黑树的左旋右旋指定节点 x 的左旋右图转成左图指定节点 y 的右旋左图转成右图红黑树的平衡插入二叉查找树的插入插入后调整红黑树结构调整思想插入染红后... java 多线程同步以及线程间通信详解 & 消费者生产者模式 & 死锁 & Thread...

leeon 2019-08-16 10:32 评论0 收藏0
Java多线程进阶（二三）—— J.U.C之collections框架：ConcurrentHash

摘要：需要注意的是所链接的是一颗红黑树，红黑树的结点用表示，所以中实际上一共有五种不同类型的结点。时不再延续，转而直接对每个桶加锁，并用红黑树链接冲突结点。 showImg(https://segmentfault.com/img/bVbfTCY?w=1920&h=1080); 本文首发于一世流云专栏：https://segmentfault.com/blog... 一、Concurren...

Jason_Geng 2019-08-19 11:00 评论0 收藏0
这几道Java集合框架面试题在面试中几乎必问

摘要：若遇到哈希冲突，则将冲突的值加到链表中即可。之后相比于之前的版本，之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值默认为时，将链表转化为红黑树，以减少搜索时间。有序，唯一红黑树自平衡的排序二叉树。本文是最最最常见Java面试题总结系列第三周的文章。主要内容： Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...

bigdevil_s 2019-08-19 11:01 评论0 收藏0