親ポインタを持つバイナリ検索ツリーの利点は何ですか？この時点までは

Question

は、私は次のように、左と右のポインタを二分探索木を実施してきました：

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

私はノードは、親ノードへのポインタを持っていた実装に出くわしました。なぜあなたはそれをしたいのですか？トレードオフは何ですか？

Answer 1

parentポインターが構造体に冗長性を導入し、いくつかの状況で回避できるため、1つの観点から質問が有効です。しかし、バイナリツリーの場合、親ノードのアドレスを覚えていなくても、1つ上のレベル（つまり、ノードからその親に）上がることができるという大きな利点があります。ノードの親ノードが分かっていれば、いくつかのアルゴリズム（例えば、ノード数を2つの値にするなど）を非常に効果的かつ簡単に実装できます。あなたは（ツリーのバランスをとることによって、たとえば）、ツリーの構造を変更する場合は、ツリーの一貫性を保つためにleft/rightとparentポインタの両方を更新するために覚えておく必要があります。

トレードオフが冗長です。

Answer 2

バイナリ検索ツリーは、非常に一般的なクラスのバイナリツリーを指します。 バイナリ検索ツリーの場合、親ポインタを持つ理由はありません。

ただし、親ポインタが有益なバイナリツリーの特殊なバリアントがあります。例えば、AVLツリーまたは赤い黒の木を探してください。これらの専門化は、ツリーが常に平衡であることを保証することによって、赤色の黒のツリーで検索/挿入/削除のための保証されたO(log n)の複雑さなど、さまざまな目標を達成するツリーのレイアウトにさらに制限を課します。

これらの制限を満たすために、親ポインタが便利な場合があります。もちろん、それは速度のためのメモリ（ポインタ）を取引することによって（アルゴリズムによって親を見上げる）そうする。

データ構造に関する好きな本を検討して、その理由やウィキペディアを確認してください。