BST中的值的底面

給定一個值和BST，我們需要找到最小的數字，它只是小於或等於給定值，即數值的底部。例如，1 4 7 9 12 13 43 45是在BST中的給定的序列遍歷，我們給出的值爲15。BST中的值的底面

所以地板（15）= 13，地板（10）= 9等

我正在做序遍歷和保持先前的節點，並且如果該值之前和根節點的數據之間然後returnt那價值作爲地板。但是，它不適用於所有情況。

此外，由於它是一個BST，我們不需要做完整的遍歷，我們可以利用BST屬性。但我無法將我的邏輯轉換爲代碼。所以任何人都可以請幫忙嗎？

最好在Java中。我們需要在我們正在創建基於Java的新語言的項目中使用它。

來源

2014-04-28 h4ck3d

以下working Java code解決了這個問題在O(log N)時間。

邏輯非常簡單。如果當前節點中的值小於val，則在當前節點的右側子樹中查找更大的值，或者在左側子樹中查找答案。

void run(){ 
     Obj root = new Obj(1); 
     root = insertVal(root, 4); 
     root = insertVal(root, 7); 
     root = insertVal(root, 9); 
     root = insertVal(root, 12); 
     root = insertVal(root, 13); 
     root = insertVal(root, 43); 
     root = insertVal(root, 45); 
     System.out.println(floor(root, 15)); 
} 

// throws a RuntimeException if there is no smaller value in the BST. 
int floor(Obj root, int val){ 
    int ans = Integer.MIN_VALUE; 
    boolean found = false; 
    while(root != null){ 
     if(root.val==val){ 
      return val; 
     } 
     if(val < root.val){ 
      root = root.left; 
     }else{ 
      found = true; 
      ans = root.val; 
      root = root.right; 
     } 
    } 
    if(!found){ 
     throw new RuntimeException("There is no smaller value than " + val + " in the BST"); 
    } 
    return ans; 
} 

Obj insertVal(Obj root, int val){ 
    if(root==null){ 
     return new Obj(val); 
    } 
    if(val < root.val){ 
     root.left = insertVal(root.left, val); 
    }else{ 
     root.right = insertVal(root.right, val); 
    } 
    return root; 
} 
} 
class Obj{ 
int val; 
Obj right; 
Obj left; 

public Obj(int val){ 
     this.val = val; 
     right = left = null; 
} 

public String toString(){ 
     return val + " "; 
} 
}

來源

2014-04-28 12:31:22

BST中的值的底面

回答

相關問題