Проверьте, сбалансировано ли данное Двоичное Дерево как Красно-Черное Дерево

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

В красно-черном дереве максимальная высота узла не более чем в два раза превышает минимальную высоту ( Четыре красно-черных свойства дерева гарантируют, что это всегда соблюдается). Учитывая бинарное дерево поиска, нам нужно проверить следующее свойство.
Для каждого узла длина самого длинного пути от листа к узлу имеет не более чем вдвое больше узлов на кратчайшем пути от узла к листу.

    12                                        40
      \                                     /    \ 
       14                                 10      100    
         \                                        /  \
          16                                     60   150    
 Cannot be a Red-Black Tree              It can be Red-Black Tree
 with any color assignment
 Max height of 12 is 1
 Min height of 12 is 3


          10
        /   \
      5     100
           /   \
          50   150
         /
        40 
 It can also be Red-Black Tree

Ожидаемая сложность времени O (n). Дерево должно быть пройдено не более одного раза в решении.

Мы настоятельно рекомендуем свернуть браузер и попробовать это в первую очередь.
Для каждого узла нам нужно получить максимальную и минимальную высоты и сравнить их. Идея состоит в том, чтобы пройти по дереву и для каждого узла проверить, сбалансировано ли оно. Нам нужно написать рекурсивную функцию, которая возвращает три вещи: логическое значение, указывающее, сбалансировано дерево или нет, минимальная высота и максимальная высота. Чтобы вернуть несколько значений, мы можем использовать структуру или передать переменные по ссылке. Мы передали maxh и minh по ссылке, чтобы значения могли использоваться в родительских вызовах.

C ++

/ * Программа для проверки того, сбалансировано ли данное двоичное дерево как красно-черное дерево * /
#include <iostream>

using namespace std;

struct Node

{

int key;

Node *left, *right;

};

/ * утилита, которая выделяет новый узел с данным ключом * /

Node* newNode(int key)

{

Node* node = new Node;

node->key = key;

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

return (node);

}

// Возвращает дерево возврата, если двоичное дерево сбалансировано как красно-черный
// дерево. Эта функция также устанавливает значение в maxh и minh (передается
// ссылка). maxh и minh устанавливаются как максимальная и минимальная высота корня.

bool isBalancedUtil(Node *root, int &maxh, int &minh)

{

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

if (root == NULL)

{

maxh = minh = 0;

return true;

}

int lmxh, lmnh; // Для сохранения максимальной и минимальной высоты левого поддерева

int rmxh, rmnh; // Для сохранения максимальной и минимальной высоты правого поддерева

// Проверить, сбалансировано ли левое поддерево, также установить lmxh и lmnh

if (isBalancedUtil(root->left, lmxh, lmnh) == false)

return false;

// Проверить, сбалансировано ли правое поддерево, также установить rmxh и rmnh

if (isBalancedUtil(root->right, rmxh, rmnh) == false)

return false;

// Устанавливаем максимальную и минимальную высоты этого узла для родительского вызова

maxh = max(lmxh, rmxh) + 1;

minh = min(lmnh, rmnh) + 1;

// Посмотрим, сбалансирован ли этот узел

if (maxh <= 2*minh)

return true;

return false;

}

// Обёртка над isBalancedUtil ()

bool isBalanced(Node *root)

{

int maxh, minh;

return isBalancedUtil(root, maxh, minh);

}

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

int main()

{

Node * root = newNode(10);

root->left = newNode(5);

root->right = newNode(100);

root->right->left = newNode(50);

root->right->right = newNode(150);

root->right->left->left = newNode(40);

isBalanced(root)? cout << "Balanced" : cout << "Not Balanced";

return 0;

}

Джава

// Java-программа для проверки, является ли данный двоичный файл
// Дерево сбалансировано как красно-черное дерево

class GFG

