Java實(shí)現(xiàn)紅黑樹(平衡二叉樹)的詳細(xì)過程

更新時(shí)間：2021年10月14日 15:30:25 作者：qzlzzz

紅黑樹接近平衡的二叉樹，插入，刪除函數(shù)跟平衡二叉樹一樣，只是平衡函數(shù)不同,下面這篇文章主要給大家介紹了關(guān)于Java實(shí)現(xiàn)紅黑樹(平衡二叉樹)的相關(guān)資料,需要的朋友可以參考下

前言

在實(shí)現(xiàn)紅黑樹之前,我們先來了解一下符號(hào)表。

符號(hào)表的描述借鑒了Algorithms第四版,詳情在:https://algs4.cs.princeton.edu/home/

符號(hào)表有時(shí)候被稱為字典，就如同英語(yǔ)字典中，一個(gè)單詞對(duì)應(yīng)一個(gè)解釋，符號(hào)表有時(shí)候又被稱之為索引，即書本最后將術(shù)語(yǔ)按照字母順序列出以方便查找的那部分?？偟膩碚f，符號(hào)表就是將一個(gè)鍵和一個(gè)值聯(lián)系起來，就如Python中的字典,JAVA中的HashMap和HashTable,Redis中以鍵值對(duì)的存儲(chǔ)方式。

在如今的大數(shù)據(jù)時(shí)代，符號(hào)表的使用是非常頻繁的，但在一個(gè)擁有著海量數(shù)據(jù)的符號(hào)表中，如何去實(shí)現(xiàn)快速的查找以及插入數(shù)據(jù)就是高效的算法去完成的事情，可以說沒有這些算法的發(fā)明產(chǎn)生，信息時(shí)代無從談起。

既然是數(shù)據(jù)結(jié)構(gòu)去實(shí)現(xiàn)符號(hào)表，這就要求我們對(duì)符號(hào)表的API,也就是符號(hào)表的功能去定義，前面我們說到既然符號(hào)表的使用是如何在海量數(shù)據(jù)中去查找，插入數(shù)據(jù)，那么我們便定義符號(hào)表的API有增刪改查這四個(gè)基本功能。

/**
 * <p>
 *     符號(hào)表的基本API
 * </p>
 * @author qzlzzz
 * @version 1.0
 * @since 2021/10/8
 */
public interface RedBlackBST<Key extends Comparable<Key>,Value> {

    /**
     * 根據(jù)Key在符號(hào)表中找到Value
     * @param key the key
     * @return the value of key
     */
    Value get(Key key);

    /**
     * 插入key-value，如果符號(hào)表中有Key，且Key不為空則將該Key的Value轉(zhuǎn)為傳入的Value
     * @param key the-key
     * @param value the-value
     */
    void put(Key key,Value value);

    /**
     * 根據(jù)Key去符號(hào)表中刪除Key
     * @param key the key
     */
    void delete(Key key);

}

這里由于紅黑樹是平衡二叉樹，即意味著其有平衡性和有序性，因?yàn)槠溆行蛐缘奶攸c(diǎn)，因此我們可以范圍或根據(jù)位置去需找鍵，也可以查找到樹中的最小鍵和最大鍵。

至于什么是平衡性，文章后講，這里先停一停。

因此我們可以額外的定義:

    /**
     * 根據(jù)位置返回鍵，如果沒有返回null
     * @param k the index of key
     * @return the key
     */
    Key select(int k);

    /**
     * 返回紅黑樹中最小的鍵
     * @return the min key in this tree
     */
    Key min();

    /**
     * 返回紅黑樹中最大的鍵
     * @return the max key in this tree
     */
    Key max();

    /**
     * 返回小于該鍵的數(shù)量
     * @param key the key
     * @return amount of key small than the key
     */
    int rank(Key key);

接下來我們說說紅黑樹。

紅黑二叉查找樹

紅黑二叉查找樹實(shí)際上基于二叉查找樹上實(shí)現(xiàn)了2-3樹，也就是說紅黑二叉查找樹是一個(gè)2-3樹。所以在認(rèn)識(shí)紅黑二叉查找樹之前，我們得了解2-3樹的原理，以及組成結(jié)構(gòu)。

2-3樹

