国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

紅黑樹插入操作的java實現

jayce / 1840人閱讀

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

前言

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

參考鏈接

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
        
    }
}

有任何問題，歡迎指出！

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71676.html

相關文章

  • 數據結構與算法（十四）深入理解紅黑樹和JDK TreeMap和TreeSet源碼分析

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

    curlyCheng 評論0 收藏0

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

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

    2json 評論0 收藏0

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

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

    yangrd 評論0 收藏0

  • 數據結構 - 收藏集 - 掘金

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

    leeon 評論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 評論0 收藏0

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

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

    bigdevil_s 評論0 收藏0

發表評論

0條評論

jayce

男|高級講師

TA的文章

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