3

2 週間前に、挿入、削除、キーの検索、および 3 つの要素の範囲の合計の取得などの基本的な機能を可能にするスプレイ ツリーの実装を完了しました。この実装は、この質問の参照として、または好奇心から見つけることができます。

追加のタスクとして (オプションで期限が過ぎています。私はこれを成績のためではなく、「Google で検索」するのが容易ではない有用なデータ構造であると信じているため、これを解決しています)、Rope データ構造を実装するように依頼されました。文字列を操作して、文字列が "warlock" で指定されたキーが 0 2 2 の場合、文字列は "lowarck" になります (0 2 は部分文字列 "war" であり、"lock" は "war" を削除した後に残ったものであり、挿入します2 文字目以降は "lo"+"war"+"ck" になります)。これは 1 つのクエリにすぎませんが、30 万文字の長さの文字列に対して最大 10 万のクエリになる可能性があるため、単純なソリューションは機能しません。

私の最初の疑問は、ツリーの初期化についてです(要点を読んだ人のために、ほとんどの人にとって理解しやすいように、頂点の代わりにノードを使用します)。

これは Node クラスと NodePair クラスです。

class Node {
        char key;
        int size;
        Node left;
        Node right;
        Node parent;

        Node(char key, int size, Node left, Node right, Node parent) {
            this.key = key;
            this.size = size;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
    }

class NodePair {
        Node left;
        Node right;
        NodePair() {
        }
        NodePair(Node left, Node right) {
            this.left = left;
            this.right = right;
        }
    }

その後、次の方法でツリーを作成します。

StringBuffer sb = new StringBuffer(br.readLine());
Node left=null;
for (int i=0;i<sb.length();i++){
    root=new Vertex(sb.charAt(i),  i+1, left, null, null);
    if (i!=sb.length()-1){
        left=root;
    }
}

これにより、文字列の最初の文字 (node.key として) の node.size が 1 で、一番左の子になる非常に不均衡なツリーが作成されます。文字列の最後の文字は、size=sb.length() のルートです。

これが正しく初期化されているかどうかは完全にはわかりません。キーとサイズを指定して inorder traversal print を実行したところ、文字列全体がサイズ順で取得されました。これは私が期待していたものです。

その後、Update メソッドを次のように変更しました。

void update(Node v) {
        if (v == null) return;
        v.sum = v.key + (v.left != null ? v.left.sum : 0) + (v.right != null ? v.right.sum : 0);
        if (v.left != null) {
            v.left.parent = v;
        }
        if (v.right != null) {
            v.right.parent = v;
        }
    }

これに：（CLRSの章14.1に基づく）

void update(Node v) {
    if (v == null) return;
    v.size = 1 + (v.left != null ? v.left.size : 0) + (v.right != null ? v.right.size : 0);
    if (v.left != null) {
        v.left.parent = v;
    }
    if (v.right != null) {
        v.right.parent = v;
    }
}

次に、オリジナルの find メソッド:

NodePair find(Node root, int key) {
        Node v = root;
        Node last = root;
        Node next = null;
        while (v != null) {
            if (v.key >= key && (next == null || v.key < next.key)) {
                next = v;
            }
            last = v;
            if (v.key == key) {
                break;
            }
            if (v.key < key) {
                v = v.right;
            } else {
                v = v.left;
            }
        }
        root = splay(last);
        return new NodePair(next, root);
    }

これに：（CLRS Chapter 14.1のOrder Statistics-SELECTに基づく）

Node find(Node r, int k){
  int s = r.left.size + 1;
  if (k==s) return r;
  else if (k < s) {
     return find(r.left,k);
  }
  return find(r.right,k-s);
}

ただし、ご覧のとおり、このメソッドがノードを返すのに対し、元の検索は NodePair を返すため、この時点で既に問題があります。インストラクターによるNodePairの説明は次のとおりです。

結果と新しいルートのペアを返します。見つかった場合、結果は指定されたキーを持つノードへのポインターです。それ以外の場合、結果は最小の大きなキー (順序の次の値) を持つノードへのポインターです。キーがツリー内のすべてのキーよりも大きい場合、結果は null になります。

Find メソッドを使用して分割するノードを探すため、これは分割メソッドを複雑にします。これに加えて、私はこの find メソッドで NullPointerException を取得しており、他の学生から、他のエラーを回避するには非再帰バージョンを使用する必要があることを理解しているため、基本的には OS-Select の非再帰バージョンを実装する必要があります。以前の find メソッドとして NodePair を使用するか、分割メソッドを次のように変更します。

NodePair split(Node root, int key) {
    NodePair result = new NodePair();
    NodePair findAndRoot = find(root, key);
    root = findAndRoot.right;
    result.right = findAndRoot.left;
    if (result.right == null) {
        result.left = root;
        return result;
    }
    result.right = splay(result.right);
    result.left = result.right.left;
    result.right.left = null;
    if (result.left != null) {
        result.left.parent = null;
    }
    update(result.left);
    update(result.right);
    return result;
}

ご覧のとおり、find メソッドは NodePair の findAndRoot に割り当てられています。OS-Select の非再帰への変換に加えて、私の主な問題は、以前の find メソッドと split メソッドで NodePair が使用される方法を理解することだと思います。

最後に、これはツリーとキーを受け取り、それらを操作するメソッドの実装です。

 Node stringManip(Node v, int i, int j, int k){
    Node left;
    Node right;
    NodePair middleRight =split(v,j+1);
    left=middleRight.left;
    right=middleRight.right;
    NodePair leftMiddle = split(left,i);
    Node start = leftMiddle.left;
    Node substr = leftMiddle.right;
    Node tmp = merge(start, right);
    NodePair pairString = split(tmp,k+1);
    Vertex fLeft =pairString.left;
    Vertex fRight = pairString.right;
    root = merge(merge(fLeft,substr),fRight);
    root = splay(root);
    update(root);
    return root;
}

私のコードからわかるように、私はプログラミングを学び始めて 5 か月しか経っていない初心者であり、Java を選択したので、収集した情報から、このタイプのデータ構造はより中級であることがわかります。エキスパートレベル（以前の splay treeを実装できたことにすでに驚いています。ですから、回答で私の初心者レベルを考慮してください。

PD: これは非再帰的な OS-Select の疑似コード バージョンですが、まだ NullPointerException があります。

OS-SELECT(x, i)
    while x != null
        r <- size[left[x]]+1
        if i = r
            then return x
        elseif i < r
            x = left[x]
        else
            x = right[x]
            i = i - r
4

0 に答える 0