Рубрики

Сортированный связанный список с сбалансированным BST

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

Примеры:

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


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

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

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

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

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

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

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

Ниже приведена реализация метода 2. Основной код, который создает сбалансированный BST, выделен.

C ++

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

using namespace std;

  
/ * Узел списка ссылок * /

class LNode 

    public:

    int data; 

    LNode* next; 

}; 

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

class TNode 

    public:

    int data; 

    TNode* left; 

    TNode* right; 

}; 

  

TNode* newNode(int data); 

int countLNodes(LNode *head); 

TNode* sortedListToBSTRecur(LNode **head_ref, int n); 

  

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

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

    int n = countLNodes(head); 

  

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

    return sortedListToBSTRecur(&head, n); 

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

TNode* sortedListToBSTRecur(LNode **head_ref, int n) 

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

    if (n <= 0) 

        return NULL; 

  

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

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

  

    / * Выделить память для root, и

    ссылка выше построена слева

    поддерево с корнем * /

    TNode *root = newNode((*head_ref)->data); 

    root->left = left; 

  

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

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

    *head_ref = (*head_ref)->next; 

  

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

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

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

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

        левое поддерево - 1 (для корня), которое равно nn / 2-1 * /

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

  

    return root; 

  

  

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

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

int countLNodes(LNode *head) 

    int count = 0; 

    LNode *temp = head; 

    while(temp) 

    

        temp = temp->next; 

        count++; 

    

    return count; 

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

void push(LNode** head_ref, int new_data) 

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

    LNode* new_node = new LNode();

      

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

    new_node->data = new_data; 

  

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

    new_node->next = (*head_ref); 

  

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

    (*head_ref) = new_node; 

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

void printList(LNode *node) 

    while(node!=NULL) 

    

        cout << node->data << " "

        node = node->next; 

    

  
/ * Вспомогательная функция, которая выделяет новый узел с
данные даны и NULL левый и правый указатели. * /

TNode* newNode(int data) 

    TNode* node = new TNode();

    node->data = data; 

    node->left = NULL; 

    node->right = NULL; 

  

    return node; 

  
/ * Полезная функция для
предварительный заказ печати BST * /

void preOrder(TNode* node) 

    if (node == NULL) 

        return

    cout<<node->data<<" "

    preOrder(node->left); 

    preOrder(node->right); 

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

int main() 

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

    LNode* head = NULL; 

  

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

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

    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 "

    printList(head); 

  

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

    TNode *root = sortedListToBST(head); 

    cout<<"\nPreOrder Traversal of constructed BST "

    preOrder(root); 

  

    return 0; 

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

С

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

  
/ * Узел списка ссылок * /

struct LNode

{

    int data;

    struct LNode* next;

};

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

struct TNode

{

    int data;

    struct TNode* left;

    struct TNode* right;

};

  

struct TNode* newNode(int data);

int countLNodes(struct LNode *head);

struct TNode* sortedListToBSTRecur(struct LNode **head_ref, int n);

  

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

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

struct TNode* sortedListToBST(struct LNode *head)

{

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

    int n = countLNodes(head);

  

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

    return sortedListToBSTRecur(&head, n);

}

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

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

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

struct TNode* sortedListToBSTRecur(struct LNode **head_ref, int n)

{

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

    if (n <= 0)

        return NULL;

  

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

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

  

    / * Выделить память для root и связать созданный выше левый

       поддерево с корнем * /

    struct TNode *root = newNode((*head_ref)->data);

    root->left = left;

  

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

    *head_ref = (*head_ref)->next;

  

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

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

      левое поддерево - 1 (для корня), которое равно nn / 2-1 * /

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

  

    return root;

}

  

  

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

  
/ * Служебная функция, которая возвращает количество узлов в данном связанном списке * /

int countLNodes(struct LNode *head)

{

    int count = 0;

    struct LNode *temp = head;

    while(temp)

    {

        temp = temp->next;

        count++;

    }

    return count;

}

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

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

{

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

    struct LNode* new_node =

        (struct LNode*) malloc(sizeof(struct LNode));

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

    new_node->data  = new_data;

  

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

    new_node->next = (*head_ref);

  

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

    (*head_ref)    = new_node;

}

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

void printList(struct LNode *node)

{

    while(node!=NULL)

    {

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

        node = node->next;

    }

}

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

   данные даны и NULL левый и правый указатели. * /

struct TNode* newNode(int data)

{

    struct TNode* node = (struct TNode*)

                         malloc(sizeof(struct TNode));

    node->data = data;

    node->left = NULL;

    node->right = NULL;

  

    return node;

}

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

void preOrder(struct TNode* node)