我們把含有一個(gè)鍵，兩個(gè)鏈接的結(jié)點(diǎn)稱為2-結(jié)點(diǎn)，標(biāo)準(zhǔn)的二叉查找樹其每個(gè)結(jié)點(diǎn)都是2-結(jié)點(diǎn)，在考慮好的情況下，我們構(gòu)造標(biāo)準(zhǔn)二叉查找樹，一般能夠得到樹高為總鍵樹的對(duì)數(shù)的一個(gè)查找樹，其查找和插入操作都是對(duì)數(shù)級(jí)別的，但標(biāo)準(zhǔn)二叉查找樹的基本實(shí)現(xiàn)的良好性能取決于鍵值對(duì)分布的足夠亂以致于打消長(zhǎng)路徑帶來的問題，但我們不能保證插入情況是隨機(jī)的，如果鍵值對(duì)的插入時(shí)順序插入的，就會(huì)帶來下面的問題:

從圖中我們可以看到，我們將A,B,C,D,E按順序插入的話，會(huì)得到一個(gè)鍵值與樹高成正比的二叉查找樹，其插入和查找的會(huì)從對(duì)數(shù)級(jí)別提到O(N)級(jí)別。

當(dāng)然我們希望的肯定是無論鍵值對(duì)的情況是怎樣的，我們都能構(gòu)造一個(gè)樹高與總鍵數(shù)成對(duì)數(shù)，插入查找等操作均能夠在對(duì)數(shù)時(shí)間內(nèi)完成的數(shù)據(jù)結(jié)構(gòu)。也就是說，在順序插入的情況下，我們希望樹高依然為~lgN,這樣我們就能保證所有的查找都能在~lgN次比較結(jié)束。

為了保證查找樹的平衡性，我們需要一些靈活性，因此在這里我們?cè)试S樹中的一個(gè)結(jié)點(diǎn)保存多個(gè)鍵，我們引入3-結(jié)點(diǎn),所謂的3-結(jié)點(diǎn)就是一個(gè)結(jié)點(diǎn)中有2個(gè)鍵，3個(gè)鏈接。

因此一顆2-3查找樹或?yàn)橐活w空樹，或由2-結(jié)點(diǎn)和3-結(jié)點(diǎn)組成。在介紹2-3樹的操作前，我們將A,B,C,D,E,F,G,H順序插入得到的樹如下圖所示:

從圖中我們可以看出2-3樹的平衡性，靈活性，它保證了任意的插入得到的樹高依舊是總鍵的對(duì)數(shù)。

2-3樹的插入操作

理解2-3樹的插入操作，有利于去構(gòu)造紅黑樹，在這里分三種情況:

插入新鍵,底層結(jié)點(diǎn)是2-結(jié)點(diǎn)
插入新鍵，底層結(jié)點(diǎn)是3-結(jié)點(diǎn),父結(jié)點(diǎn)是2-結(jié)點(diǎn)
插入新鍵，底層結(jié)點(diǎn)是3-結(jié)點(diǎn)，父結(jié)點(diǎn)是3-結(jié)點(diǎn)

第一種情況

若插入新鍵，底層結(jié)點(diǎn)是2-結(jié)點(diǎn)的話，該底層結(jié)點(diǎn)變?yōu)?-結(jié)點(diǎn),將插入的鍵保存其中即可。

第二種情況

若插入新鍵，底層結(jié)點(diǎn)是3-結(jié)點(diǎn),底層結(jié)點(diǎn)先變成臨時(shí)的4-結(jié)點(diǎn)(3個(gè)鍵，4條鏈接)，后4-結(jié)點(diǎn)中的中鍵吐出，使得父節(jié)點(diǎn)由2-結(jié)點(diǎn)變?yōu)?-結(jié)點(diǎn)，原4-結(jié)點(diǎn)中鍵兩邊的鍵變成兩個(gè)2-結(jié)點(diǎn),原本由父結(jié)點(diǎn)指向子結(jié)點(diǎn)的一個(gè)鏈接，替換為原4-結(jié)點(diǎn)中鍵左右兩邊的鏈接，分別指向兩個(gè)新的2-結(jié)點(diǎn)。

第三種情況

