java - 二分探索木の親ポインタ

Question

私は二分探索木を書いていて、親ポインタを含めたいと思っています。私が今持っている方法は、親参照がノードであることです。たとえば、私の getParent() は値ではなくノードを返します。

私の質問は、これが正しい方法なのか、それとも getParent() がノードの代わりに値を返すように親の値だけを参照する必要があるのか​​ということです。

Answer 1

ノード自体を返却することをお勧めします。値自体を保存し続けると、各ノードに 1 つではなく 2 つの値のセットが含まれるため、データ サイズが不当に大きくなり、理論的にはほぼ 2 倍になります。

Answer 2

それはあなたの要件に依存しますが、NodevalueでNodeとして維持しているようです。このようにして、必要に応じてプログラムを強化して、必要に応じてオリエンテーションを含めることができます。この方法はより柔軟です。