程式師世界 >> 編程語言 >> JAVA編程 >> 關於JAVA >> 圖解紅黑樹及Java停止紅黑二叉樹遍歷的辦法

圖解紅黑樹及Java停止紅黑二叉樹遍歷的辦法

編輯：關於JAVA

圖解紅黑樹及Java停止紅黑二叉樹遍歷的辦法。本站提示廣大學習愛好者：（圖解紅黑樹及Java停止紅黑二叉樹遍歷的辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是圖解紅黑樹及Java停止紅黑二叉樹遍歷的辦法正文

紅黑樹
紅黑樹是一種數據構造與算法教室上經常提到但又不會細講的樹，也是技巧面試中常常被問到的樹，但是不管是書上照樣網上的材料，平日都比擬呆板難以懂得，能不克不及一種比擬直不雅的方法來懂得紅黑樹呢？本文將以圖形的方法來說明紅黑樹的拔出與刪除操作。
對樹構造的進修是一個遞進的進程，我們平日所接觸的樹都是二叉樹，二叉樹簡略來講就是每一個非葉子節點都有且只要兩個孩子，分離叫做左孩子和右孩子。二叉樹中有一類特別的樹叫二叉查找樹，二叉查找樹是一種有序的樹，關於每一個非葉子節點，其左子樹的值都小於它，其右子樹的值都年夜於它。比二叉查找樹更進一步的是二叉均衡樹，二叉均衡樹除包管有序外，還可以或許堅持每一個節點閣下子樹的高度相差不跨越1。罕見的均衡樹有AVL樹，Treap，紅黑樹，舒展樹，等等。
紅黑樹是一種二叉查找樹，但在每一個節點上增長一個存儲位表現節點的色彩，可所以RED或BLACK。經由過程對任何一條從根到葉子的途徑上各個節點著色方法的限制，紅黑樹確保沒有一條途徑會比其他途徑長出兩倍，因此是接近均衡的。
紅黑樹知足一下5特性質：

每一個節點是白色或許黑色；
根節點是黑色；
每一個葉子節點NIL是黑色；
假如一個節點是白色，則它的兩個孩子都是黑色；（每條途徑上不克不及有兩個持續的白色節點）
任一節點到其一切子孫葉子節點NIL的途徑上包括雷同數量的黑色節點。

留意，在紅黑樹中，把傳統二叉樹的葉子節點的孩子指向NIL，稱NIL為紅黑樹中的葉子節點。NIL節點中含有指向父節點的指針，這能夠是須要把null改成NIL的緣由。

1、拔出操作
起首以二叉查找樹的拔出方法（拔出的新節點都在葉子節點處）拔出新的節點，並將其繪為白色。然後再重繪其色彩或扭轉以堅持紅黑樹的性質，調劑分為以下三種情形：
1 新節點N沒有父節點（即位於根上）
將新節點N繪為黑色。

2 新節點N的父節點P為黑色
不消調劑。

3 新節點N的父節點P為白色
由於紅黑樹不許可有兩個持續的白色節點（性質4），所以須要調劑，依據N的叔父節點色彩分為兩種情形：（我們以 N的父節點P為左孩子為例，P為右孩子的情形相似，不再胪陳）
3.1 新節點N的叔父節點U為白色
將新節點N的父節點P和叔父節點U都繪為黑色，將其祖父節點G繪為白色，如許包管從G到每一個null節點的途徑上所包括的黑色節點個數與本來堅持分歧。但因為我們把G釀成了白色，假如G的父親也是白色，便可能招致持續兩個白色節點（違背性質4），所以，須要從新檢討G能否違背了紅黑樹性質。

3.2 新節點N的叔父節點U為黑色
若新節點N是其父節點P的左孩子：將其父節點P繪為黑色，祖父節點G繪為白色，然後對G停止一次右扭轉。

若新節點N是其父節點P的右孩子：對其父節點停止一次左扭轉，成績轉化為左孩子的情形。

2、刪除操作
《算法導論》和維基百科上的做法都是，當刪除一個黑色節點D時，把D的黑色“下推”至其子節點C，也就是說C除自己的色彩外多了一重額定的黑色，然後赓續把這重額定的黑色沿樹上移，直到碰著一個白色節點，把其變成黑色以包管途徑上黑色節點數量不變，或許移到樹的根部，如許一切途徑上的黑色節點數量都減一，堅持相等。上移進程中能夠須要扭轉和修正一些節點的色彩，以包管途徑上黑色節點數量不變。
這類做法能夠有益於代碼的完成（可用迭代的方法），但卻未便於懂得（小我以為）。本著懂得優先的目標，我依據被刪除節點D的孩子能否為NIL做以下分類：
1 被刪除節點D的兩個孩子都是NIL
1.1 被刪除節點D是白色
用NIL調換D便可。

