この記事を読んでいると、特定の方法で回転を実行し、ツリーを一方向にトラバースして要素を削除することで、ツリーの片側を取り除くことができると書かれています。
彼らが何をしようとしているのかは理解できますが、その理由はわかりません。
このタイプの削除は、単純なポストオーダー削除と比べてどのような利点がありますか?
考えられる利点の 1 つは、再帰によって使用されるメモリを節約できることですが、ツリーを 2 回走査し、1 回は回転し、次に削除するのに比べれば、オーバーヘッドは取るに足らないものだと思います。ここで何か不足していますか？
記事は、このメソッドのポイントは再帰 (およびスタック スペースの消費) を回避することであることにとどまっているようです。スタック上で何も追跡する必要なく、右に下降します。」
一般に、再帰の深さが適切であると確信できない場合は、再帰を避けることを好みます。これは、他の種類のメモリが不足するずっと前にスタック領域が不足するためです。場合によっては、システムが制限するように設計されているためです。無限再帰の原因となるエラーをキャッチするための再帰。ただし、同じパッケージ内の他のルーチンが再帰を必要とすることを既に認めている場合、これはここではあまり重要ではないと思います。また、再帰の深さはツリーの深さに依存し、バランスの取れたツリーの場合、これはおおよそノード数の対数になるため、深すぎてはなりません。