4

これが私のコードです。ツリー全体をトラバースしてから、各ノードで検索を行っています。find()O(log n) かかるので、プログラム全体で O(n log n) 時間かかります。

このプログラムを実装するためのより良い方法はありますか? 私は時間の複雑さの観点からだけでなく、一般的にも優れていると言っています。これをどのように実装するのが最善ですか？

public boolean searchNum(BinTreeNode node, int num) {
    //validate the input

    if (node == null) {
        return false;
    }
    // terminal case for recursion

    int result = num - node.item;
    //I have a separate find() which finds if the key is in the tree
    if (find(result)) {
        return true;
    }
    return seachNum(node.leftChild, num) || searchNum(node.rightChilde, num);

}

public boolean find(int key) {

    BinTreeNode node = findHelper(key, root);
    if (node == null) {
        return false;
    } else {
        return true;
    }
}


private BinTreeNode findHelper(int key, BinTreeNode node) {
    if (node == null) {
        return null;
    }
    if (key == node.item) {
        return node;
    } else if (key < node.item) {
        return findHelper(key, node.leftChild);
    } else {
        return findHelper(key, node.rightChild);
    }
}
4

6 に答える 6

9

二分探索木の合計で値になる 2 つのノードを見つけることは、並べ替えられた配列で合計して値になる 2 つの要素を見つけるのと同様の方法で行うことができます。

配列が小さいものから大きいものに並べ替えられている場合、2 つのポインターを保持します。1 つは最初から、もう 1 つは最後から始まります。ポインターが指す 2 つの要素の合計がターゲットよりも大きい場合は、右のポインターを左に 1 つ移動し、合計がターゲットよりも小さい場合は、左のポインターを右に 1 つ移動します。最終的に、2 つのポインターは、合計がターゲット値になる 2 つの要素を指すか、中間で一致します。

boolean searchNumArray(int[] arr, int num) {
    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == num) {
          return true;
        } else if (sum > num) {
          right--;
        } else {
          left++;
        }
    }
    return false;
}

二分探索木を順番に走査すると、ソートされた配列になります。したがって、同じ考え方を二分探索木に適用できます。

次のコードは、双方向から順番にトラバーサルを繰り返します。トラバーサルにはスタックが使用されているため、時間計算量は O(n) で、空間計算量は O(h) です。ここで、h はバイナリ ツリーの高さです。

class BinTreeIterator implements Iterator<BinTreeNode> {
    Stack<BinTreeNode> stack;
    boolean leftToRight;

    public boolean hasNext() {
        return !stack.empty();
    }

    public BinTreeNode next() {
        return stack.peek();
    }

    public void remove() {
        BinTreeNode node = stack.pop();
        if (leftToRight) {
            node = node.rightChild;
            while (node.rightChild != null) {
                stack.push(node);
                node = node.rightChild;
            }
        } else {
            node = node.leftChild;
            while (node.leftChild != null) {
                stack.push(node);
                node = node.leftChild;
            }
        }
    }

    public BinTreeIterator(BinTreeNode node, boolean leftToRight) {
        stack = new Stack<BinTreeNode>();
        this.leftChildToRight = leftToRight;

        if (leftToRight) {
            while (node != null) {
                stack.push(node);
                node = node.leftChild;
            }
        } else {
            while (node != null) {
                stack.push(node);
                node = node.rightChild;
            }
        }            
    }
}



public static boolean searchNumBinTree(BinTreeNode node, int num) {
    if (node == null)
        return false;

    BinTreeIterator leftIter = new BinTreeIterator(node, true);
    BinTreeIterator rightIter = new BinTreeIterator(node, false);

    while (leftIter.hasNext() && rightIter.hasNext()) {
        BinTreeNode left = leftIter.next();
        BinTreeNode right = rightIter.next();
        int sum = left.item + right.item;
        if (sum == num) {
            return true;
        } else if (sum > num) {
            rightIter.remove();
            if (!rightIter.hasNext() || rightIter.next() == left) {
                return false;
            }
        } else {
            leftIter.remove();
            if (!leftIter.hasNext() || leftIter.next() == right) {
                return false;
            }
        }
    }

    return false;
}
于 2013-09-20T01:21:22.103 に答える
1

Chen Pang はすでに完璧な答えを出しています。ただし、今日同じ問題を試していたので、次の解決策を思い付くことができました。誰かに役立つかもしれないので、ここに投稿します。

