手寫紅黑樹的簡單實現(xiàn)

基于《算法》一書的紅黑樹的插入和刪除?？催^不同的教材，也有不同的實現(xiàn)方式，但是最終的結(jié)果也大致相同，感覺這個比較容易理解，就采用這種的方式來進行簡單實現(xiàn)。

定義樹節(jié)點的實體類型

private static final boolean RED = true;
private static final boolean BLACK = false;

/**
     * 紅黑樹的節(jié)點結(jié)構(gòu)
     * 保存的值，左節(jié)點，右節(jié)點以及顏色(true為紅色，false為黑色)
     * 默認(rèn)添加一個紅節(jié)點
     *
     * @param <E>
     */
static final class RedBlackTreeNode<E extends Comparable<E>> {

  E val;
  RedBlackTreeNode<E> left;
  RedBlackTreeNode<E> right;
  boolean color = RED;


  RedBlackTreeNode(E val) {
    this.val = val;
  }

}

這里簡單的定義了一下紅黑樹，并且只有節(jié)點，并不是map這樣的k-v結(jié)構(gòu)。如果定義k-v結(jié)構(gòu)到時比較的時候比較k即可。

用了泛型，并且要支持比較(繼承自Comparable)，不然無法比較大小進行插入。

然后定義了一個值，左節(jié)點和右節(jié)點，然后顏色默認(rèn)為紅色。

再增加一個構(gòu)造函數(shù)即可

定義公共方法

主要做的就是插入和刪除節(jié)點，為了方便查看是否符合添加了一個中序遍歷的打印方法

public class RedBlackTree<E extends Comparable<E>> {

    RedBlackTreeNode<E> head;
    
  public void add(E e) {
    ...
  }
    
  
  public void remove(E e){
    ...
  }
  
  public void printTree(){
    ...
  }
  
}

定義這些公共方法來對外部調(diào)用，具體實現(xiàn)可以放到私有方法中。

變換操作

在紅黑樹的變換中主要有三個：左旋，右旋，變色。接下來我們就來實現(xiàn)這三個方法。

旋轉(zhuǎn)操作可以保持紅黑樹的兩個重要性質(zhì)：有序性和完美平衡性

左旋

private RedBlackTreeNode<E> rotateLeft(RedBlackTreeNode<E> node) {
  //變換位置
  RedBlackTreeNode<E> result = node.right;
  node.right = result.left;
  result.left = node;
  //換色
  result.color = node.color;
  node.color = RED;
  return result;
}

當(dāng)右節(jié)點為紅色， 左節(jié)點為空或者黑色時，需要進行左旋操作。

首先定義一個變量存儲右節(jié)點，然后將右節(jié)點的左節(jié)點作為父節(jié)點（傳入?yún)?shù)）的右節(jié)點。這時與右節(jié)點（定義的變量）斷開了關(guān)聯(lián)。

然后將定義的變量（右節(jié)點）的左節(jié)點設(shè)置為參數(shù)節(jié)點（左節(jié)點之前已經(jīng)賦值到參數(shù)節(jié)點的右節(jié)點上）。

還需進行一步換色，將定義變量的顏色設(shè)置為父節(jié)點的顏色（不影響上一級的操作），然后將父節(jié)點設(shè)置為紅色。

將定義的變量作為父節(jié)點返回。

右旋

private RedBlackTreeNode<E> rotateRight(RedBlackTreeNode<E> node) {
  //變換位置
  RedBlackTreeNode<E> result = node.left;
  node.left = result.right;
  result.right = node;
  //變色
  result.color = node.color;
  node.color = RED;
  return result;
}

當(dāng)左節(jié)點為紅色，左節(jié)點的左節(jié)點也為紅色時，需要進行右旋操作。

這個與左旋基本類似，將左節(jié)點作為父節(jié)點返回，然后對其他節(jié)點也要確保不丟失，還有換色操作不能影響紅黑樹的特性。

換色

private void flipColor(RedBlackTreeNode<E> node) {
   node.left.color = BLACK;
   node.right.color = BLACK;
   node.color = RED;
}

當(dāng)兩個子節(jié)點都為紅色時，需要進行換色

讓兩個子節(jié)點變?yōu)楹谏?，父?jié)點變?yōu)榧t色

完成公共方法的實現(xiàn)

剛才我們在上面有提到，需要判斷節(jié)點的顏色，雖然我們在節(jié)點的類型中定義了color屬性，但是考慮到其他情況還是寫一個方法來完成判斷顏色的功能：

isRed(Node)

private boolean isRed(RedBlackTreeNode<E> node) {
   if (node == null) {
      return false;
   }
   return node.color;
}

當(dāng)節(jié)點為空時返回false即為黑色，不然判斷節(jié)點的color屬性是否為紅色。

還有一個中序打印的方法

printTree()

public void printTree() {
   print(head);
}

private void print(RedBlackTreeNode<E> node) {
   if (node == null) {
      return;
   }
   print(node.left);
   System.out.print(node.val + " ");
   print(node.right);
}

