Рубрики

Найти k-й наименьший элемент в BST (Статистика заказов в BST)

Учитывая корень дерева двоичного поиска и K в качестве входных данных, найдите K-й наименьший элемент в BST.

Например, в следующем BST, если k = 3, то выходное значение должно быть 10, а если k = 5, то выходное значение должно быть 14.

Метод 1: Использование обхода Inorder.

Обход по порядку следования BST извлекает элементы дерева в отсортированном порядке. Обход по порядку использует стек для хранения исследуемых узлов дерева (многопоточное дерево избегает стека и рекурсии для обхода, см. Этот пост ). Идея состоит в том, чтобы отслеживать вытолкнутые элементы, которые участвуют в статической обработке заказа. Гипотетический алгоритм приведен ниже,

Сложность по времени: O (n), где n — общее количество узлов в дереве.

Алгоритм:

/* initialization */
pCrawl = root
set initial stack element as NULL (sentinal)

/* traverse upto left extreme */
while(pCrawl is valid )
   stack.push(pCrawl)
   pCrawl = pCrawl.left

/* process other nodes */
while( pCrawl = stack.pop() is valid )
   stop if sufficient number of elements are popped.
   if( pCrawl.right is valid )
      pCrawl = pCrawl.right
      while( pCrawl is valid )
         stack.push(pCrawl)
         pCrawl = pCrawl.left

Реализация:

#include <stdio.h>
#include <stdlib.h>

  
#define ARRAY_SIZE(arr) sizeof(arr)/sizeof(arr[0])

  
/ * просто добавляем элементы для проверки * /
/ * ПРИМЕЧАНИЕ: отсортированный массив приводит к перекосу дерева * /

int ele[] = { 20, 8, 22, 4, 12, 10, 14 };

  
/ * тот же псевдоним * /

typedef struct node_t node_t;

  
/ * Узел двоичного дерева * /

struct node_t

{

    int data;

  

    node_t* left;

    node_t* right;

};

  
/ * простой стек, в котором хранятся адреса узлов * /

typedef struct stack_t stack_t;

  
/ * начальный элемент всегда NULL, используется как sentinal * /

struct stack_t

{

    node_t*  base[ARRAY_SIZE(ele) + 1];

    int      stackIndex;

};

  
/ * pop операция стека * /
node_t *pop(stack_t *st)
{

    node_t *ret = NULL;

  

    if( st && st->stackIndex > 0 )

    {

        ret = st->base[st->stackIndex];

        st->stackIndex--;

    }

  

    return ret;

}

  
/ * операция выталкивания стека * /

void push(stack_t *st, node_t *node)

{

    if( st )

    {

        st->stackIndex++;

        st->base[st->stackIndex] = node;

    }

}

  
/ * Итеративная вставка

   Рекурсия наименее предпочтительна, если мы не получим что-то

* /
node_t *insert_node(node_t *root, node_t* node)
{

    / * Ползущий указатель * /

    node_t *pTraverse = root;

    node_t *currentParent = root;

  

    // Переходим к соответствующему узлу

    while(pTraverse)

    {

        currentParent = pTraverse;

  

        if( node->data < pTraverse->data )

        {

            / * левое поддерево * /

            pTraverse = pTraverse->left;

        }

        else

        {

            / * правое поддерево * /

            pTraverse = pTraverse->right;

        }

    }

  

    / * Если дерево пустое, сделать его корневым узлом * /

    if( !root )

    {

        root = node;

    }

    else if( node->data < currentParent->data )

    {

        / * Вставить на левой стороне * /

        currentParent->left = node;

    }

    else

    {

        / * Вставить на правой стороне * /

        currentParent->right = node;

    }

  

    return root;

}

  
/ * Элементы находятся в массиве. Функция строит двоичное дерево * /

node_t* binary_search_tree(node_t *root, int keys[], int const size)

{

    int iterator;

    node_t *new_node = NULL;

  

    for(iterator = 0; iterator < size; iterator++)

    {

        new_node = (node_t *)malloc( sizeof(node_t) );

  

        / * инициализировать * /

        new_node->data   = keys[iterator];

        new_node->left   = NULL;

        new_node->right  = NULL;

  

        / * вставить в BST * /

        root = insert_node(root, new_node);

    }

  

    return root;

}

  

node_t *k_smallest_element_inorder(stack_t *stack, node_t *root, int k)