若插入新鍵，底層結(jié)點(diǎn)是3-結(jié)點(diǎn),其父結(jié)點(diǎn)也是3-結(jié)點(diǎn)的話,使得底層結(jié)點(diǎn)變?yōu)榕R時(shí)的4-結(jié)點(diǎn),后4-結(jié)點(diǎn)中的中鍵吐出，使得父節(jié)點(diǎn)由3-結(jié)點(diǎn)變?yōu)榕R時(shí)的4-結(jié)點(diǎn),原4-結(jié)點(diǎn)中鍵兩邊的鍵變成兩個(gè)2-結(jié)點(diǎn),原本由父結(jié)點(diǎn)指向子結(jié)點(diǎn)的一個(gè)鏈接，替換為原4-結(jié)點(diǎn)中鍵左右兩邊的鏈接，分別指向兩個(gè)新的2-結(jié)點(diǎn)，隨后父節(jié)點(diǎn)也要吐出中鍵，重復(fù)上述的步驟，如果父節(jié)點(diǎn)的父節(jié)點(diǎn)也是3-結(jié)點(diǎn)，則繼續(xù)持續(xù)上述步驟，若根結(jié)點(diǎn)也是3-結(jié)點(diǎn),根節(jié)點(diǎn)吐出中鍵，生成兩個(gè)2-結(jié)點(diǎn)后，整個(gè)樹高+1,但各個(gè)底層結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑始終相等。

以上的三種變化是2-3樹的動(dòng)態(tài)變化的核心，非常關(guān)鍵，我們可以在推演的過程種看到這種變化是自下向上的，而且是局部的變化，這種局部的變化并沒有影響2-3樹的有序性和平衡性。

同時(shí)我們也可以看出，如果要以代碼來實(shí)現(xiàn)2-3樹的話相當(dāng)?shù)穆闊?，因?yàn)樾枰幚淼那闆r實(shí)在太多。我們需要維護(hù)兩種不同類型的結(jié)點(diǎn)，將被查找的鍵和結(jié)中的每個(gè)鍵進(jìn)行比較，將鏈接和其他信息從一個(gè)結(jié)點(diǎn)復(fù)制到另一個(gè)結(jié)點(diǎn)。實(shí)現(xiàn)這些需要大量的代碼，實(shí)現(xiàn)的這些代碼所帶來開銷或許還會(huì)比標(biāo)準(zhǔn)二叉查找樹要多。因此后面人們想出了結(jié)合標(biāo)準(zhǔn)二叉樹來實(shí)現(xiàn)2-3樹的數(shù)據(jù)結(jié)構(gòu)，這便是紅黑樹。

實(shí)現(xiàn)紅黑二叉樹

紅黑樹是基于標(biāo)準(zhǔn)二叉樹來實(shí)現(xiàn)的，它實(shí)現(xiàn)2-3樹的關(guān)鍵點(diǎn)在于它把二叉樹的鏈接分為了紅和黑。它將兩個(gè)用紅鏈相鏈接的結(jié)點(diǎn)看為3-結(jié)點(diǎn)，而黑鏈鏈接的結(jié)點(diǎn)則視為2-結(jié)點(diǎn)。這也意味著我們完全不用去重新寫一個(gè)紅黑樹的get()方法，只需要使用標(biāo)準(zhǔn)二叉樹的get()方法就可以實(shí)現(xiàn)查找，不同點(diǎn)在于，要在put()方法中改動(dòng)一下便能夠去實(shí)現(xiàn)一個(gè)紅黑二叉查找樹。實(shí)現(xiàn)紅黑樹代碼改動(dòng)量少，但其后面的思想其實(shí)很復(fù)雜，由于篇幅的原因，對(duì)紅黑樹如何去實(shí)現(xiàn)2-3樹的三種變化的原理就不做過多描述。

首先定義結(jié)點(diǎn)

/**
 * <h3>
 *     紅黑樹的實(shí)現(xiàn),博客:https://www.cnblogs.com/qzlzzz/p/15395010.html
 * </h3>
 * @author qzlzzz
 * @since 2021/10/12
 * @version 1.0
 */
public class RedBlackBST<Key extends Comparable<Key>,Value> {
    
        
    private Node root;//根節(jié)點(diǎn)

    //<父結(jié)點(diǎn)>指向自己<子結(jié)點(diǎn)>的鏈接是黑色的
    private static final boolean RED = true;