在對外部的方法中調(diào)用了內(nèi)部方法，傳入了頭結(jié)點。

由于是中序遍歷，所以需要先遍歷左節(jié)點，然后打印自己，然后遍歷右節(jié)點。這是一個遞歸操作，所以需要定義終止條件：當(dāng)節(jié)點為空時就返回。

具體實現(xiàn)

add()

public void add(E val) throws IllegalAccessException {
   if (val == null) {
      throw new IllegalAccessException("不能添加null值");
   }
   head = addVal(val, head);
   //最終將根節(jié)點設(shè)置為黑色
   head.color = BLACK;
}

private RedBlackTreeNode<E> addVal(E val, RedBlackTreeNode<E> node) {
        //達到最終的節(jié)點，如果為空則新建一個紅色的節(jié)點
        if (node == null) {
            return new RedBlackTreeNode<E>(val);
        }
        if (val.compareTo(node.val) < 0) {
            //如果小，則左節(jié)點為 新建節(jié)點返回的節(jié)點(可能會經(jīng)過調(diào)整)
            node.left = addVal(val, node.left);
        } else if (val.compareTo(node.val) > 0) {
            //如果大，則右節(jié)點為  新建節(jié)點后返回的節(jié)點(可能會經(jīng)過調(diào)整)
            node.right = addVal(val, node.right);
        } else {
            //值相等
            return node;
        }
        //判斷平衡等操作
        if (isRed(node.right) && !isRed(node.left)) {
            //右節(jié)點為紅色，左節(jié)點為空或者黑色時需要進行左旋
            node = rotateLeft(node);
        }
        if (isRed(node.left) && isRed(node.left.left)) {
            //左節(jié)點為紅色，左節(jié)點的左節(jié)點也為紅色時，需要進行右旋
            node = rotateRight(node);
        }
        if (isRed(node.left) && isRed(node.right)) {
            //當(dāng)兩個子節(jié)點都為紅色時，需要進行變色
            flipColor(node);
        }
        return node;
    }

? 在公共方法中首先進行了一個參數(shù)校驗，如果為空則無法比較所以就拋出一個異常。

然后調(diào)用私有方法進行添加節(jié)點：傳入的參數(shù)為要添加的值，樹的頭結(jié)點。

在私有方法中首先判斷了傳入的節(jié)點是否為空，如果為空則新建一個紅色節(jié)點返回。

當(dāng)不為空時進行大小判斷，判斷是添加在左子樹還是右子樹上，然后遞歸調(diào)用當(dāng)前方法，傳入要添加的值和左節(jié)點或右節(jié)點，如果相等則直接返回當(dāng)期節(jié)點即可（不是map不用重新改變value）。并且添加后可能會進行調(diào)整，所以需要重新賦值。

接下來就是判斷是否符合紅黑樹的規(guī)定，然后進行左旋，右旋，變色等操作。這時也會進行重新調(diào)整，所以需要重新賦值。

操作完成后返回到公共方法中。

在公共方法中將頭結(jié)點的顏色設(shè)置為黑色，保證紅黑樹的特性。

remove()

public void remove(E val) throws IllegalAccessException {
   if (val == null) {
      throw new IllegalAccessException("不允許null值操作");
   }
   if (head == null) {
      throw new IllegalAccessException("樹為空");
   }
   head = removeVal(val, head);
}

private RedBlackTreeNode<E> removeVal(E val, RedBlackTreeNode<E> node) throws IllegalAccessException {
   if (node == null) {
      throw new IllegalAccessException("val not exist!");
   }
   if (val.compareTo(node.val) < 0) {
      node.left = removeVal(val, node.left);
   } else if (val.compareTo(node.val) > 0) {
      node.right = removeVal(val, node.right);
   } else {
      if (node.right != null) {
         node = getRightMinNode(node);
      } else if (node.left != null) {
         node = getLeftMaxNode(node);
      } else {
         node = null;
      }
   }
  //判斷平衡等操作
  if (node != null) {
            //判斷平衡等操作
            if (isRed(node.right) && !isRed(node.left)) {
                //右節(jié)點為紅色，左節(jié)點為空或者黑色時需要進行左旋
                node = rotateLeft(node);
            }
            if (isRed(node.left) && isRed(node.left.left)) {
                //左節(jié)點為紅色，左節(jié)點的左節(jié)點也為紅色時，需要進行右旋
                node = rotateRight(node);
            }
            if (isRed(node.left) && isRed(node.right)) {
                //當(dāng)兩個子節(jié)點都為紅色時，需要進行變色
                flipColor(node);
            }
        }
   return node;
}

在公共方法中進行參數(shù)校驗，如果刪除的是null，則拋出異常。

然后當(dāng)樹為空時也不能進行刪除操作。刪除操作也可能會進行結(jié)構(gòu)修改，所以也需要進行重新賦值。

用參數(shù)與當(dāng)前節(jié)點比較，如果小則遞歸傳入左節(jié)點，如果大則遞歸傳入右節(jié)點，當(dāng)節(jié)點為空時表示要刪除的節(jié)點不再樹中，我在這里是拋出了異常，可能有些不太妥當(dāng)。

