成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

紅黑樹插入操作的java實現(xiàn)

jayce / 1861人閱讀

摘要：對紅黑樹不了解的建議先閱讀文章再看實現(xiàn)。本紅黑樹實現(xiàn)不支持多線程環(huán)境。參考鏈接數(shù)據(jù)結(jié)構(gòu)定義的紅黑樹的節(jié)點如下該作為的一個內(nèi)部類存在。二者唯一的不同在于，默認插入的節(jié)點為紅色，我們需要重新調(diào)整樹結(jié)構(gòu)從而確保紅黑樹重新達到平衡。

前言

網(wǎng)上有非常多的關(guān)于紅黑樹理論的描述，本文的重點將不在于此，但是會在文中給出優(yōu)秀文章的鏈接。對紅黑樹不了解的建議先閱讀文章再看實現(xiàn)。本紅黑樹實現(xiàn)不支持多線程環(huán)境。因為刪除操作灰常復(fù)雜，所以后續(xù)更新。源碼在文末可以查看。

參考鏈接

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

數(shù)據(jù)結(jié)構(gòu)

定義的紅黑樹的節(jié)點如下：

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的一個內(nèi)部類存在。除了和普通的TreeNode相同給的左子節(jié)點和右子節(jié)點的引用，還額外引用了父節(jié)點，方便我們回溯。除此以外還封裝了一些方法，比如獲得自己的祖父節(jié)點，叔叔節(jié)點以及兄弟節(jié)點等。

旋轉(zhuǎn)操作

因為額外持有了父節(jié)點，所以在執(zhí)行旋轉(zhuǎn)操作的時候需要額外注意空指針以及不恰當?shù)馁x值帶來的循環(huán)引用。左旋和右旋的代碼如下：

    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;
        }
    }
插入

我們知道，在紅黑樹中插入一個節(jié)點相當于在一個二叉搜索樹中插入一個節(jié)點。因此該節(jié)點一定是作為葉節(jié)點而插入的。二者唯一的不同在于，默認插入的節(jié)點為紅色，我們需要重新調(diào)整樹結(jié)構(gòu)從而確保紅黑樹重新達到平衡。

    @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()) {
            //肯定存在祖父節(jié)點，因為根節(jié)點必須為黑色
            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()) {
            //肯定存在祖父節(jié)點，因為根節(jié)點必須為黑色
            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
        
    }
}

有任何問題，歡迎指出！

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/71676.html

相關(guān)文章

  • 數(shù)據(jù)結(jié)構(gòu)與算法（十四）深入理解紅黑樹和JDK TreeMap和TreeSet源碼分析

    摘要：很多文章或書籍在介紹紅黑樹的時候直接上來就是紅黑樹的個基本性質(zhì)插入刪除操作等。這也不奇怪，算法的作者就是紅黑樹的作者之一。所以，理解樹對掌握紅黑樹是至關(guān)重要的。 本文主要包括以下內(nèi)容： 什么是2-3樹 2-3樹的插入操作 紅黑樹與2-3樹的等價關(guān)系 《算法4》和《算法導(dǎo)論》上關(guān)于紅黑樹的差異 紅黑樹的5條基本性質(zhì)的分析 紅黑樹與2-3-4樹的等價關(guān)系 紅黑樹的插入、刪除操作 JDK ...

    curlyCheng 評論0 收藏0

  • Map集合、散列表、紅黑樹介紹

    摘要：并且，我們的底層都是紅黑樹來實現(xiàn)的。紅黑樹是一種平衡二叉樹因此它沒有節(jié)點。 前言 聲明，本文用得是jdk1.8 前面已經(jīng)講了Collection的總覽和剖析List集合： Collection總覽 List集合就這么簡單【源碼剖析】 原本我是打算繼續(xù)將Collection下的Set集合的，結(jié)果看了源碼發(fā)現(xiàn)：Set集合實際上就是HashMap來構(gòu)建的！ showImg(https:/...

    2json 評論0 收藏0

  • 樹 - （二叉查找樹，紅黑樹，B樹）- 紅黑樹

    摘要：需要執(zhí)行的操作依次是首先，將紅黑樹當作一顆二叉查找樹，將該節(jié)點從二叉查找樹中刪除然后，通過旋轉(zhuǎn)和重新著色等一系列來修正該樹，使之重新成為一棵紅黑樹。 雖是讀書筆記，但是如轉(zhuǎn)載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨 關(guān)于二叉樹的基本知識，可以參見：Java 實現(xiàn)基本數(shù)據(jù)結(jié)構(gòu) 2(樹) 以下是算法導(dǎo)論第13章的學(xué)...

    yangrd 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu) - 收藏集 - 掘金

    面試舊敵之紅黑樹（直白介紹深入理解） - Android - 掘金 讀完本文你將了解到： 什么是紅黑樹 黑色高度 紅黑樹的 5 個特性 紅黑樹的左旋右旋 指定節(jié)點 x 的左旋 右圖轉(zhuǎn)成左圖 指定節(jié)點 y 的右旋左圖轉(zhuǎn)成右圖 紅黑樹的平衡插入 二叉查找樹的插入 插入后調(diào)整紅黑樹結(jié)構(gòu) 調(diào)整思想 插入染紅后... java 多線程同步以及線程間通信詳解 & 消費者生產(chǎn)者模式 & 死鎖 & Thread...

    leeon 評論0 收藏0

  • Java多線程進階（二三）—— J.U.C之collections框架：ConcurrentHash

    摘要：需要注意的是所鏈接的是一顆紅黑樹，紅黑樹的結(jié)點用表示，所以中實際上一共有五種不同類型的結(jié)點。時不再延續(xù)，轉(zhuǎn)而直接對每個桶加鎖，并用紅黑樹鏈接沖突結(jié)點。 showImg(https://segmentfault.com/img/bVbfTCY?w=1920&h=1080); 本文首發(fā)于一世流云專欄：https://segmentfault.com/blog... 一、Concurren...

    Jason_Geng 評論0 收藏0

  • 這幾道Java集合框架面試題在面試中幾乎必問

    摘要：若遇到哈希沖突，則將沖突的值加到鏈表中即可。之后相比于之前的版本，之后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值默認為時，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間。有序，唯一紅黑樹自平衡的排序二叉樹。 本文是最最最常見Java面試題總結(jié)系列第三周的文章。主要內(nèi)容： Arraylist 與 LinkedList 異同 ArrayList 與 Vector 區(qū)別 HashMap的底層...

    bigdevil_s 評論0 收藏0

發(fā)表評論

0條評論

jayce

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<