{

static class Node

{

int key;

Node left, right;

Node(int key)

{

left = null;

right = null;

this.key = key;

}

static class INT

{

static int d;

INT()

{

d = 0;

}

// Возвращает возвращает дерево, если Двоичный
// дерево сбалансировано как красно-черное
// дерево. Эта функция также устанавливает значение
// в maxh и minh (передается по ссылке).
// maxh и minh устанавливаются как максимальные и
// минимальная высота корня.

static boolean isBalancedUtil(Node root,

INT maxh, INT minh)

{

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

if (root == null)

{

maxh.d = minh.d = 0;

return true;

}

// Для сохранения максимальной и минимальной высоты левого поддерева

INT lmxh=new INT(), lmnh=new INT();

// Для сохранения максимальной и минимальной высоты правого поддерева

INT rmxh=new INT(), rmnh=new INT();

// Проверить, сбалансировано ли левое поддерево,

// также устанавливаем lmxh и lmnh

if (isBalancedUtil(root.left, lmxh, lmnh) == false)

return false;

// Проверить, сбалансировано ли правильное поддерево,

// также устанавливаем rmxh и rmnh

if (isBalancedUtil(root.right, rmxh, rmnh) == false)

return false;

// Устанавливаем максимальную и минимальную высоты

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

maxh.d = Math.max(lmxh.d, rmxh.d) + 1;

minh.d = Math.min(lmnh.d, rmnh.d) + 1;

// Посмотрим, сбалансирован ли этот узел

if (maxh.d <= 2*minh.d)

return true;

return false;

}

// Обёртка над isBalancedUtil ()

static boolean isBalanced(Node root)

{

INT maxh=new INT(), minh=new INT();

return isBalancedUtil(root, maxh, minh);

}

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

public static void main(String args[])

{

Node root = new Node(10);

root.left = new Node(5);

root.right = new Node(100);

root.right.left = new Node(50);

root.right.right = new Node(150);

root.right.left.left = new Node(40);

System.out.println(isBalanced(root) ?

"Balanced" : "Not Balanced");

}
}

// Этот код предоставлен Арнабом Кунду

python3

"" "Программа для проверки наличия данного двоичного файла
Дерево сбалансировано, как красно-черное дерево "" "

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

class newNode:

# Конструкция для создания нового узла

def __init__(self, key):

self.data = key

self.left = None

self.right = None

# Возвращает возвращает дерево, если Двоичный
# дерево сбалансировано как красно-черное
# дерево. Эта функция также устанавливает значение
# в maxh и minh (мимо
# ссылка). maxh и minh установлены
# как максимальная и минимальная высота корня.

def isBalancedUtil(root, maxh, minh) :

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

if (root == None) :

maxh = minh = 0

return True

lmxh=0

# Для хранения макс и мин

# высоты левого поддерева

lmnh=0

# Для хранения макс и мин

# высоты правого поддерева

rmxh, rmnh=0,0

# Проверьте, сбалансировано ли левое поддерево,

# также установите lmxh и lmnh

if (isBalancedUtil(root.left, lmxh, lmnh) == False) :

return False

# Проверьте, сбалансировано ли правильное поддерево,

# также установите rmxh и rmnh

if (isBalancedUtil(root.right, rmxh, rmnh) == False) :

return False

# Установите максимальную и минимальную высоты

# этот узел для родительского вызова

maxh = max(lmxh, rmxh) + 1

minh = min(lmnh, rmnh) + 1

# Проверьте, сбалансирован ли этот узел

if (maxh <= 2 * minh) :

return True

return False

# Обёртка над isBalancedUtil ()

def isBalanced(root) :

maxh, minh =0,0

return isBalancedUtil(root, maxh, minh)

Код водителя

if __name__ == '__main__':

root = newNode(10)

root.left = newNode(5)

root.right = newNode(100)

root.right.left = newNode(50)

root.right.right = newNode(150)

root.right.left.left = newNode(40)

if (isBalanced(root)):

print("Balanced")

else:

print("Not Balanced")

# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

// C # Программа для проверки, если данный бинарный
// Дерево сбалансировано как красно-черное дерево

using System;

class GFG

{

public class Node

{

public int key;

public Node left, right;

public Node(int key)

{

left = null;

right = null;

this.key = key;

}

public class INT

{

public int d;

public INT()

{

d = 0;

}

static bool isBalancedUtil(Node root,

INT maxh, INT minh)

{

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

if (root == null)

{

maxh.d = minh.d = 0;

return true;

}

// Для сохранения максимальной и минимальной высоты левого поддерева

INT lmxh = new INT(), lmnh = new INT();

// Для сохранения максимальной и минимальной высоты правого поддерева

INT rmxh = new INT(), rmnh = new INT();

// Проверить, сбалансировано ли левое поддерево,

// также устанавливаем lmxh и lmnh

if (isBalancedUtil(root.left, lmxh, lmnh) == false)

return false;

// Проверить, сбалансировано ли правильное поддерево,

// также устанавливаем rmxh и rmnh

if (isBalancedUtil(root.right, rmxh, rmnh) == false)

return false;

// Устанавливаем максимальную и минимальную высоты

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

maxh.d = Math.Max(lmxh.d, rmxh.d) + 1;

minh.d = Math.Min(lmnh.d, rmnh.d) + 1;

// Посмотрим, сбалансирован ли этот узел

if (maxh.d <= 2 * minh.d)

return true;

return false;

}

// Обёртка над isBalancedUtil ()

static bool isBalanced(Node root)

{

INT maxh = new INT(), minh = new INT();

return isBalancedUtil(root, maxh, minh);

}

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

public static void Main(String []args)

{

Node root = new Node(10);

root.left = new Node(5);

root.right = new Node(100);

root.right.left = new Node(50);

root.right.right = new Node(150);

root.right.left.left = new Node(40);

Console.WriteLine(isBalanced(root) ?

"Balanced" : "Not Balanced");

}
}

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

Выход:

Balanced

Сложность времени: Сложность времени вышеприведенного кода равна O (n), так как код выполняет простой обход дерева.

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

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

Проверьте, сбалансировано ли данное Двоичное Дерево как Красно-Черное Дерево

0.00 (0%) 0 votes