如果與當(dāng)前節(jié)點相同，則刪除當(dāng)前節(jié)點。這時就暴露了一個問題，當(dāng)當(dāng)前節(jié)點有子節(jié)點時如果進行刪除。其實這也分為幾種情況即上面代碼中的第20-26行：

  1. 當(dāng)前節(jié)點無子節(jié)點，刪除當(dāng)前節(jié)點即置為null即可。

  2. 將右子節(jié)點的最小節(jié)點作為當(dāng)前節(jié)點的替代，然后刪除這個最小節(jié)點。

    /**
 * 獲取右側(cè)樹的最小節(jié)點
 *
 * @param node
 * @return
 */
private RedBlackTreeNode<E> getRightMinNode(RedBlackTreeNode<E> node) {
   RedBlackTreeNode<E> parent = node.right;
   if (parent.left == null) {
      node.right = parent.right;
      return parent;
   }
   RedBlackTreeNode<E> result = parent.left;
   //可能有優(yōu)化的地方
   while (result.left != null) {
      parent = parent.left;
      result = parent.left;
   }
   parent.left = null;
   return result;
}

  3. 當(dāng)右節(jié)點為空時，找到左節(jié)點的最大值作為當(dāng)前節(jié)點的替代，然后刪除這個最大節(jié)點。

    private RedBlackTreeNode<E> getLeftMaxNode(RedBlackTreeNode<E> node) {
   RedBlackTreeNode<E> parent = node.left;
   if (parent.right == null) {
      node.right = parent.left;
      return parent;
   }
   RedBlackTreeNode<E> result = parent.right;
   while (result.right != null) {
      parent = parent.right;
      result = parent.right;
   }
   parent.right = null;
   return result;
}

進行替換后，需要檢查是否符合紅黑樹的特性是否需要左旋，右旋，變色等操作。

驗證

public static void main(String[] args) throws IllegalAccessException {
   RedBlackTree<Integer> redBlackTree = new RedBlackTree<Integer>();
   redBlackTree.add(1);
   redBlackTree.add(3);
   redBlackTree.add(5);
   redBlackTree.add(7);
   redBlackTree.add(9);
   redBlackTree.add(2);
   redBlackTree.add(4);
   redBlackTree.printTree();
   System.out.println();
   redBlackTree.remove(2);
   redBlackTree.printTree();
   System.out.println();
   redBlackTree.remove(11);
}

首先我們依次添加[1,3,5,7,9,2,4]。然后將樹打印，按照預(yù)期結(jié)果打印出的結(jié)果應(yīng)該是順序的1~9。然后我們刪除2節(jié)點，如果我們將插入過程畫出來會發(fā)現(xiàn)如果刪除2，則會造成1，3兩個紅節(jié)點的連接，這不符合紅黑樹的規(guī)定，所以需要進行調(diào)整。然后再次進行打印查看結(jié)果是否為有誤。

最后我們刪除一個不存在的值，看它是否會報錯。

1 2 3 4 5 7 9 
1 3 4 5 7 9 
Exception in thread "main" java.lang.IllegalAccessException: val not exist!
    at RedBlackTree.removeVal(RedBlackTree.java:33)
    at RedBlackTree.removeVal(RedBlackTree.java:38)
    at RedBlackTree.removeVal(RedBlackTree.java:38)
    at RedBlackTree.removeVal(RedBlackTree.java:38)
    at RedBlackTree.remove(RedBlackTree.java:28)
    at Test.main(Test.java:21)

通過輸出可以看出結(jié)果符合我們的要求，然后也可以通過debug的方法查看刪除2節(jié)點后的節(jié)點情況發(fā)現(xiàn)與在草稿上手畫版一致。

給出一個剛才插入的圖畫過程。

刪除2節(jié)點后的情況

本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！
博主郵箱：liunaijie1996@163.com，有問題可以郵箱交流。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 8.26+2523.5永城煤電 8.27+2000+4000+10000中國郵政 8.28+7399.66北京十薈...
    TA留柱閱讀 404評論 0贊 0
  • 將“五爺爺”送上山，入土為安后，客人都走了，樂隊散了，靈堂和大竹棚都拆了，耳朵里又只有空氣緩緩流動的“嗡嗡”之聲，...
    夢醉撈刀河閱讀 166評論 1贊 2
  • 現(xiàn)在這段時間有點容易累 一是傻逼公司 老給我弄一些傻逼事 二是身體想休息一下 今天我想說說就是以前我在中介公司一件...
    墨先山雨閱讀 194評論 0贊 0
  • 有很久都沒有去表哥家玩了，昨天他家請客，去一看。完全的三觀盡毀，家里跟垃圾場一樣，地上床上全是泥巴。 床上，亂成一...
    毒醉_閱讀 459評論 0贊 0
  • globe與geo完美結(jié)合 globe globe用于繪制3D地球，屬于echart-gl.js，本身可以進行坐標(biāo)...
    你好趙大寶閱讀 1,744評論 0贊 1

友情鏈接更多精彩內(nèi)容