5

以下は、バイナリ検索ツリーの最小共通祖先の実装です。2 つの質問があります。

1) 時間の複雑さは O(n) であり、空間の複雑さは O(n) の最悪のケースですが、BST のバランスがとれている場合、時間と空間の両方の平均的なケースは O(logn) です。あれは正しいですか？2) バイナリ検索ツリーだけでなく、バ​​イナリ ツリーにソリューションを拡張するにはどうすればよいですか。

ご連絡をお待ちしております。

//The function findOrQueue is to enqueue all elements upto target node to a queue
public void findOrQueue(Node target, Node top, LLQueue q) {
    int cmp = target.getData().compareTo(top.getData()); 
    if(cmp == 0) {
        q.enqueue(top);
        return ;
    }
    else if (cmp < 0) {
        q.enqueue(top);
        findOrQueue(target, top.getLeftChild(),q);
    }
    else {
        q.enqueue(top);
        findOrQueue(target, top.getRightChild(),q);
   }
}

public Node LCA(Node n1, Node n2) throws QueueEmptyException {
    LLQueue q1 = new LLQueue();
    LLQueue q2 = new LLQueue();
    findOrQueue(n1,getRoot(),q1);
    findOrQueue(n2,getRoot(),q2);
    Node t = null;
    while (!q1.isEmpty() && !q2.isEmpty()) {
        Node t1 = (Node)q1.dequeue();
        Node t2 = (Node)q2.dequeue();
        if(t1.getData() != t2.getData()) {
            return t;
        }
        else t = t1;
    }
    if(q1.isEmpty() && q2.isEmpty()) 
        return null;
    else
        return t;
    }
4

1 に答える 1

0

ソリューションを一般的な二分木に拡張するための鍵は、ルートとターゲットノードを接続するパスを見つけることにあるようです。このパスを取得したら、LCA関数を簡単に変更して、最も低い共通の祖先を見つけることができます。

次の大まかな実装ではLinkedBlockingQueue、パッケージjava.util.concurrent。*とStack in java.util。*を使用しますが、他の通常のキューとスタックでもうまくいきます。このコードは、ターゲットノードがツリーに存在することを前提としています。

public static void findPath2(Node target,Node top, Stack<Node> path){
    LinkedBlockingQueue<Node> q1 = new LinkedBlockingQueue<Node>(), q2 = new LinkedBlockingQueue<Node>(),
    q3 = new LinkedBlockingQueue<Node>();
    Node n = top;
    Node parrent = null;
    while(n.getData().compareTo(target.getData())!= 0){
        parrent = n;
        if(n.right != null){
            q2.add(n.right);
            q3.add(parrent);
        }
        if(n.left != null){
            q2.add(n.left); 
            q3.add(parrent);
        }
        n = q2.remove();
        q1.add(n);
    }

    Stack<Node> s3 = new Stack<Node>(), s2 = new Stack<Node>();
    while(!q3.isEmpty()){
        s3.push(q3.remove());           
    }       
    for(int i = 1; i <= q2.size(); i++)
        s3.pop();       
    while(!s3.isEmpty())
        s2.push(s3.pop());
    while(!q1.isEmpty())
        s3.push(q1.remove());
    LinkedBlockingQueue<Node> temp = new LinkedBlockingQueue<Node>();
    while(!s2.isEmpty())
        temp.add(s2.pop());
    while(!temp.isEmpty())
        s2.push(temp.remove());
    path.push(s3.pop());
    path.push(s2.pop());
    while(!s3.isEmpty()){
        n = s3.peek();          
        while(n.getData().compareTo(path.peek().getData()) != 0 && !s3.isEmpty()){
            s3.pop();
            s2.pop();
            if(!s3.isEmpty())
                n = s3.peek();
        }
        if(!s3.isEmpty()){
            s3.pop();
            path.push(s2.pop());
        }
    }       
}
于 2013-01-08T07:15:53.520 に答える