BST, est-il possible de trouver le plus bas suivant dans O (lg N)?

Question

La classe TreeNode est définie avec uniquement les enfants gauche et droit.

public class TreeNode { 

    public int val; 
    public TreeNode left, right; 

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

Mon code trouve le nœud le plus bas suivant dans O (n). Je me demandais s'il était possible de le trouver dans lg (N) étant donné que le nœud n'a pas de pointeur vers son nœud 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

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; 
} 

Answer 2

Non, parce que vous ne l'avez pas mis en place un B inaire S echerchez T REE, juste un arbre binaire.

Un BST limitera ses valeurs telles que left.val < val < right.val, de sorte que vous pouvez faire

// 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; 
} 

Vous devez utiliser quelque chose comme un R-B tree pour vous assurer qu'il est équilibré