En un árbol rojo-negro , la altura máxima de un Node es como máximo el doble de la altura mínima ( las cuatro propiedades del árbol rojo-negro aseguran que esto siempre se cumpla). Dado un árbol de búsqueda binario, debemos verificar la siguiente propiedad.
Para cada Node, la longitud del camino más largo de hoja a Node no tiene más del doble de los Nodes en el camino más corto de Node a hoja.
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
La complejidad de tiempo esperada es O(n). El árbol debe atravesarse como máximo una vez en la solución.
Recomendamos encarecidamente minimizar el navegador y probarlo usted mismo primero.
Para cada Node, necesitamos obtener las alturas máxima y mínima y compararlas. La idea es atravesar el árbol y para cada Node comprobar si está equilibrado. Necesitamos escribir una función recursiva que devuelva tres cosas, un valor booleano para indicar que el árbol está balanceado o no, altura mínima y altura máxima. Para devolver múltiples valores, podemos usar una estructura o pasar variables por referencia. Hemos pasado maxh y minh por referencia para que los valores se puedan usar en las llamadas a los padres.
Implementación:
C++
/* Program to check if a given Binary Tree is balanced like a Red-Black Tree */
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int key;
Node *left, *right;
};
/* utility that allocates a new Node with the given key */
Node* newNode(int key)
{
Node* node = new Node;
node->key = key;
node->left = node->right = NULL;
return (node);
}
// Returns returns tree if the Binary tree is balanced like a Red-Black
// tree. This function also sets value in maxh and minh (passed by
// reference). maxh and minh are set as maximum and minimum heights of root.
bool isBalancedUtil(Node *root, int &maxh, int &minh)
{
// Base case
if (root == NULL)
{
maxh = minh = 0;
return true;
}
int lmxh, lmnh; // To store max and min heights of left subtree
int rmxh, rmnh; // To store max and min heights of right subtree
// Check if left subtree is balanced, also set lmxh and lmnh
if (isBalancedUtil(root->left, lmxh, lmnh) == false)
return false;
// Check if right subtree is balanced, also set rmxh and rmnh
if (isBalancedUtil(root->right, rmxh, rmnh) == false)
return false;
// Set the max and min heights of this node for the parent call
maxh = max(lmxh, rmxh) + 1;
minh = min(lmnh, rmnh) + 1;
// See if this node is balanced
if (maxh <= 2*minh)
return true;
return false;
}
// A wrapper over isBalancedUtil()
bool isBalanced(Node *root)
{
int maxh, minh;
return isBalancedUtil(root, maxh, minh);
}
/* Driver program to test above functions*/
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
// Java Program to check if a given Binary
// Tree is balanced like a Red-Black Tree
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;
}
}
// Returns returns tree if the Binary
// tree is balanced like a Red-Black
// tree. This function also sets value
// in maxh and minh (passed by reference).
// maxh and minh are set as maximum and
// minimum heights of root.
static boolean isBalancedUtil(Node root,
INT maxh, INT minh)
{
// Base case
if (root == null)
{
maxh.d = minh.d = 0;
return true;
}
// To store max and min heights of left subtree
INT lmxh=new INT(), lmnh=new INT();
// To store max and min heights of right subtree
INT rmxh=new INT(), rmnh=new INT();
// Check if left subtree is balanced,
// also set lmxh and lmnh
if (isBalancedUtil(root.left, lmxh, lmnh) == false)
return false;
// Check if right subtree is balanced,
// also set rmxh and rmnh
if (isBalancedUtil(root.right, rmxh, rmnh) == false)
return false;
// Set the max and min heights
// of this node for the parent call
maxh.d = Math.max(lmxh.d, rmxh.d) + 1;
minh.d = Math.min(lmnh.d, rmnh.d) + 1;
// See if this node is balanced
if (maxh.d <= 2*minh.d)
return true;
return false;
}
// A wrapper over isBalancedUtil()
static boolean isBalanced(Node root)
{
INT maxh=new INT(), minh=new INT();
return isBalancedUtil(root, maxh, minh);
}
// Driver code
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");
}
}
// This code is contributed by Arnab Kundu
Python3
""" Program to check if a given Binary
Tree is balanced like a Red-Black Tree """
# Helper function that allocates a new
# node with the given data and None
# left and right pointers.
class newNode:
# Construct to create a new node
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# Returns returns tree if the Binary
# tree is balanced like a Red-Black
# tree. This function also sets value
# in maxh and minh (passed by
# reference). maxh and minh are set
# as maximum and minimum heights of root.
def isBalancedUtil(root, maxh, minh) :
# Base case
if (root == None) :
maxh = minh = 0
return True
lmxh=0
# To store max and min
# heights of left subtree
lmnh=0
# To store max and min
# heights of right subtree
rmxh, rmnh=0,0
# Check if left subtree is balanced,
# also set lmxh and lmnh
if (isBalancedUtil(root.left, lmxh, lmnh) == False) :
return False
# Check if right subtree is balanced,
# also set rmxh and rmnh
if (isBalancedUtil(root.right, rmxh, rmnh) == False) :
return False
# Set the max and min heights of
# this node for the parent call
maxh = max(lmxh, rmxh) + 1
minh = min(lmnh, rmnh) + 1
# See if this node is balanced
if (maxh <= 2 * minh) :
return True
return False
# A wrapper over isBalancedUtil()
def isBalanced(root) :
maxh, minh =0,0
return isBalancedUtil(root, maxh, minh)
# Driver Code
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")
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# Program to check if a given Binary
// Tree is balanced like a Red-Black Tree
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;
}
}
// Returns returns tree if the Binary
// tree is balanced like a Red-Black
// tree. This function also sets value
// in maxh and minh (passed by reference).
// maxh and minh are set as maximum and
// minimum heights of root.
static bool isBalancedUtil(Node root,
INT maxh, INT minh)
{
// Base case
if (root == null)
{
maxh.d = minh.d = 0;
return true;
}
// To store max and min heights of left subtree
INT lmxh = new INT(), lmnh = new INT();
// To store max and min heights of right subtree
INT rmxh = new INT(), rmnh = new INT();
// Check if left subtree is balanced,
// also set lmxh and lmnh
if (isBalancedUtil(root.left, lmxh, lmnh) == false)
return false;
// Check if right subtree is balanced,
// also set rmxh and rmnh
if (isBalancedUtil(root.right, rmxh, rmnh) == false)
return false;
// Set the max and min heights
// of this node for the parent call
maxh.d = Math.Max(lmxh.d, rmxh.d) + 1;
minh.d = Math.Min(lmnh.d, rmnh.d) + 1;
// See if this node is balanced
if (maxh.d <= 2 * minh.d)
return true;
return false;
}
// A wrapper over isBalancedUtil()
static bool isBalanced(Node root)
{
INT maxh = new INT(), minh = new INT();
return isBalancedUtil(root, maxh, minh);
}
// Driver code
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");
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript Program to check if a given Binary
// Tree is balanced like a Red-Black Tree
class Node {
constructor(val) {
this.key = val;
this.left = null;
this.right = null;
}
}
class INT {
constructor() {
this.d = 0;
}
}
// Returns returns tree if the Binary
// tree is balanced like a Red-Black
// tree. This function also sets value
// in maxh and minh (passed by reference).
// maxh and minh are set as maximum and
// minimum heights of root.
function isBalancedUtil(root, maxh, minh) {
// Base case
if (root == null) {
maxh.d = minh.d = 0;
return true;
}
// To store max and min heights of left subtree
var lmxh = new INT(), lmnh = new INT();
// To store max and min heights of right subtree
var rmxh = new INT(), rmnh = new INT();
// Check if left subtree is balanced,
// also set lmxh and lmnh
if (isBalancedUtil(root.left, lmxh, lmnh) == false)
return false;
// Check if right subtree is balanced,
// also set rmxh and rmnh
if (isBalancedUtil(root.right, rmxh, rmnh) == false)
return false;
// Set the max and min heights
// of this node for the parent call
maxh.d = Math.max(lmxh.d, rmxh.d) + 1;
minh.d = Math.min(lmnh.d, rmnh.d) + 1;
// See if this node is balanced
if (maxh.d <= 2 * minh.d)
return true;
return false;
}
// A wrapper over isBalancedUtil()
function isBalanced(root) {
var maxh = new INT(), minh = new INT();
return isBalancedUtil(root, maxh, minh);
}
// Driver code
var 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);
document.write(isBalanced(root) ?
"Balanced" : "Not Balanced");
// This code contributed by umadevi9616
</script>
Producción
Balanced
Complejidad de tiempo: la complejidad de tiempo del código anterior es O (n) ya que el código realiza un recorrido de árbol simple.
Espacio auxiliar : O (n) para la pila de llamadas desde que se usa la recursividad
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA