0

2 つの子ノードを持つ BST のノードを削除しようとしています。例えば、

     |
    12
   /  \
  5    15
 / \     \
2   6    20

info=12 を含むノードを削除したい。この操作を実行するには助けが必要です。

4

2 に答える 2

5

左サブツリーの右端の子、または右サブツリーの左端の子 (この例では 6 または 15) を取得し、そのうちの 1 つをその位置に移動する必要があります。その後、削除できます。したいノード。

サブツリー内のノードの数を追跡するために何かをしている場合、通常はより大きなサブツリーからノードを選択する必要があるため、移動すると、ツリーは少なくとも開始時と同じくらいバランスが取れています。 . たとえば、この場合、バランスを維持するためには 15 よりも 6 を取得する方がよいでしょう。ただし、プレーンでバランスの取れていない BST がある場合は、その情報を簡単に入手できない可能性があります。

于 2012-12-05T05:22:41.720 に答える
0

これについては、Algorithms 第 4 版の書籍サイト ( http://algs4.cs.princeton.edu/32bst/ ) で適切な議論が行われています。

于 2012-12-05T05:27:59.187 に答える