Рубрики

Конвертировать обычный BST в сбалансированный BST

Учитывая BST ( B inary S earch T ree), который может быть несбалансированным, преобразовать его в сбалансированный BST, который имеет минимально возможную высоту.

Примеры :

Input:
       30
      /
     20
    /
   10
Output:
     20
   /   \
 10     30


Input:
         4
        /
       3
      /
     2
    /
   1
Output:
      3            3           2
    /  \         /  \        /  \
   1    4   OR  2    4  OR  1    3   OR ..
    \          /                   \
     2        1                     4 

Input:
          4
        /   \
       3     5
      /       \
     2         6 
    /           \
   1             7
Output:
       4
    /    \
   2      6
 /  \    /  \
1    3  5    7 

Простое решение состоит в том, чтобы обойти узлы в Inorder и одну за другой вставить в самобалансирующееся BST, подобное дереву AVL. Временная сложность этого решения составляет O (n Log n), и это решение не гарантирует

Эффективное решение может построить сбалансированный BST за O (n) время с минимально возможной высотой. Ниже приведены шаги.

  1. Пройдите по указанному BST в порядке и сохраните результат в массиве. Этот шаг занимает O (N) времени. Обратите внимание, что этот массив будет отсортирован, так как обход по BST всегда производит отсортированную последовательность.
  2. Создайте сбалансированный BST из созданного выше отсортированного массива, используя рекурсивный подход, обсуждаемый здесь . Этот шаг также занимает O (n) времени, поскольку мы проходим каждый элемент ровно один раз, а обработка элемента занимает O (1) времени.

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

C ++

// C ++ программа для преобразования левого несбалансированного BST в
// сбалансированный BST
#include <bits/stdc++.h>

using namespace std;

  

struct Node

{

    int data;

    Node* left,  *right;

};

  
/ * Эта функция пересекает перекошенное двоичное дерево и

   хранит свои указатели узлов в векторных узлах [] * /

void storeBSTNodes(Node* root, vector<Node*> &nodes)

{

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

    if (root==NULL)

        return;

  

    // Сохраняем узлы в Inorder (который отсортирован

    // заказ на BST)

    storeBSTNodes(root->left, nodes);

    nodes.push_back(root);

    storeBSTNodes(root->right, nodes);

}

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

Node* buildTreeUtil(vector<Node*> &nodes, int start,

                   int end)

{

    // базовый вариант

    if (start > end)

        return NULL;

  

    / * Получить средний элемент и сделать его корневым * /

    int mid = (start + end)/2;

    Node *root = nodes[mid];

  

    / * Использование индекса в обходе Inorder, конструкция

       левый и правый субтресс * /

    root->left  = buildTreeUtil(nodes, start, mid-1);

    root->right = buildTreeUtil(nodes, mid+1, end);

  

    return root;

}

  
// Эта функция преобразует несбалансированный BST в
// сбалансированный BST
Node* buildTree(Node* root)
{

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

    vector<Node *> nodes;

    storeBSTNodes(root, nodes);

  

    // Создает BST из узлов []

    int n = nodes.size();

    return buildTreeUtil(nodes, 0, n-1);

}

  
// Сервисная функция для создания нового узла

Node* newNode(int data)

{

    Node* node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return (node);

}

  
/ * Функция для предварительного обхода дерева * /

void preOrder(Node* node)

{

    if (node == NULL)

        return;

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

    preOrder(node->left);

    preOrder(node->right);

}

  
// Драйвер программы

int main()

{

    / * Построенное перекошенное двоичное дерево

                10

               /

              8

             /

            7

           /

          6

         /

        5 * /

  

    Node* root = newNode(10);

    root->left = newNode(8);

    root->left->left = newNode(7);

    root->left->left->left = newNode(6);

    root->left->left->left->left = newNode(5);

  

    root = buildTree(root);

  

    printf("Preorder traversal of balanced "

            "BST is : \n");

    preOrder(root);

  

    return 0;

}

Джава

// Java-программа для преобразования левого несбалансированного BST в сбалансированный BST

  

import java.util.*;

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

   и указатель на правого ребенка * /

class Node 

{

    int data;

    Node left, right;

  

    public Node(int data) 

    {

        this.data = data;

        left = right = null;

    }

}

  

class BinaryTree 

{

    Node root;

  

    / * Эта функция пересекает перекошенное двоичное дерево и

       хранит свои указатели узлов в векторных узлах [] * /

    void storeBSTNodes(Node root, Vector<Node> nodes) 

    {

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

        if (root == null)

            return;

  

        // Сохраняем узлы в Inorder (который отсортирован

        // заказ на BST)

        storeBSTNodes(root.left, nodes);

        nodes.add(root);

        storeBSTNodes(root.right, nodes);

    }

  

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

    Node buildTreeUtil(Vector<Node> nodes, int start,

            int end) 

    {

        // базовый вариант

        if (start > end)

            return null;

  

        / * Получить средний элемент и сделать его корневым * /

        int mid = (start + end) / 2;

        Node node = nodes.get(mid);

  

        / * Использование индекса в обходе Inorder, конструкция

           левый и правый субтресс * /

        node.left = buildTreeUtil(nodes, start, mid - 1);

        node.right = buildTreeUtil(nodes, mid + 1, end);

  

        return node;

    }

  

    // Эта функция преобразует несбалансированный BST в

    // сбалансированный BST

    Node buildTree(Node root) 

    {

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

        Vector<Node> nodes = new Vector<Node>();

        storeBSTNodes(root, nodes);

  

        // Создает BST из узлов []

        int n = nodes.size();

        return buildTreeUtil(nodes, 0, n - 1);

    }

  

