Рубрики

Сумма k наименьших элементов в BST

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

Примеры:

Input :  K = 3
              8
            /   \
           7     10
         /      /   \
        2      9     13
Output : 17
Explanation : Kth smallest element is 8 so sum of all
              element smaller then or equal to 8 are
              2 + 7 + 8

Input : K = 5
           8
         /   \
        5    11
      /  \
     2    7
      \
       3
Output :  25

Способ 1 (не меняет структуру узла BST)
Идея состоит в том, чтобы пройти BST в обходе по порядку. Обратите внимание, что обход Inorder BST обращается к элементам в отсортированном (или увеличивающемся) порядке. Во время обхода мы отслеживаем количество посещенных узлов и добавляем узлы до тех пор, пока счетчик не станет k.

C ++

// c ++ программа для поиска суммы всех элементов меньше
// чем или равен Kth самый маленький элемент в BST
#include <bits/stdc++.h>

using namespace std;

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

struct Node

{

    int data;

    Node* left, * right;

};

  
// служебная функция new Node of BST

struct Node *createNode(int data)

{

    Node * new_Node = new Node;

    new_Node->left = NULL;

    new_Node->right = NULL;

    new_Node->data = data;

    return new_Node;

}

  
// Утилита для вставки нового узла
// с заданным ключом в BST и также поддерживаем lcount, Sum

struct Node * insert(Node *root, int key)

{

    // Если дерево пустое, вернуть новый узел

    if (root == NULL)

        return createNode(key);

  

    // Иначе вернемся вниз по дереву

    if (root->data > key)

        root->left = insert(root->left, key);

  

    else if (root->data < key)

        root->right = insert(root->right, key);

  

    // вернуть (неизмененный) указатель узла

    return root;

}

  
// функция возвращает сумму всех элементов меньше
// и равен Kth наименьшему элементу

int ksmallestElementSumRec(Node *root, int k, int &count)

{

    // Базовые случаи

    if (root == NULL)

        return 0;

    if (count > k)

        return 0;

  

    // Вычисляем сумму элементов в левом поддереве

    int res = ksmallestElementSumRec(root->left, k, count);

    if (count >= k)

        return res;

  

    // Добавить данные root

    res += root->data;

  

    // Добавить текущий узел

    count++;

    if (count >= k)

      return res;

  

    // Если число меньше k, вернуть верные узлы поддеревьев

    return res + ksmallestElementSumRec(root->right, k, count);

}

  
// Оболочка над ksmallestElementSumRec ()

int ksmallestElementSum(struct Node *root, int k)

{

   int count = 0;

   ksmallestElementSumRec(root, k, count);

}

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

int main()

{

  

    / * 20

        / /

       8 22

     / /

    4 12

         / /

        10 14

          * /

    Node *root = NULL;

    root = insert(root, 20);

    root = insert(root, 8);

    root = insert(root, 4);

    root = insert(root, 12);

    root = insert(root, 10);

    root = insert(root, 14);

    root = insert(root, 22);

  

    int k = 3;

    cout <<  ksmallestElementSum(root, k) <<endl;

    return 0;

}

python3

# Python3 программа для поиска Sum Of All
# Элементы меньше или равны
# Kth самый маленький элемент в BST

  

INT_MAX = 2147483647

  
# Узел двоичного дерева
"" "утилита, которая выделяет новый узел
с заданным ключом "" "

class createNode: 

  

    # Конструкция для создания нового узла

    def __init__(self, key): 

        self.data = key

        self.left = None

        self.right = None

  
# Полезная функция для вставки нового
# Узел с данным ключом в BST, а также
# keep lcount, Sum

def insert(root, key) :

  

    # Если дерево пусто, вернуть новый узел

    if (root == None) :

        return createNode(key) 

  

    # В противном случае, повторить вниз по дереву

    if (root.data > key) :

        root.left = insert(root.left, key) 

  

    elif (root.data < key): 

        root.right = insert(root.right, key) 

  

    # вернуть (неизмененный) указатель узла

    return root 

  
