帶有父指針的二叉查找樹有什麼優點？

Question

直到此時，我已經實現二叉搜索樹與左，右指針，如：

template<typename T> 
struct BSTNode{ 
    BSTNode* left; 
    BSTNode* right; 
    T data; 
} 

我碰到實現中的節點也有指向父節點。你爲什麼想這麼做？什麼是折衷？

Answer 1

從一個角度來看，你的問題是有效的，因爲parent指針引入了冗餘成是在幾種情況下可以避免的結構。但是在二叉樹的情況下，這會給你帶來的巨大好處，即你可以在不記得父節點的地址的情況下向上「跳躍」一級（即從一個節點到它的父節點）。如果節點的父節點是已知的，則幾個算法（例如，獲得兩個值之間的節點數量）可以非常有效和簡單地實現。

權衡是冗餘：如果你（通過平衡樹爲例）修改樹的結構，你必須記住更新left/right和parent指針既要保證樹的一致性。

Answer 2

二叉搜索樹指的是一個相當普通類二叉樹。 對於二叉搜索樹沒有理由有父指針。

有二叉樹的更加專業化的變種，然而，在父親指針是有益的。例如，尋找AVL樹或紅黑樹。通過確保樹總是平衡的，這些專業化對樹的佈局進一步限制以實現各種目標，例如保證O(log n)在紅黑樹中查找/插入/移除的複雜性。

爲了滿足這些限制，父親指針就派上用場的時候。當然，它通過交易內存（指針）來提高速度（通過算法查找父項）。

考慮自己喜歡的書上的數據結構，看看如何以及爲什麼，或維基百科。