查找二元搜索树中第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; 
}