    / * Функция для предварительного обхода дерева * /

    void preOrder(Node node) 

    {

        if (node == null)

            return;

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

        preOrder(node.left);

        preOrder(node.right);

    }

  

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

    public static void main(String[] args) 

    {

         / * Построенное перекошенное двоичное дерево

                10

               /

              8

             /

            7

           /

          6

         /

        5 * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

        tree.root.left = new Node(8);

        tree.root.left.left = new Node(7);

        tree.root.left.left.left = new Node(6);

        tree.root.left.left.left.left = new Node(5);

  

        tree.root = tree.buildTree(tree.root);

        System.out.println("Preorder traversal of balanced BST is :");

        tree.preOrder(tree.root);

    }

}

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

python3

# Python3 программа для преобразования левого
# несбалансированный BST к сбалансированному BST

import sys

import math

  
# Узел двоичного дерева содержит данные, указатель на левый дочерний элемент
# и указатель на правого ребенка

class Node:

    def __init__(self,data):

        self.data=data

        self.left=None

        self.right=None

  
# Эта функция пересекает перекошенное двоичное дерево и
# хранит свои указатели узлов в векторных узлах []

def storeBSTNodes(root,nodes):

      

    # Базовый вариант

    if not root:

        return

      

    # Хранить узлы в Inorder (который отсортирован

    # заказ на BST)

    storeBSTNodes(root.left,nodes)

    nodes.append(root)

    storeBSTNodes(root.right,nodes)

  
# Рекурсивная функция для построения двоичного дерева

def buildTreeUtil(nodes,start,end):

      

    # базовый вариант

    if start>end:

        return None

  

    # Получить средний элемент и сделать его корневым

    mid=(start+end)//2

    node=nodes[mid]

  

    # Использование индекса в обходе Inorder, конструкция

    # левый и правый субтресс

    node.left=buildTreeUtil(nodes,start,mid-1)

    node.right=buildTreeUtil(nodes,mid+1,end)

    return node

  
# Эта функция преобразует несбалансированный BST в
# сбалансированный BST

def buildTree(root):

      

    # Хранить узлы данного BST в отсортированном порядке

    nodes=[]

    storeBSTNodes(root,nodes)

  

    # Создает BST из узлов []

    n=len(nodes)

    return buildTreeUtil(nodes,0,n-1)

  
# Функция для предварительного обхода дерева

def preOrder(root):

    if not root:

        return

    print("{} ".format(root.data),end="")

    preOrder(root.left)

    preOrder(root.right)

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

if __name__=='__main__':

    # Построено перекошенное двоичное дерево

    № 10

    # /

    № 8

    # /

    № 7

    # /

    № 6

    # /

    № 5

    root = Node(10)

    root.left = Node(8)

    root.left.left = Node(7)

    root.left.left.left = Node(6)

    root.left.left.left.left = Node(5)

    root = buildTree(root)

    print("Preorder traversal of balanced BST is :")

    preOrder(root)

      
# Этот код предоставлен Викашем Кумаром 37

C #

using System;

using System.Collections.Generic;

  
// C # программа для преобразования левого несбалансированного BST в сбалансированный BST

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

   и указатель на правого ребенка * /

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int data)

    {

        this.data = data;

        left = right = null;

    }

}

  

public class BinaryTree

{

    public Node root;

  

    / * Эта функция пересекает перекошенное двоичное дерево и

       хранит свои указатели узлов в векторных узлах [] * /

    public virtual void storeBSTNodes(Node root, List<Node> nodes)

    {

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

        if (root == null)

        {

            return;

        }

  

        // Сохраняем узлы в Inorder (который отсортирован

        // заказ на BST)

        storeBSTNodes(root.left, nodes);

        nodes.Add(root);

        storeBSTNodes(root.right, nodes);

    }

  

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

    public virtual Node buildTreeUtil(List<Node> nodes, int start, int end)

    {

        // базовый вариант

        if (start > end)

        {

            return null;

        }

  

        / * Получить средний элемент и сделать его корневым * /

        int mid = (start + end) / 2;

        Node node = nodes[mid];

  

        / * Использование индекса в обходе Inorder, конструкция

           левый и правый субтресс * /

        node.left = buildTreeUtil(nodes, start, mid - 1);

        node.right = buildTreeUtil(nodes, mid + 1, end);

  

        return node;

    }

  

    // Эта функция преобразует несбалансированный BST в

    // сбалансированный BST

    public virtual Node buildTree(Node root)

    {

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

        List<Node> nodes = new List<Node>();

        storeBSTNodes(root, nodes);

  

        // Создает BST из узлов []

        int n = nodes.Count;

        return buildTreeUtil(nodes, 0, n - 1);

    }

  

    / * Функция для предварительного обхода дерева * /

    public virtual void preOrder(Node node)

    {

        if (node == null)

        {

            return;

        }

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

        preOrder(node.left);

        preOrder(node.right);

    }

  

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

    public static void Main(string[] args)

    {

         / * Построенное перекошенное двоичное дерево

                10

               /

              8

             /

            7

           /

          6

         /

        5 * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

        tree.root.left = new Node(8);

        tree.root.left.left = new Node(7);

        tree.root.left.left.left = new Node(6);

        tree.root.left.left.left.left = new Node(5);

  

        tree.root = tree.buildTree(tree.root);

        Console.WriteLine("Preorder traversal of balanced BST is :");

        tree.preOrder(tree.root);

    }

}

  

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

Выход :

Preorder traversal of balanced BST is : 
7 5 6 8 10 

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотели бы внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Конвертировать обычный BST в сбалансированный BST

0.00 (0%) 0 votes