1.2 被刪除節點D是黑色（我們以D是左孩子為例）
1.2.1 被刪除節點D的兄弟節點B的兩個孩子都為NIL
將D的兄弟節點B繪為白色，父節點P繪為黑色。

圖中半紅半黑表現該節點能夠為白色，也能夠為黑色。假如P本來是白色，如許修正後途徑上的黑色節點數量和刪除D之前一樣；假如P本來是黑色，那末刪除D後會招致途徑上黑色節點的數量比刪除前少了一個，所以還需持續檢討經由P的途徑上黑色節點數量的轉變能否影響了紅黑樹的性質。
1.2.2 被刪除節點D的兄弟節點B有一個孩子不為NIL
這個孩子必定是白色的，不然從D的父節點到各個葉子節點的途徑上黑色節點的數量就會不等（違背性質5）。
若這個孩子為右孩子，將B的這個右孩子繪為黑色，B繪為其父節點P本來的色彩，P繪為黑色，然後對P停止一次左扭轉。

若這個孩子為左孩子，將B的這個左孩子繪為黑色，B繪為白色，然後對B停止一次右扭轉，成績轉化為右孩子的情形。

1.2.3 被刪除節點D的兄弟節點B的兩個孩子都不為NIL
若B為白色，則B的兩個孩子必定為黑色。將B繪為黑色，B的左孩子繪為白色，然後對P停止一次左扭轉。

若B為黑色，則B的兩個孩子必定為白色。將B的父節點P繪為黑色，B的右孩子繪為黑色，B繪為其父節點P本來的色彩，然後對P停止一次左扭轉。

2 被刪除節點D的兩個孩子都不是NIL
依照二叉查找樹刪除節點的辦法找到D的後繼節點S，交流D和S的內容（色彩堅持不變），被刪除節點變成S，假如S有不為NIL的節點，那末持續用S的後繼節點調換S，直到被刪除節點的兩個孩子都為NIL，成績轉化為被刪除節點D的兩個孩子都為NIL的情形。
3 被刪除節點D有一個孩子不是NIL
這個孩子C必定是白色節點，不然從D到各個NIL節點的途徑上的黑色節點數量就會分歧（違背性質5）。
交流D和C的內容（色彩堅持不變），被刪除節點變成C，成績轉化為被刪除節點D的兩個孩子都為NIL的情形。

二叉樹的遍歷
二叉樹的遍歷有三種：前序遍歷、中序遍歷和後序遍歷。每種遍歷的完成又有遞歸和迭代兩種，這篇文章我們來評論辯論若何用比擬優雅的代碼來完成二叉樹的遍歷。
起首我來界說一個二叉樹的節點：

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  
  public TreeNode(int x) {
    val = x;
  }
}

1、前序遍歷（Preorder Traversal）
簡略來說，前序遍歷就是先拜訪父節點，再拜訪左孩子，最初拜訪右孩子，即以父、左、右的次序來遍歷。
遞歸完成異常簡略，代碼以下：

public class Solution {
  List<Integer> result = new ArrayList<Integer>();
  
  public List<Integer> preorderTraversal(TreeNode root) {
    dfs(root);
    return result;
  }
  
  private void dfs(TreeNode root) {
    if (root == null) {
      return;
    } 
    result.add(root.val);
    dfs(root.left);
    dfs(root.right);
  }
}

迭代完成須要借助一個棧，存儲沒被拜訪的右節點，代碼以下：

public class Solution {
 
  public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    
    if (root == null) {
      return result;
    }
    
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
      TreeNode curr = stack.pop();
      result.add(curr.val);
      
      if (curr.right != null) {
        stack.push(curr.right);
      }
      if (curr.left != null) {
        stack.push(curr.left);
      }
    }
    
    return result;
  }
}

2、中序遍歷（Inorder Traversal）
簡略來說，中序遍歷就是先拜訪左孩子，再拜訪父節點，最初拜訪右孩子，即以左、父、右的次序遍歷。
遞歸代碼也比擬輕易，以下所示：

public class Solution {
 
