二分探索木:削除

二分探索木:削除

記事二分探索木:検索と挿入では、二分探索木に要素を挿入する方法と、二分探索木内の値を検索する方法について説明しました。今回は、二分探索木からノードを削除する方法について説明します。 二分探索木の削除操作 二分探索木にノードを挿入するのは比較的簡単です。しかし、ノードを削除する際には、複数の可能性に注意しなければなりません。以下の 3つのケースが発生する可能性があります。 削除されるノードには子がありません。 リーフノードには子がないので、何も気にする必要はありません。リーフノードを NULL に置き換えて、このノードに割り当てられた領域を解放することができます。 削除するノードの子(左または右の子)が 1つしかない場合。 この場合、そのノードの子を格納し、元の位置から削除します。そして、削除されたノードの元の位置に子ノードが挿入されます。

人気記事

最新記事