Нахождение k-го наименьшего значения в BST

Вот что мне нужно, чтобы найти k-е наименьшее значение в двоичном дереве поиска:

struct treeNode 
{
   int data;
   struct treeNode *left, *right:
};

int rank(stuct treeNode* ptr, int k)
{
   if(node == NULL)
    return root; 

   while(ptr->left != NULL) {
     ptr = ptr->left;
     return rank(ptr->left)
   }
}

Это явно не правильно. Не предоставив решение, может ли кто-нибудь направить меня в правильном направлении относительно того, как я могу решить эту проблему? Мне трудно понять, как найти k-й наименьший элемент в BST.


c binary-search-tree
person kachilous    schedule 03.05.2011    source источник

Ответы (3)


arrow_upward
5
arrow_downward

BST — это отсортированное двоичное дерево, обход по порядку (левое поддерево, текущий узел, правое поддерево) даст значения отсортированных узлов. Чтобы найти k-й наименьший узел, просто выполните обход по порядку со счетчиком. Счетчик начинается с 0, всякий раз, когда проходится узел, увеличивайте его на единицу, когда он достигает k, узел является k-м наименьшим.

person Arrix    schedule 03.05.2011
comment
Спасибо. Также может ли это быть возможной реализацией с использованием порядка? pastebin.com/wvSsTnDM - person kachilous; 04.05.2011

arrow_upward
1
arrow_downward

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

Основная идея, выяснить, каков индекс текущего узла. Если оно меньше k, нужно искать в левом поддереве. Если оно больше, чем k, искать справа, смещая узлы, подсчитанные слева и текущие. Обратите внимание, что это по сути то же самое, что и поиск в обычном BST, за исключением того, что на этот раз мы ищем по индексу, а не по данным. Какой-то псевдокод:

if size of left subtree is equal to k:
    // the current node is kth
    return data of current node
else if size of left subtree is greater than k:
    // the kth node is on the left
    repeat on the left subtree
else if size of left subtree is less than k:
    // the kth node is on the right
    reduce k by the size of the left subtree + 1 // need to find the (k')th node on the right subtree
    repeat on the right subtree

Для иллюстрации рассмотрим это дерево с отмеченными индексами (даже не беспокойтесь о данных, так как они не важны при поиске):

        3
      /   \
     2     6
    /     / \
   0     4   7
    \     \
     1     5

Предположим, мы хотим найти второе (k = 2).
Начиная с 3, размер левого поддерева равен 3.
Оно больше, чем k, поэтому переходим к левому поддереву.
Размер левое поддерево равно 2.
k также равно 2, поэтому текущий узел должен быть вторым.

Предположим, мы хотим найти 4-й (k = 4).
Начиная с 3, размер левого поддерева равен 3.
Он меньше l, поэтому присвойте новому k значение 0 (k' = 4). - (3 + 1)) и перейти к правому поддереву.
Начиная с 6, размер левого поддерева равен 2.
Это больше, чем k' (0), поэтому перейти к левому поддереву.< br> Размер левого поддерева равен 0.
k' также равно 0, поэтому текущий узел должен быть 4-м.

Вы поняли идею.

person Jeff Mercado    schedule 03.05.2011

arrow_upward
0
arrow_downward

Это должно работать:

int rank(struct treeNode* n,int k,int* chk)
    {
    if(!n) return -1;
    int _chk = 0;
    if(!chk) chk = &_chk;

    int t = rank(n->left,k,chk);
    if(t>=0) return t;

    if(++*chk > k) return n->data;

    int t = rank(n->right,k,chk);
    if(t>=0) return t;
    return -1;
    }

позвоните как rank(root,k,0)

person David X    schedule 03.05.2011