Нахождение k-го элемента в БСТ


Дано двоичное дерево поиска, определить ее K-й элемент симметричного обхода.

Вот моя структура узла:

struct node 
{
    int elem;
    node *left, *right;


    static node* create(int elem)
    {
        node *newnode = new node;
        newnode->elem = elem;
        newnode->left = newnode->right = NULL;
        return newnode;
    }   

        // Forget freeing up memory

};

Вот моя БСТ:

class tree
{
  private:
  node *root;

  public:
  tree(int elem)    { root = node::create(elem); }

  bool insert(int elem) 
  {
    node *newnode = node::create(elem);
    node *travnode = root;

    while(1)
    {
      if(elem &lt travnode->elem) 
      {
        if(travnode-> left == NULL)
    {
      travnode->left = node::create(elem);
      return true;
    }
    else travnode = travnode->left;
      } // elem < travnode->elem
      else
      if(elem > travnode->elem)
      {

        if(travnode->right == NULL)
    {
      travnode->right = node::create(elem);
      return true;
    }
    else
          travnode = travnode->right;

      }
      else 
         return false;
 } 

  /*  findKthInorder 
  @param mynode [in]     -- the root of tree whose kth largest is to be found
  @param k [in]          -- value k
  @param count [in]      -- a counter to keep track of which node we're in
  @param result [in,out] -- returns mynode->elem once we're in kth node
  */
  void findKthInorder(const node *mynode, const int k, int &count,  int &result) const   
  {
    if(mynode != NULL) 
    {
      findKthInorder(mynode->left,k,count,result);
      if(!--count)  
      {
        result = mynode->elem;
    return;
      } // if (!--count)

      findKthInorder(mynode->right,k,count,result);
    } // if (mynode != NULL)
  } // findKthInorder


  /* findKthInorder 
     abstracts away previous function and is exposed to outside world
  */
  int findKthInorder(const int k) const 
  {
    int count = k,result = 0;
    findKthInorder(root,k,count,result);
    return result;

   }

}; // class tree

Вот некоторые тестовый код, который я написал:

int main()
{
   tree T = tree(5);   
   T.insert(1); T.insert(7);   T.insert(-1);T.insert(6);

   for(int i = 1;i != 5; ++i)  
       printf("%d, " T.findKthInorder(i)); // -1, 1,5,6,7
   return 0;
}

Я буду рад выслушать любые предложения для более элегантного findKthInorder() функция.



2466
4
задан 9 апреля 2011 в 08:04 Источник Поделиться
Комментарии
1 ответ

Если вы добавляете общее поле граф для каждого узла, вы можете найти K-й элемент эффективно (за логарифмическое время) написанием метод вроде этого (непроверенных):

node *kth(int k)
{
assert(k >= 0 && k < total);

if (left != NULL) {
if (k < left->total)
return left->kth(k);
k -= left->total;
}

if (k == 0)
return this;

assert(right != NULL);
return right->kth(k - 1);
}

В противном случае рекурсивный алгоритм, который вы использовали для findKthInorder является наиболее элегантный способ я могу думать, чтобы сделать это. Я бы прибраться немного, хотя:

static const Node *kth_(const Node *node, int &k)
{
if (node == NULL)
return NULL;

const Node *tmp = kth_(node->left, k);
if (tmp != NULL)
return tmp;

if (k-- == 0)
return node;

return kth_(node->right, k);
}

int kth(int k) const
{
assert(k >= 0);

const Node *node = kth_(this, k);
if (node == NULL) {
std::cerr << "kth: k is too large\n";
exit(1);
}

return node->elem;
}

Возвращая узла указателя, а не какой-либо элемент из вспомогательной функции имеет два преимущества:


  • Мы можем использовать значение null , чтобы указать отказ.

  • Мы вам бросить аргумента из вспомогательной функции.

  • В будущем, вам будет легче написать функцию для обновления K-й элемент.

В findKthInOrder вспомогательные функции, к аргумент никогда не используется и может быть удален также.

Пару уборок на стороне:


  • Я переименовал класс узла к узлу , чтобы не сказать mynode повсюду. Я думаю, это просто дело вкуса, видя, как STL использует Буквы в именах типа.

  • Я переключился на нулевой индексацией. Опять же, это дело вкуса, но индексация с нуля-это гораздо более распространено в C++, и работать проще во многих случаях.

5
ответ дан 11 апреля 2011 в 04:04 Источник Поделиться