Найти nth наименьший элемент в двоичном дереве поиска

Question

Я написал алгоритм поиска n-го наименьшего элемента в BST, но он возвращает корневой узел вместо n-го наименьшего. Поэтому, если вы вводите узлы в порядке 7 4 3 13 21 15, этот алгоритм после вызова find (root, 0) возвращает узел со значением 7 вместо 3, а для вызова find (root, 1) он возвращает 13 вместо 4. Любой мысли?

Binode* Tree::find(Binode* bn, int n) const 
{ 
    if(bn != NULL) 
    { 

    find(bn->l, n); 
    if(n-- == 0) 
     return bn;  
    find(bn->r, n); 

    } 
    else 
     return NULL; 
} 

и определение Binode

class Binode 
{ 
public: 
    int n; 
    Binode* l, *r; 
    Binode(int x) : n(x), l(NULL), r(NULL) {} 
}; 

Answer 1

Есть несколько проблем с кодом:

1) find() возвращает значение (правильный узел, предполагая, что функция работает как задумано) , но вы не распространяете это значение на цепочку вызовов, поэтому вызовы верхнего уровня не знают о найденном (возможно) элементе

.

Binode* elem = NULL; 
elem = find(bn->l, n); 
if (elem) return elem; 
if(n-- == 0) 
    return bn;  
elem = find(bn->r, n); 
return elem; // here we don't need to test: we need to return regardless of the result 

2), даже если вы убыли n в нужном месте, изменение не распространяется вверх по цепочке вызовов. Вам необходимо передать параметр по ссылке (отметьте & после int в сигнале функции), поэтому изменение производится на исходное значение, а не на его копию

.

Binode* Tree::find(Binode* bn, int& n) const 

Я не проверял предложенные изменения, но они должны поставить вас в правильном направлении для достижения прогресса

Answer 2

Это не позволяет эффективно извлекать п-й наименьший элемент в виде двоичного дерева поиска сам по себе , Однако это становится возможным, если вы сохраняете в каждом узле целое число, указывающее количество узлов во всем его поддереве. От my generic AVL tree implementation:

static BAVLNode * BAVL_GetAt (const BAVL *o, uint64_t index) 
{ 
    if (index >= BAVL_Count(o)) { 
     return NULL; 
    } 

    BAVLNode *c = o->root; 

    while (1) { 
     ASSERT(c) 
     ASSERT(index < c->count) 

     uint64_t left_count = (c->link[0] ? c->link[0]->count : 0); 

     if (index == left_count) { 
      return c; 
     } 

     if (index < left_count) { 
      c = c->link[0]; 
     } else { 
      c = c->link[1]; 
      index -= left_count + 1; 
     } 
    } 
} 

В приведенном выше коде, node->link[0] и node->link[1] левый и правый ребенок node и node->count это число узлов во всем поддереве node.

Приведенный выше алгоритм имеет сложность времени O (logn), если дерево сбалансировано. Кроме того, если вы держите эти подсчеты, возможна другая операция - с учетом указателя на узел, можно эффективно определить его индекс (обратный к тому, что вы просили). В коде, который я связал, эта операция называется BAVL_IndexOf().

Помните, что количество узлов должно быть обновлено по мере изменения дерева; это можно сделать без (асимптотического) изменения временной сложности.