  public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    recurse(root, result);
    return result;
  }
  
  private void recurse(TreeNode root, List<Integer> result) {
    if (root == null) return;
    recurse(root.left, result);
    result.add(root.val);
    recurse(root.right, result);
  }
}

下面這類寫法有別於前序遍歷的遞歸代碼，前序遍歷的遞歸我們應用了成員變量來存儲遍歷的成果，這裡我們應用辦法參數來保留遍歷的成果。兩種寫法都可以，愛好哪一種就應用哪一種。
中序遍歷的迭代完成沒有前序遍歷那末簡略，固然也須要借助一個棧，但迭代終止的前提卻有所分歧。想象一下，關於一棵二叉樹，我們最早拜訪的節點是其最右邊的節點，我們固然可以經由過程一個 while 輪回達到其最右邊，可是當我們回退時，我們若何曉得某個節點的左孩子能否曾經拜訪過了？我們應用一個 curr 變量記載以後拜訪的節點，當我們把一棵子樹的右節點都拜訪終了時，我們就該回退該子樹的父節點了，而此時 curr 為 null，所以我們可以以此來辨別一個節點的左子樹能否已被拜訪過。代碼以下：

public class Solution {
  
  public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode curr = root;
    
    while (curr != null || !stack.isEmpty()) {
      while (curr != null) {
        stack.push(curr);
        curr = curr.left;
      }
      curr = stack.pop();
      result.add(curr.val);
      
      curr = curr.right;
    }
    
    return result;
  }
}

3、後序遍歷（Postorder Traversal）
簡略來說，後序遍歷就是先拜訪左孩子，在拜訪右孩子，最初拜訪父節點，即以左、右、父的次序遍歷。
模仿中序遍歷，可以很輕易地寫出後序遍歷的遞歸完成：

public class Solution {
 
  public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    recurse(root, result);
    return result;
  }
  
  private void recurse(TreeNode root, List<Integer> result) {
    if (root == null) return;
    recurse(root.left, result);
    recurse(root.right, result);
    result.add(root.val);
  }
}

後序遍歷的迭代，也須要一個標識要辨別一個節點的閣下孩子能否曾經拜訪過了，假如沒有，則順次拜訪其閣下孩子，假如拜訪過了，則拜訪該節點。為此，我們用一個 pre 變量來表現上一個拜訪的節點，假如上一個拜訪的節點是以後節點的左孩子或右孩子，那末解釋以後節點的閣下孩子曾經拜訪過了，那末便可以拜訪該節點了，不然，則須要進入閣下孩子順次拜訪。代碼以下：

public class Solution {
 
  public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<Integer>();
    
    Stack<TreeNode> stack = new Stack<TreeNode>();
    if (root != null) stack.push(root);
    
    TreeNode pre = root;
    
    while (!stack.isEmpty()) {
      TreeNode curr = stack.peek();
      if (curr.left == pre || curr.right == pre || (curr.left == null && curr.right == null)) {
        result.add(curr.val);
        stack.pop();
        pre = curr;
      } else {
        if (curr.right != null) stack.push(curr.right);
        if (curr.left != null) stack.push(curr.left);
      }
    }
    
    return result;
  }
}

後序遍歷的迭代還有別的一種比擬簡略的完成，我們曉得先序遍歷的次序是父、左、右，爾後序遍歷的次序是左、右、父，那末假如我們把先序遍歷稍作修正，改成父、右、左的次序，那末就恰好與後序遍歷的次序相反了，以如斯次序拜訪完，最初我們對拜訪成果做個反轉便可以了。而先序遍歷的迭代完成絕對來講比擬輕易，模仿下面寫法我們可以以下完成：

public class Solution {
 
  public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<Integer>();
    
    Stack<TreeNode> stack = new Stack<TreeNode>();
    if (root != null) stack.push(root);
    
    while (!stack.isEmpty()) {
      TreeNode curr = stack.pop();
      result.add(curr.val);
      if (curr.left != null) stack.push(curr.left);
      if (curr.right != null) stack.push(curr.right);
    }
 
    Collections.reverse(result);
    
    return result;
  }
}

4、總結
三種遍歷的遞歸完成都很輕易。前序遍歷的迭代完成最好寫，只須要一個棧就好；中序遍歷最難，輪回前提除斷定棧能否為空，還要斷定以後節點能否為空，以表現能否左子樹曾經遍歷終了；後續遍歷的迭代假如轉化為前序遍歷的迭代，就輕易許多，不然，也須要記載上一個拜訪的節點，以表現以後節點的閣下子樹能否曾經拜訪終了。