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

01.01.2020Бинарное дерево поиска, Деревья

Дан отсортированный массив. Напишите функцию, которая создает сбалансированное дерево двоичного поиска с использованием элементов массива.

Примеры:

Input:  Array {1, 2, 3}
Output: A Balanced BST
     2
   /  \
  1    3 

Input: Array {1, 2, 3, 4}
Output: A Balanced BST
      3
    /  \
   2    4
 /
1

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

1) Get the Middle of the array 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.

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

C ++

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

using namespace std;

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

class TNode

{

public:

int data;

TNode* left;

TNode* right;

};

TNode* newNode(int data);

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

TNode* sortedArrayToBST(int arr[],

int start, int end)

{

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

if (start > end)

return NULL;

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

int mid = (start + end)/2;

TNode *root = newNode(arr[mid]);

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

и сделать его оставленным потомком root * /

root->left = sortedArrayToBST(arr, start,

mid - 1);

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

и сделайте это правильным потомком root * /

root->right = sortedArrayToBST(arr, mid + 1, end);

return root;

}

/ * Вспомогательная функция, которая выделяет новый узел
с данными данными и 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()

{

int arr[] = {1, 2, 3, 4, 5, 6, 7};

int n = sizeof(arr) / sizeof(arr[0]);

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

TNode *root = sortedArrayToBST(arr, 0, n-1);

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

preOrder(root);

return 0;

}

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

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

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

struct TNode

{

int data;

struct TNode* left;

struct TNode* right;

};

struct TNode* newNode(int data);

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

struct TNode* sortedArrayToBST(int arr[], int start, int end)

{

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

if (start > end)

return NULL;

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

int mid = (start + end)/2;

struct TNode *root = newNode(arr[mid]);

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

левый потомок корня * /

root->left = sortedArrayToBST(arr, start, mid-1);

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

правый потомок корня * /

root->right = sortedArrayToBST(arr, mid+1, end);

return root;

}

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

данные даны и 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()

{

int arr[] = {1, 2, 3, 4, 5, 6, 7};

int n = sizeof(arr)/sizeof(arr[0]);

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

struct TNode *root = sortedArrayToBST(arr, 0, n-1);

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

preOrder(root);

return 0;

}

Джава

// Java-программа для печати BST в заданном диапазоне

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

class Node {

int data;

Node left, right;

Node(int d) {

data = d;

left = right = null;

}

class BinaryTree {

static Node root;

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

из отсортированного массива * /

Node sortedArrayToBST(int arr[], int start, int end) {

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

if (start > end) {

return null;

}

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

int mid = (start + end) / 2;

Node node = new Node(arr[mid]);

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

левый потомок корня * /

node.left = sortedArrayToBST(arr, start, mid - 1);

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

правый потомок корня * /

node.right = sortedArrayToBST(arr, mid + 1, end);

return node;

}

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

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

BinaryTree tree = new BinaryTree();

int arr[] = new int[]{1, 2, 3, 4, 5, 6, 7};

int n = arr.length;

root = tree.sortedArrayToBST(arr, 0, n - 1);

System.out.println("Preorder traversal of constructed BST");

tree.preOrder(root);

}

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

питон

# Python код для преобразования отсортированного массива
# к сбалансированному бинарному дереву поиска

# двоичный узел дерева

class Node:

def __init__(self, d):

self.data = d

self.left = None

self.right = None

# функция для преобразования отсортированного массива в
# сбалансированный BST
# input: отсортированный массив целых чисел
# output: корневой узел сбалансированного BST

def sortedArrayToBST(arr):

if not arr:

return None

# найти середину

mid = (len(arr)) / 2

# сделать средний элемент корнем

root = Node(arr[mid])

# левое поддерево root имеет все

# значения <обр [середина]

root.left = sortedArrayToBST(arr[:mid])

# правильное поддерево root имеет все

# значения> обр [середина]

root.right = sortedArrayToBST(arr[mid+1:])

return root

# Полезная функция для печати предзаказа
# обход BST

def preOrder(node):

if not node:

return

print node.data,

preOrder(node.left)

preOrder(node.right)

# драйверная программа для проверки вышеуказанной функции
«»»
Построен сбалансированный BST

4

/ /
2 6
/ / / /
1 3 5 7
«»»

arr = [1, 2, 3, 4, 5, 6, 7]

root = sortedArrayToBST(arr)

print "PreOrder Traversal of constructed BST ",

preOrder(root)

# Этот код предоставлен Ишитой Трипати

C #

using System;

// C # программа для печати BST в заданном диапазоне

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

public class Node

{

public int data;

public Node left, right;

public Node(int d)

{

data = d;

left = right = null;

}

public class BinaryTree

{

public static Node root;

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

из отсортированного массива * /

public virtual Node sortedArrayToBST(int[] arr, int start, int end)

{

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

if (start > end)

{

return null;

}

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

int mid = (start + end) / 2;

Node node = new Node(arr[mid]);

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

левый потомок корня * /

node.left = sortedArrayToBST(arr, start, mid - 1);

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

правый потомок корня * /

node.right = sortedArrayToBST(arr, mid + 1, end);

return node;

}

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

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)

{

BinaryTree tree = new BinaryTree();

int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7};

int n = arr.Length;

root = tree.sortedArrayToBST(arr, 0, n - 1);

Console.WriteLine("Preorder traversal of constructed BST");

tree.preOrder(root);

}

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

Выход:

Preorder traversal of constructed BST
4 2 1 3 6 5 7

Сложность времени: O (n)
Ниже приведено рекуррентное отношение для sortedArrayToBST ().

  T(n) = 2T(n/2) + C
  T(n) -->  Time taken for an array of size n
   C   -->  Constant (Finding middle of array and linking root to left 
                      and right subtrees take constant time)

Вышеупомянутое повторение может быть решено с помощью основной теоремы, так как она попадает в случай 1.

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

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

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

0.00 (0%) 0 votes