紅黑樹 - 如何找到節點的父節點？

在紅黑樹中，旋轉時，您需要知道誰是特定節點的父節點。但是，節點只能引用右側或左側的子節點。紅黑樹 - 如何找到節點的父節點？

我想給一個節點實例變量「parent」，但正因爲如此，我認爲這樣做不值得這樣做，而且每轉更改父引用也會太複雜。

public class Node { 
    private left; 
    private right; 
    private isRed; 
    private parent; //I don't think this is good idea 
}

所以，我的解決方案是編寫findParent（）方法，使用搜索找到父。我想知道是否有其他方法來查找節點的父節點？

我的解決辦法：

樣本樹：

50 
    /\ 
    25 75

如果你想找到節點25的父母，你通過這樣的：

Node parent = findParent(Node25.value);

並返回node50。

protected Node findParent(int val) { 
     if(root == null) { 
      return null; 
     } 
     Node current = root; 
     Node parent = current; 
     while(true) { 
      if(current.val == val) { //found 
       return parent; 
      } 
      if(current == null) { //not found 
       return null; 
      } 
      parent = current; 
      if(current.val > val) { //go left 
       current = current.left; 
      } 
      else { //go right 
       current = current.right; 
      } 
     } 
    }

來源

2010-07-27 masato-san

我可能是錯的，但我認爲通常的辦法是通過母公司的調用堆棧的旋轉功能上的一個參數。 – mikera 2010-07-27 19:13:10

你應該看看libavl。正確的方法是在搜索時將祖先保存在堆棧中。 – user172818 2012-05-22 13:58:26

我想給一個節點實例變量「父」，但只是爲了這個原因，我不認爲這是值得這樣做

有您的節點有parent參考需要一個額外的指針/每個節點的參考。當需要知道給定節點的父節點時，將此與需要遍歷樹進行比較。

這是再

保持一個額外的參考，並保持高達只要您修改節點日期的成本之間的權衡。
不必遍歷樹以查找一個給定節點的父

我認爲，這兩個選項之間的選擇是有點主觀的，但我個人會選擇簡單地保持跟蹤的計算成本和複雜性parent參考。

至於你一個參考點，java.util.TreeMap實現爲一個紅黑樹包含left，right和parent引用其Entry節點。

來源

2010-07-27 19:15:46

我不認爲這些都是主觀的。如果你打算遠離擁有R-B樹，那可能是因爲你爲了追求更快的操作而願意犧牲一些東西。如果你爲了記憶而苦苦掙扎，爲什麼不使用數組呢？ – 2010-07-27 19:25:09

那麼，我認爲有一些算法，你可以說，不必維護數據結構的權衡是值得的，因爲計算複雜度的小幅增加。我個人認爲這不是其中之一。我只是想避免給出一個廣泛的答案。 – 2010-07-27 19:28:22

這對存儲父母來說比查找它更好。更新父引用並不那麼複雜。

來源

2010-07-27 19:15:06 unbeli

當你遍歷樹來到你的pivot節點時，你可以緩存前一個父節點，或者如果你需要多個級別的「undo」，你可以緩存每個遍歷節點到堆棧上。

此緩存將是您的旋轉算法的本地變量，因此它不需要樹中的更多空間或昂貴的額外遍歷。

來源

2010-07-27 19:27:44 joshperry

使用父指針是可選的。如果你放棄了父指針，那麼你將不得不使用遞歸來編寫插入/刪除操作（遞歸方法調用保存堆棧上的父信息），或者編寫一個迭代版本，在父樹向下移動時維護它自己的父級棧。

一個很好的紅黑樹的描述可以在這裏

http://adtinfo.org/

，其中包含很多rbtree實現，包括有和無父指針的描述中找到。

如果你想節省空間（這是不夠公平）的rbtree實現一個真正優秀的描述可以在這裏

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx

已用於搜索節點的描述的方法發現如果插入/刪除實現使用父級，則效率非常低。使用指針或使用遞歸。

來源

2015-10-17 21:39:29

另一種解決方案，除了父指針和再次查詢父項，是維護一個祖先堆棧。

假如有人想插入23劃分爲以下三種：

Red Black Tree

一般插入算法是：

其中23是如果它是在樹

查找節點
如果23已經存在，返回失敗
如果23不在那裏，就把它放在那裏。
根據需要運行您的重新平衡/着色程序。

現在，使用協議棧的方法，你分配一個堆棧大到足以支持每個你的樹的一級節點（我認爲2 *天花板（LOG 2（數））+ 2）應該有你覆蓋。你甚至可以保留一個分配給插入或刪除的堆棧，只要你開始插入就清除它。

所以 - 看看根。將它推入堆棧。 23大於根中的值，所以向右走。現在將節點當前節點（值21）推入堆棧。如果23在樹中，它必須在當前節點的右側。但是當前節點右側的節點是空標記。因此，應該用具有您的價值的節點替換空標記。父項是堆棧頂部的項目（最近被推送），祖父項是下一行...等等。因爲你好像在學習...... Java爲你提供了一個堆棧接口，所以你不需要開發自己的堆棧來做到這一點。只要使用他們的。

至於這是否比父指針方法更好，這似乎對我來說是有爭議的 - 爲了簡單起見，我會傾向於父指針方法，並且不需要維護輔助數據結構或廣泛使用遞歸。也就是說，任何一種方法都比在應用重新平衡/着色例程時查詢當前節點的父節點要好。

來源

2017-07-02 23:55:58

紅黑樹 - 如何找到節點的父節點？

回答

相關問題