1

すべてのキーが一意である二分探索木を考えてみましょう。ノードには親ポインタがありません。
最大 n/2 のマークされたノードがあります。
O(n 2 ) 時間でそれらすべてを削除できます (postorder traversal を使用し、O(n) でマークされたノードの削除に遭遇した場合)。しかし、それは不適切です。マークされたすべてのノードをO(n)時間で削除するアルゴリズムが必要です。ありがとう。

EDIT削除後、ノードの順序を変更しないようにする必要があります。
EDIT-2したがって、通常の削除（左のサブツリーで最も右のノードを見つけて、削除するノードと交換する）を使用して、マークされた各ノードを削除したように見えるはずです。

4

3 に答える 3

6

多くの方法がありますが、これは正しく理解しやすく、副作用として完全にバランスの取れたツリーを提供する方法です。ただし、線形の余分なスペースが必要です。

  1. サイズNからマークされたノードの数を引いた配列を作成します（マークされたノードの数がわからず、チェックしたくない場合はN）。
  2. マークされた要素をスキップして、順序どおりにトラバーサルすることにより、要素を配列内に順番に配置します。これには線形の時間がかかり、スタックスペースは木の高さに比例します。
  3. アレイを使用してツリーをトップダウンで再構築します。配列のmid要素が新しいルートになり、左サブ配列のmid要素が新しい左子になり、右サブ配列のmid要素が新しい右サブ子になります。再帰的に繰り返します。これには、線形時間と対数スタックスペースが必要です。

更新：マークされた要素をスキップすると言うのを忘れましたが、それは明らかでしたね？;）

于 2012-05-08T15:34:01.183 に答える
2

私はそれを行う方法を見つけました！

  • 順序のないトラバーサルを使用します。
  • 関数を再帰的に呼び出す前に、ノードを削除する必要があるかどうかを確認します。
  • 削除するノードが見つかったら、フラグtoFindMaxを立てて、左側のサブツリーの右端のノードを検索します。
  • 削除する別のノードが見つかった場合は、すべての変数をスタックにプッシュし、ノードが削除されたときにそれらをポップします。
  • 左側のサブツリーで最大値が見つかったら、そのサブツリーとその親への参照を保存します。
    そして、削除する最初のノードに再帰的に戻ると、それを削除します（最大値と交換します）。 
static class LinearDeletion {

    public static Node MIN_VALUE = new Node(Integer.MIN_VALUE);;
    boolean toFindMax = false;
    Node parentOfMax = null;
    Node max = MIN_VALUE;
    Stack<Object> stack = new Stack<>();

    public void perform(Node x, Node parent) {

        if (x.isToDelete) {
            stack.push(toFindMax);
            stack.push(parentOfMax);
            stack.push(max);

            toFindMax = true;
            parentOfMax = null;
            max = MIN_VALUE;

            if (x.left != null) {
                perform(x.left, x);
            }


            if (x.left == null) { //deletion of the node
                if (parent.left == x) {
                    parent.left = x.right;
                } else {
                    parent.right = x.right;
                }
            } else {
                if (x.right == null) {
                    if (parent.left == x) {
                        parent.left = x.left;
                    } else {
                        parent.right = x.left;
                    }
                } else {
                    x.key = max.key;
                    x.isToDelete = max.isToDelete;
                    if (parentOfMax != x) {
                        parentOfMax.right = max.left;
                    } else {
                        x.left = max.left;
                    }
                }
            } // end of deletion
            max = (Node) stack.pop();
            parentOfMax = (Node) stack.pop();
            toFindMax = (boolean) stack.pop();
            if (toFindMax) { // check if the current node is the maximum
                if (x.key > max.key) {
                    max = x;
                    parentOfMax = parent;
                }
            }

            if (x.right != null) {
                perform(x.right, x);
            }

        } else {

            if (x.left != null) {
                perform(x.left, x);
            }

            if (toFindMax) {
                if (x.key > max.key) {
                    max = x;
                    parentOfMax = parent;
                }
            }

            if (x.right != null) {
                perform(x.right, x);
            }
        }
    }
}
于 2012-05-09T13:26:37.980 に答える
1

postorder トラバーサルが O(n 2 )になる理由がわかりません。単一ノードの削除が O(n) である理由は、ノードを見つけるためにツリーをトラバースする必要があるためです。これは O(n) 操作です。ただし、ノードが見つかったら、O(1) 時間で削除できます。*したがって、O(n) 時間の 1 回のトラバーサルで、O(n) 個のマークされたすべてのノードを削除できます。

*バランスの取れたツリーを維持する必要がある場合を除きます。ただし、それを要件としてリストしていません。

編集@njlarsson がコメントで正しく指摘しているように、削除操作は通常、ノードが見つかった後でも O(1) ではありません。ただし、削除するノードにアクセスする前に左右のサブツリーがトラバースされるため、サブツリーのトラバース中に追加コストなしでサブツリーの最小 (または最大) 要素を取得できます。これにより、O(1) 削除が可能になります。

于 2012-05-08T15:22:35.687 に答える