查找二元搜索樹中第k個最接近的元素

Question

以下是我在訪問中被問到的一個問題。對於給定的BST，找到第k個最接近的元素。遍歷整棵樹是不可接受的。解決方案不應該是o（n），空間複雜性不是問題。 謝謝。

我嘗試 - 遍歷樹的分支之一，以獲得可能的元素，然後遍歷起始於這些元素的分支。

Answer 1

我假設兩個節點之間的緊密度由它們之間的邊數定義和虐待解決歧義還假設等距離父母的情況下，最接近然後右鍵點然後離開節點。

爲根節點第k個最接近的元件將是第k個元素是樹的級別順序遍歷。

對於樹中的任何節點上，我們將與節點開始，在距離一個邊緣，即其母公司，右，左，然後距離2邊即父，權，在距離1左節點等。我們將繼續計數，直到達到k個節點，同時確保我們不會對節點計數兩次。考慮下面的僞代碼。

KthClosest(Node * node, k) 
{ 
    std::queue<Node *> queue; 
    std::map<Node *, bool> mapToCheckIFNodeIsCounted; 
    int count = 0; 
    queue.push_back(node); 
    while(count <k) 
    { 
     Node* node = queue.pop(); 
     if(node ->parent != NULL) 
     { 
      if(mapToCheckIFNodeIsCounted.find(node->parent) ==mapToCheckIFNodeIsCounted.end()) 
      { 
       queue->push_back(node->parent); 
       mapToCheckIFNodeIsCounted.insert(std::pair<node->parent,true>); 

      } 
     } 
     if(node -> right != NULL) 
     { 

      if(mapToCheckIFNodeIsCounted.find(node->right) == mapToCheckIFNodeIsCounted.end()) 
      { 
      queue->push_back(node->right); 
      mapToCheckIFNodeIsCounted.insert(std::pair<node->right,true>); 
      } 
     } 
     if(node -> left != NULL) 
     { 

      if(mapToCheckIFNodeIsCounted.find(node->parent) == mapToCheckIFNodeIsCounted.end()) 
      { 
       queue->push_back(node->left); 

       mapToCheckIFNodeIsCounted.insert(std::pair<node->left,true>); 
      } 
     } 
     count++; 

    } 

    // Kth node is the node in queue after loop has finished fraversing k closest elements 

    Node *node = queue.pop(); 
    print(node->value); 



} 

Answer 2

首先我們必須找到。 1，首先你必須得到節點（從BST根節點） 2.你必須得到低於它的節點和遠處的節點k。 3.你必須得到一個在它上面的k節點的祖先。你必須得到距離它第k個的節點。 （在相同的水平或在其它級別）

        A(8) 
           /  \ 
           B(6)   C(22) 
         / \  /\ 
         D(5) E(7) F(17) G(26) 
            /\  \ 
            (15)H I(19)  N(29) 
            / \ 
           (14) K  L(20) 

Okie考慮樹是BST樹（A，B，C d不在BST的序列，*考慮它們的節點參照身份節點而不是值*） 我已經記下了一個代表數值的數字。

還有一個考慮因素。 由於它被宣佈爲BST樹。沒有父指針存在。 *

您將得到樹的根。 給定數字17，並給出k = 2的值。 首先對數17得到的參考（F） 對於k = 2，即是2節點的距離F. 得到樹的所有節點爲F的死者你必須檢測K（14）和L（20） 作爲F的先驗，你必須得到節點A. 再次，你必須得到節點G（2節點距離）（儘管沒有父指針，你必須得到它）。

一步一步首先對於數字 - > 17得到參考F（你有根）做一個簡單的二分搜索。

