Рубрики

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

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

    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;

    }

}

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

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