    //<父結(jié)點(diǎn)>指向自己<子結(jié)點(diǎn)>的鏈接是黑色的
    private static final boolean BLACK = false;

    /**
     * <p>紅黑樹的結(jié)點(diǎn)定義</p>
     * @author qzlzzz
     */
    private class Node{
        
        private boolean color;//指向該結(jié)點(diǎn)的鏈接的顏色
        
        private Key key;//鍵
        
        private Value value;//值
        
        private Node left,right;//該結(jié)點(diǎn)指向左結(jié)點(diǎn)的鏈接和右結(jié)點(diǎn)的鏈接
        
        private int n;//該子樹的結(jié)點(diǎn)樹

        public Node(Key key,Value value,boolean color,int n){
            this.key = key;
            this.value = value;
            this.color = color;
            this.n = n;
        }
    }
    
}

若紅鏈接為右鏈接，使鏈接轉(zhuǎn)左。

在這里我們需要保持紅鏈接為左鏈接。但使紅鏈接保持為右鏈接也行，只不過左鏈接更好實(shí)現(xiàn)。

    /**
     * 計(jì)算紅黑樹的結(jié)點(diǎn)總數(shù),內(nèi)部調(diào)用了{(lán)@link RedBlackBST#size(Node)}
     * @return
     */
    public int size(){
        return size(root);
    }

    //計(jì)算某個(gè)子樹的結(jié)點(diǎn)總數(shù)
    private int size(Node x){
        if (x == null) return 0;
        else return x.n;
    }

    /**
     * 將紅色右鏈接變?yōu)樽箧溄?，總體有序性不變，子樹結(jié)點(diǎn)數(shù)量不變
     * @param h
     * @return
     */
    private Node rotateLeft(Node h){
        Node t = h.right;
        h.right = t.left;
        t.left = h;
        t.color = h.color;
        h.color = RED;
        t.n = h.n;//轉(zhuǎn)換后子樹的結(jié)點(diǎn)是不變的，
        h.n = size(h.left) + size(h.right) + 1;
        return t;
    }

轉(zhuǎn)換的代碼圖是這樣的:

這里的1 2 3指的是鍵的大小，并不是值，紅黑樹各個(gè)底層到根節(jié)點(diǎn)的黑鏈接總數(shù)的相同的，這符合了2-3樹中各個(gè)底層結(jié)點(diǎn)到根節(jié)點(diǎn)的距離相等。

這里將紅左鏈接轉(zhuǎn)換為右鏈接的思想是一樣的，讀者可以自己嘗試去實(shí)現(xiàn)。

判斷鏈接是否為紅鏈接

    //判斷鏈接是否為紅色，不是返回false
    private boolean isRed(Node x){
        if (x == null) return false;
        return x.color;
    }

若左右兩邊的鏈接皆為紅色，將兩邊鏈接顏色設(shè)置為黑色，并使指向自己鏈接的顏色設(shè)為紅

    /**
     * <p>若左右兩邊的鏈接皆為紅色，將兩邊鏈接顏色設(shè)置為黑色，并使指向自己鏈接的顏色設(shè)為紅</p>
     * @param x
     */
    private void changeColor(Node x){
        x.color = true;
        x.left.color = false;
        x.right.color = true;
    }

為什么要這樣呢?

其實(shí)跟上述2-3樹的第二個(gè)操作脫不開關(guān)系。當(dāng)結(jié)點(diǎn)為臨時(shí)4-結(jié)點(diǎn)時(shí)，吐出中鍵，兩邊的鍵變?yōu)閮蓚€(gè)2-結(jié)點(diǎn)，原指向臨時(shí)4-結(jié)點(diǎn)的鏈接變?yōu)樵?-結(jié)點(diǎn)中間兩邊的鏈接并指向新的2-結(jié)點(diǎn)，如果父結(jié)點(diǎn)為2-結(jié)點(diǎn)，則于原4-中鍵一起變成3-結(jié)點(diǎn)，若父節(jié)點(diǎn)是3-結(jié)點(diǎn)，則循環(huán)上述操作，由于我們要保持紅鏈接為做鏈接，中途若有右紅鏈接產(chǎn)生還需要使用rotateLeft()方法去轉(zhuǎn)換。

