Преобразование отсортированной DLL на месте в сбалансированный BST

01.01.2020Связанный список

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

Примеры:

Input:  Doubly Linked List 1  2  3
Output: A Balanced BST 
     2   
   /  \  
  1    3 


Input: Doubly Linked List 1  2 3  4 5  6  7
Output: A Balanced BST
        4
      /   \
     2     6
   /  \   / \
  1   3  4   7  

Input: Doubly Linked List 1  2  3  4
Output: A Balanced BST
      3   
    /  \  
   2    4 
 / 
1

Input:  Doubly Linked List 1  2  3  4  5  6
Output: A Balanced BST
      4   
    /   \  
   2     6 
 /  \   / 
1   3  5

Преобразование «Двойной связанный список» очень похоже на проблему «Единый связанный список», и метод 1 точно такой же, как метод 1 из предыдущего поста . Способ 2 тоже почти такой же. Единственное отличие в методе 2 состоит в том, что вместо выделения новых узлов для BST мы повторно используем одни и те же узлы DLL. Мы используем указатель prev как левый, а следующий указатель как правый.

Способ 1 (простой)
Ниже приведен простой алгоритм, в котором мы сначала находим средний узел списка и делаем его корнем дерева, которое будет построено.

1) Get the Middle of the linked list and make it root.
2) Recursively do same for left half and right half.
       a) Get the middle of left half and make it left child of the root
          created in step 1.
       b) Get the middle of right half and make it right child of the
          root created in step 1.

Временная сложность: O (nLogn), где n — количество узлов в связанном списке.

Метод 2 (хитрый)
Метод 1 строит дерево от корня до листьев. В этом методе мы строим от листьев до корня. Идея состоит в том, чтобы вставлять узлы в BST в том же порядке, что и в двусвязном списке, так что дерево может быть построено за O (n) временной сложности. Сначала мы посчитаем количество узлов в данном связанном списке. Пусть счет будет n. После подсчета узлов мы берем n / 2 левых узлов и рекурсивно создаем левое поддерево. После создания левого поддерева мы назначаем средний узел корневому узлу и связываем левое поддерево с корневым. Наконец, мы рекурсивно создаем правильное поддерево и связываем его с корнем.
При создании BST мы также продолжаем перемещать указатель заголовка списка на следующий, чтобы у нас был соответствующий указатель в каждом рекурсивном вызове.
Ниже приведена реализация метода 2. Основной код, который создает сбалансированный BST, выделен.

C ++

#include <bits/stdc++.h>

using namespace std;

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

class Node

{

public:

int data;

// Для дерева следующий указатель может быть

// используется как правый указатель поддерева

Node* next;

// Для дерева указатель prev может быть

// используется как указатель на левое поддерево

Node* prev;

};

// Вспомогательная функция для подсчета узлов в связанном списке

int countNodes(Node *head);

Node* sortedListToBSTRecur(Node **head_ref, int n);

/ * Эта функция считает количество
узлы в связанном списке, а затем вызывает
sortedListToBSTRecur () для построения BST * /
Node* sortedListToBST(Node *head)
{

/ * Подсчитать количество узлов в связанном списке * /

int n = countNodes(head);

/ * Построить BST * /

return sortedListToBSTRecur(&head, n);

}

/ * Основная функция, которая создает
сбалансированный BST и возвращает его корень.
head_ref -> указатель на указатель на
Головной узел двусвязного списка
n -> Количество узлов в двусвязном списке * /

Node* sortedListToBSTRecur(Node **head_ref, int n)

{

/* Базовый вариант */

if (n <= 0)

return NULL;

/ * Рекурсивно построить левое поддерево * /

Node *left = sortedListToBSTRecur(head_ref, n/2);

/ * head_ref теперь ссылается на средний узел,

сделать средний узел корнем BST * /

Node *root = *head_ref;

// Установить указатель на левое поддерево

root->prev = left;

/ * Изменить указатель головы связанного списка

для родительских рекурсивных вызовов * /

*head_ref = (*head_ref)->next;

/ * Рекурсивно построить правильное

поддерево и связать его с корнем

Количество узлов в правом поддереве

Всего узлов - узлов в

левое поддерево - 1 (для корня) * /

root->next = sortedListToBSTRecur(head_ref, n-n/2-1);

return root;

}

/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Вспомогательная функция, которая возвращает
количество узлов в данном связанном списке * /

int countNodes(Node *head)

