BST，是否有可能在 O(lg N) 中找到下一个最低值？

Question

TreeNodeclass只定义了左右child。

public class TreeNode {

    public int val;
    public TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
    }
}

我的代码在 O(n) 中找到下一个最低节点。我想知道是否有可能在 lg(N) 中找到它，因为该节点没有指向其 parent 节点的指针。

// run time O(n)
    public static Integer findNextLowest(TreeNode root, int target) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || stack.size() > 0) {

            while (cur != null) {
                stack.push(cur);
                cur = cur.right;
            }
            TreeNode node = stack.pop();
            if (node.val < target) return node.val; // found the next lowest
            cur = node.left;
        }
        return null;
    }

Answer 1

不，因为你还没有实现 Binary Search Tree ，只是一棵二叉树。

BST 将限制其值，使得 left.val < val < right.val，因此您可以

// run time O(log(n)) if cur is balanced
public static Integer findNextLowest(TreeNode cur, int target) {        
    if (target < cur.val) { return cur.left != null ? findNextLowest(cur.left, target) : null; }
    if (curr.right != null)
    { 
        Integer result = findNextLowest(cur.right, target);
        if (result != null) { return result; }
    }
    return cur.val;
}

你应该使用类似 R-B tree 的东西来确保它是平衡的

Answer 2

private static TreeNode findNextLowest(TreeNode root, int target){
    TreeNode node = root;
    TreeNode res = null;
    while(node != null){
        while(node != null && node.val >= target){
            node = node.left;
        }
        while(node != null && node.val < target){
            res = node;
            node = node.right;
        }
    }
    return res;
}

BST，是否有可能在 O(lg N) 中找到下一个最低值？

BST, is it possible to find next lowest in O(lg N)?

target

next

binary-search-tree