# функция возвращает сумму всех элементов меньше
# чем и равно K-му наименьшему элементу

def ksmallestElementSumRec(root, k, count) :

  

    # Базовые случаи

    if (root == None) :

        return 0

    if (count[0] > k[0]) :

        return 0

  

    # Вычислить сумму элементов в левом поддереве

    res = ksmallestElementSumRec(root.left, k, count) 

    if (count[0] >= k[0]) :

        return res 

  

    # Добавить данные root

    res += root.data 

  

    # Добавить текущий узел

    count[0] += 1

    if (count[0] >= k[0]) :

        return res 

  

    # Если число меньше k, вернуть

    # правильное поддерево

    return res + ksmallestElementSumRec(root.right, 

                                        k, count) 

  
# Оболочка над ksmallestElementSumRec ()

def ksmallestElementSum(root, k): 

    count = [0

    return ksmallestElementSumRec(root, k, count) 

  
Код водителя

if __name__ == '__main__':

  

    "" "20

        / /

    8 22

    / /

    4 12

        / /

        10 14

        «»»

    root = None

    root = insert(root, 20

    root = insert(root, 8

    root = insert(root, 4

    root = insert(root, 12

    root = insert(root, 10

    root = insert(root, 14

    root = insert(root, 22)

      

    k = [3

    print(ksmallestElementSum(root, k))

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

Выход :

22

Временная сложность: O (k)

Метод 2 (Эффективно и изменяет структуру BST)
Мы можем найти необходимую сумму за O (h) время, где h — высота BST. Идея похожа на К -тый самый маленький элемент в BST . Здесь мы используем расширенную древовидную структуру данных для эффективного решения этой проблемы за время O (h) [h — высота BST].

Алгоритм:

BST Node contain to extra fields : Lcount , Sum

For each Node of BST
lCount : store how many left child it has
Sum     : store sum of all left child it has

Find Kth smallest element
[ temp_sum store sum of all element less than equal to K ]

ksmallestElementSumRec(root, K, temp_sum)

  IF root -> lCount == K + 1
      temp_sum += root->data + root->sum;
      break;
  ELSE
     IF k > root->lCount   // Goto right sub-tree
        temp_sum += root->data + root-> sum;
        ksmallestElementSumRec(root->right, K-root->lcount+1, temp_sum)
     ELSE
        // Goto left sun-tree
        ksmallestElementSumRec( root->left, K, temp_sum)

Ниже приведена реализация вышеприведенного алгоритма:

C ++

// C ++ программа для поиска суммы всех элементов меньше
// чем самый маленький элемент в BST
#include <bits/stdc++.h>

using namespace std;

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

struct Node

{

    int data;

    int lCount;

    int Sum ;

    Node* left;

    Node* right;

};

  
// служебная функция new Node of BST

struct Node *createNode(int data)

{

    Node * new_Node = new Node;

    new_Node->left = NULL;

    new_Node->right = NULL;

    new_Node->data = data;

    new_Node->lCount = 0 ;

    new_Node->Sum = 0;

    return new_Node;

}

  
// Утилита для вставки нового узла с
// данный ключ в BST, а также ведение lcount, Sum

struct Node * insert(Node *root, int key)

{

    // Если дерево пустое, вернуть новый узел

    if (root == NULL)

        return createNode(key);

  

    // Иначе вернемся вниз по дереву

    if (root->data > key)

    {

        // увеличиваем lCount текущего узла

        root->lCount++;

  

        // увеличиваем текущую сумму узла путем добавления

        // ключ в него

        root->Sum += key;

  

        root->left= insert(root->left , key);

    }

    else if (root->data < key )

        root->right= insert (root->right , key );

  

    // вернуть (неизмененный) указатель узла

    return root;

}

  
// функция, возвращающая сумму всех элементов, меньших и равных
// до Kth наименьшего элемента

void ksmallestElementSumRec(Node *root, int k , int &temp_sum)

{

    if (root == NULL)

        return ;

  

    // если мы найдем k наименьший элемент, то сломаем функцию

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

    {

        temp_sum += root->data + root->Sum ;

        return ;

    }

  

    else if (k > root->lCount)

    {

        // храним сумму всех элементов меньше текущего корня;

        temp_sum += root->data + root->Sum;

  

        // уменьшаем k и вызываем правильное поддерево

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

        ksmallestElementSumRec(root->right , k , temp_sum);

    }

    else // вызвать левое поддерево

        ksmallestElementSumRec(root->left , k , temp_sum );

}

  
// Оболочка над ksmallestElementSumRec ()

int ksmallestElementSum(struct Node *root, int k)

{

    int sum = 0;

    ksmallestElementSumRec(root, k, sum);

    return sum;

}

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

int main()

{

    / * 20

        / /

       8 22

     / /

    4 12

         / /

        10 14

          * /

    Node *root = NULL;

    root = insert(root, 20);

    root = insert(root, 8);

    root = insert(root, 4);

    root = insert(root, 12);

    root = insert(root, 10);

    root = insert(root, 14);

    root = insert(root, 22);

  

    int k = 3;

    cout <<  ksmallestElementSum(root, k) << endl;

    return 0;

}

python3

# Python3 программа для поиска суммы всех элементов
# меньше или равно t Kth наименьшего элемента в BST

  
# служебная функция new Node of BST

class createNode: 

  

    # Конструктор для создания нового узла

    def __init__(self, data): 

        self.data = data 

        self.lCount = 0

        self.Sum = 0

        self.left = None

        self.right = None

  
# Полезная функция для вставки нового узла с
# данный ключ в BST, а также поддерживать lcount, Sum

def insert(root, key):

      

    # Если дерево пусто, вернуть новый узел

    if root == None:

        return createNode(key)

  

    # В противном случае, повторить вниз по дереву

    if root.data > key:

          

        # increment lCount текущего узла

        root.lCount += 1

  

        # увеличить текущую сумму узла на

        # добавив в него ключ

        root.Sum += key 

  

        root.left= insert(root.left , key)

    elif root.data < key: 

        root.right= insert (root.right , key)

  

    # вернуть (неизмененный) указатель узла

    return root

  
# функция возвращает сумму всех элементов меньше
# чем и равно K-му наименьшему элементу

def ksmallestElementSumRec(root, k , temp_sum):

    if root == None:

        return

  

    # если мы найдем k наименьший элемент

    # затем нарушить функцию

    if (root.lCount + 1) == k:

        temp_sum[0] += root.data + root.Sum

        return

  

    elif k > root.lCount:

          

        # хранить сумму всего элемента меньше

        # чем текущий корень;

        temp_sum[0] += root.data + root.Sum

  

        # уменьшенное k и вызов правильного поддерева

        k = k -( root.lCount + 1)

        ksmallestElementSumRec(root.right, 

                               k, temp_sum)

    else: # вызов левого поддерева

        ksmallestElementSumRec(root.left, 

                               k, temp_sum)

  
# Оболочка над ksmallestElementSumRec ()

def ksmallestElementSum(root, k):

    Sum = [0

    ksmallestElementSumRec(root, k, Sum

    return Sum[0]

  
Код водителя

if __name__ == '__main__':

      

    № 20

    # / /

    # 8 22

    # / /

    № 4 12

    # / /

    № 10 14

    #

    root = None

    root = insert(root, 20

    root = insert(root, 8

    root = insert(root, 4

    root = insert(root, 12

    root = insert(root, 10

    root = insert(root, 14

    root = insert(root, 22)

  

    k = 3

    print(ksmallestElementSum(root, k))

  
# Этот код предоставлен PranchalK


Выход:

22

Сложность времени: O (h) где h — высота дерева.
Эта статья предоставлена Nishant Singh . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Сумма k наименьших элементов в BST

0.00 (0%) 0 votes