接下來讓我們以紅黑二叉樹實(shí)現(xiàn)符號(hào)表的get、put

    /**
     * 通過鍵來查找值，內(nèi)部調(diào)用{@link RedBlackBST#get(Node, Comparable)}
     * @param key
     * @return
     */
    public Value get(Key key){
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        return get(root,key);
    }
    
    private Value get(Node x,Key key){
        for (;;){
            if (x == null) return null;
            int cmp = key.compareTo(x.key);
            if (cmp == 0) return x.value;
            else if (cmp < 0) x = x.left;
            else x = x.right;
        }
    }

    /**
     * 插入鍵值對(duì),內(nèi)部使用{@link RedBlackBST#put(Node, Comparable, Object)}
     * @param key
     * @param value
     */
    public void put(Key key,Value value){
        if (key == null) throw new IllegalArgumentException("argument to put() is null");
        root = put(root,key,value);
        root.color = false;
    }

    private Node put(Node x,Key key,Value value){
        if (x == null) return new Node(key,value,RED,1);
        int cmp = key.compareTo(x.key);
        if (cmp == 0) {x.value = value;}
        else if (cmp < 0) x.left = put(x.left,key,value);
        else x.right = put(x.right,key,value);
        
        if (isRed(x.right) && !isRed(x.left)) x = rotateLeft(x);
        if (isRed(x.left) && isRed(x.left.left)) x = rotateRight(x);
        if (isRed(x.left) && isRed(x.right)) changeColor(x);
        
        x.n = size(x.left) + size(x.right) + 1;
        return x;
    }

至于put方法，后面的三個(gè)if語(yǔ)句則是:

當(dāng)前結(jié)點(diǎn)的右鏈接為紅色的話，將其轉(zhuǎn)為左紅鏈接。當(dāng)左右鏈接皆為紅色，調(diào)用changeColor()方法，使得其完成2-3樹的局部動(dòng)態(tài)變化,也就是上述說的2-3樹的插入新鍵，底層結(jié)點(diǎn)是3-結(jié)點(diǎn),父結(jié)點(diǎn)是2-結(jié)點(diǎn)的操作。
當(dāng)前結(jié)點(diǎn)的左鏈接，以及左鏈接的左連接都為紅色的話，說明這是一個(gè)臨時(shí)的4-結(jié)點(diǎn)，我們需要將第一個(gè)左紅鏈接轉(zhuǎn)為右紅鏈接，然后得到一個(gè)左右鏈接都為紅的子樹，調(diào)用changeRed()方法使得其完成2-3樹的局部動(dòng)態(tài)變化，也就是上述說的2-3樹的插入新鍵，底層結(jié)點(diǎn)是3-結(jié)點(diǎn),父結(jié)點(diǎn)是2-結(jié)點(diǎn)的操作。
當(dāng)左右鏈接都為紅色，調(diào)用changeColor()方法。

最后實(shí)現(xiàn)符號(hào)表的rank,select

    /**
     * 根據(jù)位置返回鍵,內(nèi)部調(diào)用{@link RedBlackBST#select(Node, int)}
     * @param k
     * @return
     */
    public Key select(int k){
        return select(root,k);
    }

    private Key select(Node x,int k){
        while(x != null){
            int t = x.left.N;
            if (t > k) x = x.left;
            else if (t < k){
                x = x.right;
                k = k - t - 1;
            }
            else return x.key;
        }
        return null;
    }

    /**
     * 根據(jù)鍵，返回該鍵的數(shù)量，內(nèi)部調(diào)用{@link RedBlackBST#rank(Node, Comparable)}
     * @param key
     * @return
     */
    public int rank(Key key){
        return rank(root,key);
    }

    private int rank(Node x,Key key){
        while (x != null){
            int cmp = key.compareTo(x.key);
            int count = x.left.N;
            if (cmp == 0) return (count < root.N ? count : 1 + root.left.N + count);
            else if (cmp < 0) x = x.left;
            else x = x.right;
        }
        return 0;
    }

最后以紅黑二叉樹的符號(hào)表實(shí)現(xiàn)完成了，讀者也可以嘗試將put()方法中的后三個(gè)語(yǔ)句放在判斷結(jié)點(diǎn)x為空的語(yǔ)句后面，有意思的是，此樹會(huì)變成一個(gè)2-3-4樹，也就說存在4-結(jié)點(diǎn)的一顆樹。