美女超碰,福利片在线观看,国产精品一二三在线观看

前言

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

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

符號(hào)表有時(shí)候被稱為字典，就如同英語字典中，一個(gè)單詞對(duì)應(yīng)一個(gè)解釋，符號(hào)表有時(shí)候又被稱之為索引，即書本最后將術(shù)語按照字母順序列出以方便查找的那部分。總的來說，符號(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ì)帶來下面的問題:

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

從圖中我們可以看到，我們將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順序插入得到的樹如下圖所示:

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

從圖中我們可以看出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),將插入的鍵保存其中即可。

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

第二種情況

若插入新鍵，底層結(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)。

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

第三種情況

若插入新鍵，底層結(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)的路徑始終相等。

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

以上的三種變化是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)樽箧溄樱傮w有序性不變，子樹結(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)換的代碼圖是這樣的:

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

這里的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)換。

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

接下來讓我們以紅黑二叉樹實(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語句則是:

當(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è)語句放在判斷結(jié)點(diǎn)x為空的語句后面，有意思的是，此樹會(huì)變成一個(gè)2-3-4樹，也就說存在4-結(jié)點(diǎn)的一顆樹。

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

結(jié)尾

感謝zsh帥哥，若本文有什么需要改進(jìn)或不足的地方請(qǐng)聯(lián)系我。

本文參考了:https://algs4.cs.princeton.edu/30searching/

到此這篇關(guān)于Java實(shí)現(xiàn)紅黑樹(平衡二叉樹)的文章就介紹到這了,更多相關(guān)Java實(shí)現(xiàn)紅黑樹(平衡二叉樹)內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！

原文鏈接：https://www.cnblogs.com/qzlzzz/p/15395010.html