{

    stack_t *st = stack;

    node_t *pCrawl = root;

  

    / * переместиться в крайнее левое положение (минимум) * /

    while( pCrawl )

    {

        push(st, pCrawl);

        pCrawl = pCrawl->left;

    }

  

    / * выгрузить стек и обработать каждый узел * /

    while( pCrawl = pop(st) )

    {

        / * каждая операция pop выдает один элемент

           в порядке

        * /

        if( !--k )

        {

            / * тестирование петли * /

            st->stackIndex = 0;

            break;

        }

  

        / * есть правильное поддерево * /

        if( pCrawl->right )

        {

            / * нажать левое поддерево правого поддерева * /

            pCrawl = pCrawl->right;

            while( pCrawl )

            {

                push(st, pCrawl);

                pCrawl = pCrawl->left;

            }

  

            / * выскочить из стека и повторить * /

        }

    }

  

    / * узел, имеющий k-й элемент или узел NULL * /

    return pCrawl;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main(void)

{

    node_t* root = NULL;

    stack_t stack = { {0}, 0 };

    node_t *kNode = NULL;

  

    int k = 5;

  

    / * Создание дерева приведено на диаграмме выше * /

    root = binary_search_tree(root, ele, ARRAY_SIZE(ele));

  

    kNode = k_smallest_element_inorder(&stack, root, k);

  

    if( kNode )

    {

        printf("kth smallest element for k = %d is %d", k, kNode->data);

    }

    else

    {

        printf("There is no such element");

    }

  

    getchar();

    return 0;

}

Метод 2: Расширенная структура данных дерева.

Идея состоит в том, чтобы поддерживать ранг каждого узла. Мы можем отслеживать элементы в поддереве любого узла при построении дерева. Так как нам нужен K-й наименьший элемент, мы можем поддерживать количество элементов левого поддерева в каждом узле.

Предположим, что корень имеет N узлов в своем левом поддереве. Если K = N + 1, корнем является K-й узел. Если K <N, мы продолжим поиск (рекурсию) наименьшего K-го элемента в левом поддереве корня. Если K> N + 1, мы продолжаем поиск в правом поддереве (K — N — 1) -го наименьшего элемента. Обратите внимание, что нам нужно количество элементов только в левом поддереве.

Временная сложность: O (h) где h — высота дерева.

Алгоритм:

start:
if K = root.leftElement + 1
   root node is the K th node.
   goto stop
else if K > root.leftElements
   K = K - (root.leftElements + 1)
   root = root.right
   goto start
else
   root = root.left
   goto start

stop:

Реализация:

#include <stdio.h>
#include <stdlib.h>

  
#define ARRAY_SIZE(arr) sizeof(arr)/sizeof(arr[0])

  

typedef struct node_t node_t;

  
/ * Узел двоичного дерева * /

struct node_t

{

    int data;

    int lCount;

  

    node_t* left;

    node_t* right;

};

  
/ * Итеративная вставка

   Рекурсия наименее предпочтительна, если мы не получим что-то

* /
node_t *insert_node(node_t *root, node_t* node)
{

    / * Ползущий указатель * /

    node_t *pTraverse = root;

    node_t *currentParent = root;

  

    // Переходим к соответствующему узлу

    while(pTraverse)

    {

        currentParent = pTraverse;

  

        if( node->data < pTraverse->data )

        {

            / * Мы разветвляемся на левое поддерево

               число узлов приращения * /

            pTraverse->lCount++;

            / * левое поддерево * /

            pTraverse = pTraverse->left;

        }

        else

        {

            / * правое поддерево * /

            pTraverse = pTraverse->right;

        }

    }

  

    / * Если дерево пустое, сделать его корневым узлом * /

    if( !root )

    {

        root = node;

    }

    else if( node->data < currentParent->data )

    {

        / * Вставить на левой стороне * /

        currentParent->left = node;

    }

    else

    {

        / * Вставить на правой стороне * /

        currentParent->right = node;

    }

  

    return root;

}

  
/ * Элементы находятся в массиве. Функция строит двоичное дерево * /

node_t* binary_search_tree(node_t *root, int keys[], int const size)

{

    int iterator;

    node_t *new_node = NULL;

  

    for(iterator = 0; iterator < size; iterator++)

    {

        new_node = (node_t *)malloc( sizeof(node_t) );

  

        / * инициализировать * /

        new_node->data   = keys[iterator];

        new_node->lCount = 0;

        new_node->left   = NULL;

        new_node->right  = NULL;

  

        / * вставить в BST * /

        root = insert_node(root, new_node);

    }

  

    return root;

}

  

int k_smallest_element(node_t *root, int k)

{

    int ret = -1;

  

    if( root )

    {

        / * Ползущий указатель * /

        node_t *pTraverse = root;

  

        / * Перейти к k-му самому маленькому * /

        while(pTraverse)

        {

            if( (pTraverse->lCount + 1) == k )

            {

                ret = pTraverse->data;

                break;

            }

            else if( k > pTraverse->lCount )

            {

                / * На левом поддереве меньше узлов

                    Перейти к правому поддереву * /

                k = k - (pTraverse->lCount + 1);

                pTraverse = pTraverse->right;

            }

            else

            {

                / * Узел находится на левом поддереве * /

                pTraverse = pTraverse->left;

            }

        }

    }

  

    return ret;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main(void)

{

    / * просто добавляем элементы для проверки * /

    / * ПРИМЕЧАНИЕ: отсортированный массив приводит к перекосу дерева * /

    int ele[] = { 20, 8, 22, 4, 12, 10, 14 };

    int i;

    node_t* root = NULL;

  

    / * Создание дерева приведено на диаграмме выше * /

    root = binary_search_tree(root, ele, ARRAY_SIZE(ele));

  

    / * Должен напечатать отсортированный массив * /

    for(i = 1; i <= ARRAY_SIZE(ele); i++)

    {

        printf("\n kth smallest element for k = %d is %d",

                 i, k_smallest_element(root, i));

    }

  

    getchar();

    return 0;

}

Спасибо Venki за предоставление поста. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти k-й наименьший элемент в BST (Статистика заказов в BST)

0.00 (0%) 0 votes