ArrayList get_it(Node root_node, int number) { 
    node = root_node; 
    if (node ==null) 
     throw new IllegarArgumentException("null root node"); 
    ArrayList pathtracker = new ArrayList(); 
    //is the root node matches 
    pathtracker.add(node); // fix 
    if(node.data=number) // fix 
    return pathtracker; 
    while(node !=null) { 
     if (node.data==number){ 
      return pathtracker; 
     } 
     if (node.data >= number){ 
      node=node.left; 
     } 
     else{ 
      node=node.right; 
     } 
     pathtracker.add(node);   
    } // end of while loop 
    return new ArrayList(); //search failed node is not present. 
    // returning empty arrayList 
} 

現在我們將使用pathtracker。 這有從根到這個節點的軌道節點。 第0個節點是root，length（） - 第1個節點是我們搜索的節點 。

for (int i = pathtracker.length() - 1 , depth=k ; 
     (depth => 0 && i => 0) ; i--,depth--){ 
    if (i == pathtracker.length() - 1) {//first case 
     printnodeDistancek(pathtracker.get(i), depth); 
    }else { 
     if(pathtracker.get(i).left ! = pathtracker.get(i+1)){ 
      printnodeDistancek(pathtracker.get(i).left, depth); 
     }else{ 
      printnodeDistancek(pathtracker.get(i).right, depth); 
     }  
    } // end of else block 
} // end of loop 

void printnodeDistancek(node n, k) { 
    if (node==null) 
     return; 
    if (k = 0) { 
     print node.data; 
     return; 
    } 
    printnodeDistancek(n.left, k-1); 
    printodeDistanceK(node.right, k-1); 
} 

給定數是17（F節點）和 現在，如果K = 3這應該打印N和B. 如果K = 4這應該打印d（5）和E97）

Answer 3

我想問題是有關查找BST的第K個最接近元件的值V，

注意：這是不可能的，以做到這一點，在不到O（n）的時間，除非BST是平衡的，

要查找第K個最接近的元素： 我們維持ķ整數已經最接近的值到V至今， 1.Visiting每個節點（從根開始），我們將節點的值，其前任和後繼的值添加到迄今爲止所見的最接近的值。 （如果數組已滿，我們只將值放入數組中，如果數組已滿，我們用此值替換最大值）

2.我們選擇正確的分支，如果當前節點的後繼更靠近V如果前任更近，則離開分支。

3，我們重複，直到沒有更多的節點訪問（我們得到一個葉子）

4.時間複雜度：O（N^2 * K），如果我們假設k爲常數（如ķ = 3）並且樹是平衡的，時間複雜度將是：O（log（n）^ 2）

Integer[] closest = new Integer[3]; // initialized with null 
void find_3rd_closest(Node current , int K){ 

    Node succ = Successor(current); 
    Node pred = Predecessor(current); 

    insert(closest , current.val , K); 
    if (succ != null) 
     insert(closest , succ.val , K); 
    if (pred != null) 
     insert(closest , pred.val , K); 

    if (succ != null && pred != null) 
     if (Math.abs(pred.val - K) < Math.abs(succ.val - K)) 
      find_3rd_closest(pred , K); 
     else 
      find_3rd_closest(succ , K); 
    else if (pred != null) 
     find_3rd_closest(pred , K); 
    else if (succ != null) 
     find_3rd_closest(succ , K); 
    else 
     return; 
} 

void insert(int[] closest , int val, int K){ 
    for (int i = 0 ; i < closest.length ; i++){ 
     if (closest[i] != null && Math.abs(K - val) < Math.abs(K - closest[i])){ 
      for (int j = i ; i < closest.length - 1 ; i++){ 
       int temp = closest[i+1]; 
       closest[i+1] = closest[i]; 
       closest[i] = temp; 
      } 
     } 
     closest[i] = succ.value; 
    } 
} 

Node Successor(Node current){ 
    if (current.rightChild == null) 
     return null; 
    current = current.rightChild; 
    while (current.leftChild != null) 
     current = current.leftChild; 
    return current; 
} 

Node Predecessor(Node current){ 
    if (current.leftChild == null) 
     return null; 
    current = current.leftChild; 
    while (current.rigthChild != null) 
     current = current.rightChild; 
    return current; 
}