Поиск 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. Вы должны получить предка, который находится над ним над ним. 4. Вы должны получить узлы, которые на расстоянии 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) 

Ока рассмотрит дерево является БСТ Дерево (А, В, С д не в последовательности BST, * считать их узел ссылка на идентичность узел, а не значение *) Я установил числа, которые представляют значения.

Еще одно соображение. Так как это объявлено BST Tree. нет родительских указателей. *

У вас есть корень A дерева. с номером 17 и задано значение k = 2. Сначала для номера 17 получить ссылку (F) Для k = 2, то есть от 2-х узловых расстояний, получите все узлы дерева из F. в качестве дециентов F вы должны обнаружить K (14) и L (20) как по силе F вам нужно получить Node A. снова вам нужно получить Node G (расстояние между двумя узлами) (хотя нет родительского указателя, который вам нужно получить).

Шаг за шагом сначала для номера -> 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 
} 

Теперь мы будем использовать пут-крэкер. У этого есть узлы пути от корня до этого узла. 0-й узел - корень, длина() - 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 узел) и Теперь, если к = 3 это должно напечатать N и B. , если К = 4, это должно напечатать D (5) и Е97)

Answer 3

Думаю, речь шла о нахождении K-й ближайший элемент BST до величины V,

Примечание: это не возможно сделать это в меньше, чем O (N) времени, если BST не является сбалансированным,

чтобы найти K-й элемент ближайший: Мы считаем, K целых чисел, которые были самые близкие значения V до сих пор, 1.Visiting каждый узел (начиная с корня) добавляет значение узла, значение его предшественника и преемника к ближайшим значениям, которые были обнаружены до сих пор. (мы добавляем значение только в массив, близкий к V, если массив заполнен, мы заменяем наибольшее значение этим значением).

2. Мы выбираем правильную ветвь, если преемник текущего узла ближе к V и левая ветвь, если предшественник ближе.

3.Мы повторить до тех пор, пока это не больше узла для посещения (мы получаем лист)

4.Time сложность: O (N^2 * к), если мы предположим, что к постоянной (например, к = 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; 
}