基于紅黑樹插入操作原理及java實(shí)現(xiàn)的示例分析

這篇文章主要介紹基于紅黑樹插入操作原理及java實(shí)現(xiàn)的示例分析，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名注冊、雅安服務(wù)器托管、營銷軟件、網(wǎng)站建設(shè)、阿圖什網(wǎng)站維護(hù)、網(wǎng)站推廣。

紅黑樹是一種二叉平衡查找樹，每個(gè)結(jié)點(diǎn)上有一個(gè)存儲(chǔ)位來表示結(jié)點(diǎn)的顏色，可以是RED或BLACK。

紅黑樹具有以下性質(zhì)：

(1) 每個(gè)結(jié)點(diǎn)是紅色或是黑色

(2) 根結(jié)點(diǎn)是黑色的

(3) 如果一個(gè)結(jié)點(diǎn)是紅色的，則它的兩個(gè)兒子都是黑色的

(4) 對于每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)

通過紅黑樹的性質(zhì)，可以保證所有基于紅黑樹的實(shí)現(xiàn)都能保證操作的運(yùn)行時(shí)間為對數(shù)級別（范圍查找除外。它所需的額外時(shí)間和返回的鍵的數(shù)量成正比）。

Java的TreeMap就是通過紅黑樹實(shí)現(xiàn)的。

紅黑樹的操作如果不畫圖很容易搞糊涂，下面通過圖示來說明紅黑樹的插入操作。

插入一個(gè)紅色的節(jié)點(diǎn)到紅黑樹中之后，會(huì)有6種情況：圖示中N表示插入的節(jié)點(diǎn)，P表示父節(jié)點(diǎn)，U表示叔叔節(jié)點(diǎn)，G表示祖父節(jié)點(diǎn)，X表示當(dāng)前操作節(jié)點(diǎn)

 

代碼如下：

public class RedBlackBST<Key extends Comparable<Key>, Value> {
 private Node root;
 private static final boolean RED = true;
 private static final boolean BLACK = false;
 private class Node{
  private Key key; //鍵
  private Value val; //值
  private Node left, right, parent; //左右子樹和父節(jié)點(diǎn)
  private boolean color; //由其父節(jié)點(diǎn)指向它的鏈接的顏色
  
  public Node(Key key, Value val,Node parent, boolean color){
   this.key = key;
   this.val = val;
   this.color = color;
  }
 }
 
 public Value get(Key key){
  Node x = root;
  while(x!=null){
   int cmp = key.compareTo(x.key);
   if(cmp < 0 ) x = x.left;
   else if(cmp > 0) x = x.right;
   else return x.val;
  }
  return null;
 }
 
 public void put(Key key, Value val){
  if(root==null) { //如果是根節(jié)點(diǎn)，就將節(jié)點(diǎn)新建為黑色
   root = new Node(key,val,null,BLACK);
   return;
  }
  //尋找合適的插入位置
  Node parent = null;
  Node cur = root;
  while(cur!=null) {
   parent = cur;
   if(key.compareTo(cur.key)>0) cur=cur.right;
   else cur = cur.left;
  }
  Node n = new Node(key,val,parent,RED); //普通的新建節(jié)點(diǎn)為紅色
  //將新節(jié)點(diǎn)插入parent下
  if(key.compareTo(parent.key) > 0) parent.right = n;
  else parent.left = n;
  //插入新節(jié)點(diǎn)后要調(diào)整樹中部分節(jié)點(diǎn)的顏色和屬性來保證紅黑樹的特征不被破壞
  fixAfterInsertion(n); 
 }
 private Node parentOf(Node x) {
  return (x==null ? null : x.parent);
 }
 private boolean colorOf(Node x) {
  return (x==null ? BLACK : x.color);
 }
 private Node leftOf(Node x) {
  return (x==null ? null : x.left);
 }
 private Node rightOf(Node x) {
  return(x==null ? null : x.right);
 }
 private void setColor(Node x, boolean color) {
  if(x!=null)
   x.color = color;
 }
 
 private void fixAfterInsertion(Node x) {
  while(x!=null && colorOf(parentOf(x)) == RED) {
   Node grandPa = parentOf(parentOf(x));
   Node parent = parentOf(x);
   if(parent == leftOf(grandPa)) {//case 1 || case2 || case3
    Node uncle = rightOf(grandPa);
    if(colorOf(uncle) == RED) {//case1, uncle is red
     setColor(parent,BLACK); //父節(jié)點(diǎn)置黑
     setColor(uncle, BLACK); //叔叔節(jié)點(diǎn)置黑
     setColor(grandPa,RED); //祖父節(jié)點(diǎn)置紅
     x = grandPa; //因?yàn)樽娓腹?jié)點(diǎn)由黑轉(zhuǎn)紅，故要重新調(diào)整父節(jié)點(diǎn)及其祖先的紅黑屬性
    }else {//case2 || case3,uncle is black
     if(x==rightOf(parent)) { //case2
      x = parent;
      rotateLeft(x);
     }
     //case3
     setColor(parent,BLACK);
     setColor(grandPa, RED);
     rotateRight(grandPa);
    }
    
   }else {//case4 || case 5 || case6
    Node uncle = leftOf(grandPa);
    if(colorOf(uncle) == RED) { //case4 || case5 || case6
     setColor(parent,BLACK);
     setColor(uncle, BLACK);
     setColor(grandPa,RED);
     x = grandPa;
    }else{ //case5 || case6, uncle is black
     if(x==leftOf(parent)) { //case5
      x = parent;
      rotateRight(x);
     }
     //case6
     setColor(parent,BLACK);
     setColor(grandPa, RED);
     rotateLeft(grandPa);
    }
   }
  }
 }
 private void rotateLeft(Node x) {
  if(x==null) return;
  Node y = x.right;
  x.right = y.left;
  if(y.left!=null)
   y.left.parent = x;
  y.left = x;
  y.parent = x.parent;
  if(x.parent == null) {
   root = y;
  }
  else if(x.parent.left == x) {
   x.parent.left = y;
  }else {
   x.parent.right = y;
  }
  x.parent = y;
 }
 private void rotateRight(Node x) {
  if(x==null) return;
  Node y = x.left;
  x.left = y.right;
  if(y.right != null)
   y.right.parent = x;
  y.right = x;
  y.parent = x.parent;
  if(x.parent == null) {
   root = y;
  }else if(x.parent.left==x) {
   x.parent.left = y;
  }else {
   x.parent.right=y;
  }
  x.parent = y;
 }
 
}

上面的rotateLeft和rotateRight有必要畫個(gè)圖示：

以上是“基于紅黑樹插入操作原理及java實(shí)現(xiàn)的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

文章名稱：基于紅黑樹插入操作原理及java實(shí)現(xiàn)的示例分析
文章URL：http://bm7419.com/article28/gijijp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號、Google、外貿(mào)建站、動(dòng)態(tài)網(wǎng)站、做網(wǎng)站、網(wǎng)站設(shè)計(jì)公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)