アイデアは以前のソリューションと同じですが、2 つのスタック (1 つは inorder(stack1) に続き、もう 1 つは逆の inorder order(stack2) に続きます) でそれを行っているだけです。BST の左端と右端のノードに到達したら、それらを比較することができます。

合計が必要な値よりも小さい場合は、スタック 1 からポップアウトし、そうでない場合はスタック 2 からポップします。以下は、同じの Java 実装です。

public int sum2(TreeNode A, int B) {
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    TreeNode cur1 = A;
    TreeNode cur2 = A;

    while (!stack1.isEmpty() || !stack2.isEmpty() ||
            cur1 != null || cur2 != null) {
        if (cur1 != null || cur2 != null) {
            if (cur1 != null) {
                stack1.push(cur1);
                cur1 = cur1.left;
            }

            if (cur2 != null) {
                stack2.push(cur2);
                cur2 = cur2.right;
            }
        } else {
            int val1 = stack1.peek().val;
            int val2 = stack2.peek().val;

            // need to break out of here
            if (stack1.peek() == stack2.peek()) break;

            if (val1 +  val2 == B) return 1;

            if (val1 + val2 < B) {
                cur1 = stack1.pop();
                cur1 = cur1.right;
            } else {
                cur2 = stack2.pop();
                cur2 = cur2.left;
            }
        }
    }

    return 0;
}
于 2015-10-30T16:55:50.877 に答える
0

私の知る限り、O(log n) は使用できる最良の検索関数です。「ん」に興味があります。どこかで for ループを使用している場合は、代わりにハッシュテーブルを使用することを検討してください。私の記憶が正しければ、ハッシュ テーブルのシークは O(1) です。

于 2013-09-20T01:16:53.087 に答える
0

Chen Pangの回答の下にバグが1つ見つかりました。それ以外は完璧です。バグは remove メソッドの下にあります。removeイテレータの下のメソッドを除いて、他のすべてのコードは同じです

ツリーがあるとします。Chen Pang の回答によると、要素 18 は考慮されません。同様に、左イテレータについても同様です。

                     10
                          20
                       15     25
                    13    18


class BinTreeIterator implements Iterator<BinTreeNode> {
    Stack<BinTreeNode> stack;
    boolean leftToRight;

    public boolean hasNext() {
        return !stack.empty();
    }

    public BinTreeNode next() {
        return stack.peek();
    }

    public void remove() {
        BinTreeNode node = stack.pop();
        if (leftToRight) {
            node = node.rightChild;
            while (node.rightChild != null) {
                stack.push(node);

                BinTreeNode leftNode=node.leftChild;
                while (leftNode != null) {
                    stack.push(leftNode);
                    leftNode= node.leftChild;
                }

                node = node.rightChild;
            }
        } else {
            node = node.leftChild;
            while (node.leftChild != null) {
                stack.push(node);

                BinTreeNode rightNode=node.rightChild;
                while (rightNode != null) {
                    stack.push(rightNode);
                    rightNode= node.rightChild;
                }

                node = node.leftChild;
            }
        }
    }

    public BinTreeIterator(BinTreeNode node, boolean leftToRight) {
        stack = new Stack<BinTreeNode>();
        this.leftToRight = leftToRight;

        if (leftToRight) {
            while (node != null) {
                stack.push(node);
                node = node.leftChild;
            }
        } else {
            while (node != null) {
                stack.push(node);
                node = node.rightChild;
            }
        }            
    }

    public static boolean searchNumBinTree(BinTreeNode node, int num) {
        if (node == null)
            return false;

        BinTreeIterator leftIter = new BinTreeIterator(node,true);
        BinTreeIterator rightIter = new BinTreeIterator(node,false);

        while (leftIter.hasNext() && rightIter.hasNext()) {
            BinTreeNode left = leftIter.next();
            BinTreeNode right = rightIter.next();
            int sum = left.item + right.item;
            if (sum == num) {
                return true;
            } else if (sum > num) {
                rightIter.remove();
                if (!rightIter.hasNext() || rightIter.next() == left) {
                    return false;
                }
            } else {
                leftIter.remove();
                if (!leftIter.hasNext() || leftIter.next() == right) {
                    return false;
                }
            }
        }

        return false;
    }

    private static class BinTreeNode{

        BinTreeNode leftChild;
        BinTreeNode rightChild;

    }
}
于 2016-09-26T08:32:31.357 に答える