{

    if (node == NULL)

        return;

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

    preOrder(node->left);

    preOrder(node->right);

}

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

int main()

{

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

    struct LNode* head = NULL;

  

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

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

    push(&head, 7);

    push(&head, 6);

    push(&head, 5);

    push(&head, 4);

    push(&head, 3);

    push(&head, 2);

    push(&head, 1);

  

    printf("\n Given Linked List ");

    printList(head);

  

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

    struct TNode *root = sortedListToBST(head);

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

    preOrder(root);

  

    return 0;

}

Джава

class LinkedList {

  

    / * головной узел списка ссылок * /

    static LNode head;

      

    / * Узел списка ссылок * /

    class LNode 

    {

        int data;

        LNode next, prev;

  

        LNode(int d) 

        {

            data = d;

            next = prev = null;

        }

    }

      

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

    class TNode 

    {

        int data;

        TNode left, right;

  

        TNode(int d) 

        {

            data = d;

            left = right = null;

        }

    }

  

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

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

    TNode sortedListToBST() 

    {

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

        int n = countNodes(head);

  

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

        return sortedListToBSTRecur(n);

    }

  

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

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

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

    TNode sortedListToBSTRecur(int n) 

    {

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

        if (n <= 0

            return null;

  

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

        TNode left = sortedListToBSTRecur(n / 2);

  

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

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

        TNode root = new TNode(head.data);

  

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

        root.left = left;

  

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

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

        head = head.next;

  

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

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

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

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

  

        return root;

    }

  

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

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

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

    int countNodes(LNode head) 

    {

        int count = 0;

        LNode temp = head;

        while (temp != null)

        {

            temp = temp.next;

            count++;

        }

        return count;

    }

  

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

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

    void push(int new_data) 

    {

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

        LNode new_node = new LNode(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(LNode node) 

    {

        while (node != null

        {

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

            node = node.next;

        }

    }

  

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

    void preOrder(TNode node) 

    {

        if (node == null)

            return;

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

        preOrder(node.left);

        preOrder(node.right);

    }

  

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

    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(head);

  

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

        TNode root = llist.sortedListToBST();

        System.out.println("");

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

        llist.preOrder(root);

    }

}

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

C #

// C # реализация вышеуказанного подхода

using System;

      

public class LinkedList 

{

  

    / * головной узел списка ссылок * /

    static LNode head;

      

    / * Узел списка ссылок * /

    class LNode 

    {

        public int data;

        public LNode next, prev;

  

        public LNode(int d) 

        {

            data = d;

            next = prev = null;

        }

    }

      

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

    class TNode 

    {

        public int data;

        public TNode left, right;

  

        public TNode(int d) 

        {

            data = d;

            left = right = null;

        }

    }

  

    / * Эта функция считает число

    узлов в связанном списке, а затем вызывает

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

    TNode sortedListToBST() 

    {

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

        int n = countNodes(head);

  

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

        return sortedListToBSTRecur(n);

    }

  

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

     сбалансированный BST и возвращает его корень.

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

    TNode sortedListToBSTRecur(int n) 

    {

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

        if (n <= 0) 

            return null;

  

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

        TNode left = sortedListToBSTRecur(n / 2);

  

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

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

        TNode root = new TNode(head.data);

  

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

        root.left = left;

  

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

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

        head = head.next;

  

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

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

        с корнем. Номер

        узлы в правом поддереве

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

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

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

  

        return root;

    }

  

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

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

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

    int countNodes(LNode head) 

    {

        int count = 0;

        LNode temp = head;

        while (temp != null)

        {

            temp = temp.next;

            count++;

        }

        return count;

    }

  

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

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

    void push(int new_data) 

    {

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

        LNode new_node = new LNode(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(LNode node) 

    {

        while (node != null

        {

            Console.Write(node.data + " ");

            node = node.next;

        }

    }

  

    / * Утилита для печати

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

    void preOrder(TNode node) 

    {

        if (node == null)

            return;

        Console.Write(node.data + " ");

        preOrder(node.left);

        preOrder(node.right);

    }

  

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

    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);

  

        Console.WriteLine("Given Linked List ");

        llist.printList(head);

  

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

        TNode root = llist.sortedListToBST();

        Console.WriteLine("");

        Console.WriteLine("Pre-Order Traversal of constructed BST ");

        llist.preOrder(root);

    }

}

  
// Этот код предоставлен Rajput-Ji

Выход:

Given Linked List 1 2 3 4 5 6 7 
 PreOrder Traversal of constructed BST 4 2 1 3 6 5 7

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

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

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

Сортированный связанный список с сбалансированным BST

0.00 (0%) 0 votes