{

int count = 0;

Node *temp = head;

while(temp)

{

temp = temp->next;

count++;

}

return count;

}

/ * Функция для вставки узла в
появление двусвязного списка * /

void push(Node** head_ref, int new_data)

{

/ * выделить узел * /

Node* new_node = new Node();

/ * вставить данные * /

new_node->data = new_data;

/ * так как мы добавляем в начале,

prev всегда NULL * /

new_node->prev = NULL;

/ * связать старый список с новым узлом * /

new_node->next = (*head_ref);

/ * изменить prev головного узла на новый узел * /

if((*head_ref) != NULL)

(*head_ref)->prev = new_node ;

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

(*head_ref) = new_node;

}

/ * Функция для печати узлов в заданном связанном списке * /

void printList(Node *node)

{

while (node!=NULL)

{

cout<<node->data<<" ";

node = node->next;

}

/ * Утилита для печати
предварительный обход BST * /

void preOrder(Node* node)

{

if (node == NULL)

return;

cout<<node->data<<" ";

preOrder(node->prev);

preOrder(node->next);

}

/ * Код водителя * /

int main()

{

/ * Начнем с пустого списка * /

Node* head = NULL;

/ * Давайте создадим отсортированный связанный список для проверки функций

Созданный связанный список будет 7-> 6-> 5-> 4-> 3-> 2-> 1 * /

push(&head, 7);

push(&head, 6);

push(&head, 5);

push(&head, 4);

push(&head, 3);

push(&head, 2);

push(&head, 1);

cout<<"Given Linked List\n";

printList(head);

/ * Конвертировать список в BST * /

Node *root = sortedListToBST(head);

cout<<"\nPreOrder Traversal of constructed BST \n ";

preOrder(root);

return 0;

}

// Этот код предоставлен rathbhupendra

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

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

struct Node

{

int data;

// Для дерева следующий указатель можно использовать как указатель на правое поддерево

struct Node* next;

// Для дерева указатель prev можно использовать как указатель на левое поддерево

struct Node* prev;

};

// Вспомогательная функция для подсчета узлов в связанном списке

int countNodes(struct Node *head);

struct Node* sortedListToBSTRecur(struct Node **head_ref, int n);

/ * Эта функция подсчитывает количество узлов в связанном списке и затем вызывает

sortedListToBSTRecur () для построения BST * /

struct Node* sortedListToBST(struct Node *head)

{

/ * Подсчитать количество узлов в связанном списке * /

int n = countNodes(head);

/ * Построить BST * /

return sortedListToBSTRecur(&head, n);

}

/ * Основная функция, которая создает сбалансированный BST и возвращает его корень.

head_ref -> указатель на указатель на головной узел двусвязного списка

n -> Количество узлов в двусвязном списке * /

struct Node* sortedListToBSTRecur(struct Node **head_ref, int n)

{

/* Базовый вариант */

if (n <= 0)

return NULL;

/ * Рекурсивно построить левое поддерево * /

struct Node *left = sortedListToBSTRecur(head_ref, n/2);

/ * head_ref теперь ссылается на средний узел, сделать средний узел корнем BST * /

struct Node *root = *head_ref;

// Установить указатель на левое поддерево

root->prev = left;

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

*head_ref = (*head_ref)->next;

/ * Рекурсивно построить правильное поддерево и связать его с root

Количество узлов в правом поддереве - это общее количество узлов - узлов в

левое поддерево - 1 (для корня) * /

root->next = sortedListToBSTRecur(head_ref, n-n/2-1);

return root;

}

/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Служебная функция, которая возвращает количество узлов в данном связанном списке * /

int countNodes(struct Node *head)

{

int count = 0;

struct Node *temp = head;

while(temp)

{

temp = temp->next;

count++;

}

return count;

}

/ * Функция для вставки узла при создании двусвязного списка * /

void push(struct Node** head_ref, int new_data)

{

/ * выделить узел * /

struct Node* new_node =

(struct Node*) malloc(sizeof(struct Node));

/ * вставить данные * /

new_node->data = new_data;

/ * так как мы добавляем в начале,

prev всегда NULL * /

new_node->prev = NULL;

/ * связать старый список с новым узлом * /

new_node->next = (*head_ref);

/ * изменить prev головного узла на новый узел * /

if((*head_ref) != NULL)

(*head_ref)->prev = new_node ;

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

(*head_ref) = new_node;

}

/ * Функция для печати узлов в заданном связанном списке * /

void printList(struct Node *node)

{

while (node!=NULL)

{

printf("%d ", node->data);

node = node->next;

}

/ * Утилита для печати предзаказа прохождения BST * /

void preOrder(struct Node* node)

{

if (node == NULL)

return;

printf("%d ", node->data);

preOrder(node->prev);

preOrder(node->next);

}

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

int main()

{

/ * Начнем с пустого списка * /

struct Node* head = NULL;

/ * Давайте создадим отсортированный связанный список для проверки функций

Созданный связанный список будет 7-> 6-> 5-> 4-> 3-> 2-> 1 * /

push(&head, 7);

push(&head, 6);

push(&head, 5);

push(&head, 4);

push(&head, 3);

push(&head, 2);

push(&head, 1);

printf("Given Linked List\n");

printList(head);

/ * Конвертировать список в BST * /

struct Node *root = sortedListToBST(head);

printf("\n PreOrder Traversal of constructed BST \n ");

preOrder(root);

return 0;

}

Джава

class Node

{

int data;

Node next, prev;

Node(int d)

{

data = d;

next = prev = null;

}

class LinkedList

{

Node head;

/ * Эта функция подсчитывает количество узлов в связанном списке

и затем вызывает sortedListToBSTRecur () для создания BST * /

Node sortedListToBST()

{

/ * Подсчитать количество узлов в связанном списке * /

int n = countNodes(head);

/ * Построить BST * /

return sortedListToBSTRecur(n);

}

/ * Основная функция, которая создает сбалансированный BST и

возвращает корень этого.

n -> Количество узлов в двусвязном списке * /

Node sortedListToBSTRecur(int n)

{

/* Базовый вариант */

if (n <= 0)

return null;

/ * Рекурсивно построить левое поддерево * /

Node left = sortedListToBSTRecur(n / 2);

/ * head_ref теперь ссылается на средний узел,

сделать средний узел корнем BST * /

Node root = head;

// Установить указатель на левое поддерево

root.prev = left;

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

рекурсивные вызовы * /

head = head.next;

/ * Рекурсивно построить правильное поддерево и связать его

с корнем. Количество узлов в правом поддереве

Всего узлов - узлов в левом поддереве - 1 (для корня) * /

root.next = sortedListToBSTRecur(n - n / 2 - 1);

return root;

}

/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /

/ * Вспомогательная функция, которая возвращает количество узлов в

данный связанный список * /

int countNodes(Node head)

{

int count = 0;

Node temp = head;

while (temp != null)

{

temp = temp.next;

count++;

}

return count;

}

/ * Функция для вставки узла при запуске

двусвязный список * /

void push(int new_data)

{

/ * выделить узел * /

Node new_node = new Node(new_data);

/ * так как мы добавляем в начале,

prev всегда NULL * /

new_node.prev = null;

/ * связать старый список с новым узлом * /

new_node.next = head;

/ * изменить prev головного узла на новый узел * /

if (head != null)

head.prev = new_node;

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

head = new_node;

}

/ * Функция для печати узлов в заданном связанном списке * /

void printList()

{

Node node = head;

while (node != null)

{

System.out.print(node.data + " ");

node = node.next;

}

/ * Утилита для печати предзаказа прохождения BST * /

void preOrder(Node node)

{

if (node == null)

return;

System.out.print(node.data + " ");

preOrder(node.prev);

preOrder(node.next);

}

/ * Сушилка для тестирования вышеуказанных функций * /

public static void main(String[] args)

{

LinkedList llist = new LinkedList();

/ * Давайте создадим отсортированный связанный список для проверки функций

Созданный связанный список будет 7-> 6-> 5-> 4-> 3-> 2-> 1 * /

llist.push(7);

llist.push(6);

llist.push(5);

llist.push(4);

llist.push(3);

llist.push(2);

llist.push(1);

System.out.println("Given Linked List ");

llist.printList();

/ * Конвертировать список в BST * /

Node root = llist.sortedListToBST();

System.out.println("");

System.out.println("Pre-Order Traversal of constructed BST ");

llist.preOrder(root);

}

}
// Этот код предоставлен Mayank Jaiswal (mayank_24)

Выход:

Given Linked List 
1 2 3 4 5 6 7 
Pre-Order Traversal of constructed BST 
4 2 1 3 6 5 7

Сложность времени: O (n)

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

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

Преобразование отсортированной DLL на месте в сбалансированный BST

0.00 (0%) 0 votes