Рубрики

Реализация BST, где каждый узел хранит максимальное количество узлов в пути до любого листа

Дан массив значений. Задача состоит в том, чтобы реализовать двоичное дерево поиска, используя значения массива, в котором каждый узел хранит максимальное количество узлов в пути, начиная с самого узла и заканчивая на любом листе дерева.

Примечание . Максимальное количество узлов в пути от любого узла к любому конечному узлу в BST — это высота поддерева, укорененного в этом узле.

Примеры:

Input : arr[] = {1, 2, 3, 4, 5, 6, 7}
Output :
data = 1 height = 6
data = 2 height = 5
data = 3 height = 4
data = 4 height = 3
data = 5 height = 2
data = 6 height = 1
data = 7 height = 0

Input : arr[] = {4, 12, 10, 5, 11, 8, 7, 6, 9}
Output :
data = 4 height = 6
data = 5 height = 3
data = 6 height = 0
data = 7 height = 1
data = 8 height = 2
data = 9 height = 0
data = 10 height = 4
data = 11 height = 0
data = 12 height = 5

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

Допустим, существующее дерево (данные узла выделены красным, а текущая высота узла — зеленым):

Теперь мы собираемся добавить новый узел, содержащий значение 6, маршрут, пройденный узлом для добавления, выделен синим цветом:

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

Теперь мы собираемся добавить еще один узел, содержащий значение 9, а путь, по которому он будет добавлен в свою конечную позицию, выделен синим цветом:

Поскольку это изменение не влияет на высоту непосредственного родителя узла, содержащего значение 9, высота его родителя не будет затронута, и увеличение высоты не будет распространяться вверх.

Ниже приведена реализация вышеуказанного подхода:

// C реализация вышеуказанного подхода
#include <stdio.h>
#include <stdlib.h>

  
// Структура, содержащая базовый шаблон узла

struct node {

  

    // Сохраняет данные и текущую высоту узла

    int data;

    int height;

    struct node* right;

    struct node* left;

};

  

int indicator = 0;

void left_insert(struct node*, struct node*);

void right_insert(struct node*, struct node*);

  
// По обходу дерева

void traverse(struct node* head)

{

    if (head != NULL) {

        traverse(head->left);

        printf(" data   = %d", head->data);

        printf(" height = %d\n", head->height);

        traverse(head->right);

    }

}

  
// Вставка в левое поддерево

void left_insert(struct node* head, struct node* temp)

{

    // Дочерний узел текущей головы

    struct node* child = NULL;

  

    if (head->data > temp->data) {

        if (head->left == NULL) {

            indicator = 1;

            child = head->left = temp;

        }

        else {

            left_insert(head->left, temp);

            child = head->left;

        }

    }

    else {

        right_insert(head, temp);

    }

  

    if ((indicator == 1) && (child != NULL)) {

        if (head->height > child->height) {

            // Завершение распространения на высоту вышеупомянутых узлов

            indicator = 0;

        }

        else {

            head->height += 1;

        }

    }

}

  
// Вставка в правое поддерево

void right_insert(struct node* head, struct node* temp)

{

    // Дочерний узел текущей головы

    struct node* child = NULL;

  

    if (head->data < temp->data) {

        if (head->right == NULL) {

            indicator = 1;

            child = head->right = temp;

        }

        else {

            right_insert(head->right, temp);

            child = head->right;

        }

    }

    else {

        left_insert(head, temp);

    }

  

    if ((indicator == 1) && (child != NULL)) {

        if (head->height > child->height) {

  

            // Завершение распространения на высоту вышеупомянутых узлов

            indicator = 0;

        }

        else {

            head->height += 1;

        }

    }

}

  
// Функция для создания узла и push
// это в соответствующую позицию

void add_nodes(struct node** head, int value)

{

    struct node *temp_head = *head, *temp;

  

    if (*head == NULL) {

        // Когда добавлен первый узел

        *head = malloc(sizeof(**head));

        (*head)->data = value;

        (*head)->height = 0;

        (*head)->right = (*head)->left = NULL;

    }

    else {

        temp = malloc(sizeof(*temp));

        temp->data = value;

        temp->height = 0;

        temp->right = temp->left = NULL;

        left_insert(temp_head, temp);

        temp_head = *head;

        indicator = 0;

    }

}

  
// Код драйвера

int main()

{

    struct node *head = NULL, *temp_head = NULL;

  

    add_nodes(&head, 4);

    add_nodes(&head, 12);

    add_nodes(&head, 10);

    add_nodes(&head, 5);

    add_nodes(&head, 11);

    add_nodes(&head, 8);

    add_nodes(&head, 7);

    add_nodes(&head, 6);

    add_nodes(&head, 9);

  

    temp_head = head;

  

    // Обход дерева для отображения

    // обновленные значения высоты

    traverse(temp_head);

    return 0;

}

Выход:

 data   = 4 height = 6
 data   = 5 height = 3
 data   = 6 height = 0
 data   = 7 height = 1
 data   = 8 height = 2
 data   = 9 height = 0
 data   = 10 height = 4
 data   = 11 height = 0
 data   = 12 height = 5

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

Реализация BST, где каждый узел хранит максимальное количество узлов в пути до любого листа

0.00 (0%) 0 votes