Un árbol donde ninguna hoja está mucho más lejos de la raíz que cualquier otra hoja. Diferentes esquemas de equilibrio permiten diferentes definiciones de «mucho más lejos» y diferentes cantidades de trabajo para mantenerlos equilibrados.
Considere un esquema de equilibrio de altura en el que se deben verificar las siguientes condiciones para determinar si un árbol binario está equilibrado.
Un árbol vacío está equilibrado en altura. Un árbol binario T no vacío está balanceado si:
- El subárbol izquierdo de T está balanceado
- El subárbol derecho de T está balanceado
- La diferencia entre las alturas del subárbol izquierdo y el subárbol derecho no es más de 1.
El esquema de equilibrio de altura anterior se utiliza en árboles AVL. El siguiente diagrama muestra dos árboles, uno de ellos está equilibrado en altura y el otro no. El segundo árbol no está equilibrado en altura porque la altura del subárbol izquierdo es 2 más que la altura del subárbol derecho.
C++
/* CPP program to check if a tree is height-balanced or not */ #include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { public: int data; Node* left; Node* right; Node(int d) { int data = d; left = right = NULL; } }; // Function to calculate the height of a tree int height(Node* node) { // base case tree is empty if (node == NULL) return 0; // If tree is not empty then // height = 1 + max of left height // and right heights return 1 + max(height(node->left), height(node->right)); } // Returns true if binary tree // with root as root is height-balanced bool isBalanced(Node* root) { int lh; // for height of left subtree int rh; // for height of right subtree // If tree is empty then return true if (root == NULL) return 1; // Get the height of left and right sub trees lh = height(root->left); rh = height(root->right); if (abs(lh - rh) <= 1 && isBalanced(root->left) && isBalanced(root->right)) return 1; // If we reach here then tree is not height-balanced return 0; } // Driver code int main() { Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->left->left->left = new Node(8); if (isBalanced(root)) cout << "Tree is balanced"; else cout << "Tree is not balanced"; return 0; } // This code is contributed by rathbhupendra
C
/* C program to check if a tree is height-balanced or not */ #include <stdio.h> #include <stdlib.h> #define bool int /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* Returns the height of a binary tree */ int height(struct node* node); /* Returns true if binary tree with root as root is height-balanced */ bool isBalanced(struct node* root) { int lh; /* for height of left subtree */ int rh; /* for height of right subtree */ /* If tree is empty then return true */ if (root == NULL) return 1; /* Get the height of left and right sub trees */ lh = height(root->left); rh = height(root->right); if (abs(lh - rh) <= 1 && isBalanced(root->left) && isBalanced(root->right)) return 1; /* If we reach here then tree is not height-balanced */ return 0; } /* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */ /* returns maximum of two integers */ int max(int a, int b) { return (a >= b) ? a : b; } /* The function Compute the "height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int height(struct node* node) { /* base case tree is empty */ if (node == NULL) return 0; /* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + max(height(node->left), height(node->right)); } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } int main() { struct node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->left->left->left = newNode(8); if (isBalanced(root)) printf("Tree is balanced"); else printf("Tree is not balanced"); getchar(); return 0; }
Java
/* Java program to determine if binary tree is height balanced or not */ /* A binary tree node has data, pointer to left child, and a pointer to right child */ class Node { int data; Node left, right; Node(int d) { data = d; left = right = null; } } class BinaryTree { Node root; /* Returns true if binary tree with root as root is height-balanced */ boolean isBalanced(Node node) { int lh; /* for height of left subtree */ int rh; /* for height of right subtree */ /* If tree is empty then return true */ if (node == null) return true; /* Get the height of left and right sub trees */ lh = height(node.left); rh = height(node.right); if (Math.abs(lh - rh) <= 1 && isBalanced(node.left) && isBalanced(node.right)) return true; /* If we reach here then tree is not height-balanced */ return false; } /* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */ /* The function Compute the "height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int height(Node node) { /* base case tree is empty */ if (node == null) return 0; /* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + Math.max(height(node.left), height(node.right)); } public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.left.left.left = new Node(8); if (tree.isBalanced(tree.root)) System.out.println("Tree is balanced"); else System.out.println("Tree is not balanced"); } } // This code has been contributed by Mayank Jaiswal(mayank_24)
Python3
""" Python3 program to check if a tree is height-balanced """ # A binary tree Node class Node: # Constructor to create a new Node def __init__(self, data): self.data = data self.left = None self.right = None # function to find height of binary tree def height(root): # base condition when binary tree is empty if root is None: return 0 return max(height(root.left), height(root.right)) + 1 # function to check if tree is height-balanced or not def isBalanced(root): # Base condition if root is None: return True # for left and right subtree height lh = height(root.left) rh = height(root.right) # allowed values for (lh - rh) are 1, -1, 0 if (abs(lh - rh) <= 1) and isBalanced( root.left) is True and isBalanced( root.right) is True: return True # if we reach here means tree is not # height-balanced tree return False # Driver function to test the above function root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.left.left.left = Node(8) if isBalanced(root): print("Tree is balanced") else: print("Tree is not balanced") # This code is contributed by Shweta Singh
C#
using System; /* C# program to determine if binary tree is height balanced or not */ /* A binary tree node has data, pointer to left child, and a pointer to right child */ public class Node { public int data; public Node left, right; public Node(int d) { data = d; left = right = null; } } public class BinaryTree { public Node root; /* Returns true if binary tree with root as root is height-balanced */ public virtual bool isBalanced(Node node) { int lh; // for height of left subtree int rh; // for height of right subtree /* If tree is empty then return true */ if (node == null) { return true; } /* Get the height of left and right sub trees */ lh = height(node.left); rh = height(node.right); if (Math.Abs(lh - rh) <= 1 && isBalanced(node.left) && isBalanced(node.right)) { return true; } /* If we reach here then tree is not height-balanced */ return false; } /* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */ /* The function Compute the "height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ public virtual int height(Node node) { /* base case tree is empty */ if (node == null) { return 0; } /* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + Math.Max(height(node.left), height(node.right)); } public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.left.left.left = new Node(8); if (tree.isBalanced(tree.root)) { Console.WriteLine("Tree is balanced"); } else { Console.WriteLine("Tree is not balanced"); } } } // This code is contributed by Shrikant13
Javascript
<script> // JavaScript program to check if a tree is height-balanced // A binary tree Node class Node{ // Constructor to create a new Node constructor(data){ this.data = data this.left = null this.right = null } } // function to find height of binary tree function height(root){ // base condition when binary tree is empty if(root == null) return 0 return Math.max(height(root.left), height(root.right)) + 1 } // function to check if tree is height-balanced or not function isBalanced(root){ // Base condition if(root == null) return true // for left and right subtree height let lh = height(root.left) let rh = height(root.right) // allowed values for (lh - rh) are 1, -1, 0 if (Math.abs(lh - rh) <= 1 && isBalanced( root.left)== true && isBalanced( root.right) == true) return true // if we reach here means tree is not // height-balanced tree return false } // Driver function to test the above function let root = new Node(1) root.left = new Node(2) root.right = new Node(3) root.left.left = new Node(4) root.left.right = new Node(5) root.left.left.left = new Node(8) if(isBalanced(root)) document.write("Tree is balanced","</br>") else document.write("Tree is not balanced","</br>") // This code is contributed by ShinjanPatra </script>
C++
/* C++ program to check if a tree is height-balanced or not */ #include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { public: int data; Node* left; Node* right; Node(int d) { data = d; left = right = NULL; } }; /* The function returns true if root is balanced else false The second parameter is to store the height of tree. Initially, we need to pass a pointer to a location with value as 0. We can also write a wrapper over this function */ bool isBalanced(Node* root, int* height) { /* lh --> Height of left subtree rh --> Height of right subtree */ int lh = 0, rh = 0; /* l will be true if left subtree is balanced and r will be true if right subtree is balanced */ int l = 0, r = 0; if (root == NULL) { *height = 0; return 1; } /* Get the heights of left and right subtrees in lh and rh And store the returned values in l and r */ l = isBalanced(root->left, &lh); r = isBalanced(root->right, &rh); /* Height of current node is max of heights of left and right subtrees plus 1*/ *height = (lh > rh ? lh : rh) + 1; /* If difference between heights of left and right subtrees is more than 2 then this node is not balanced so return 0 */ if (abs(lh - rh) >= 2) return 0; /* If this node is balanced and left and right subtrees are balanced then return true */ else return l && r; } // Driver code int main() { int height = 0; /* Constructed binary tree is 1 / \ 2 3 / \ / 4 5 6 / 7 */ Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->left->left->left = new Node(7); if (isBalanced(root, &height)) cout << "Tree is balanced"; else cout << "Tree is not balanced"; return 0; } // This is code is contributed by rathbhupendra
C
/* C program to check if a tree is height-balanced or not */ #include <stdio.h> #include <stdlib.h> #define bool int /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* The function returns true if root is balanced else false The second parameter is to store the height of tree. Initially, we need to pass a pointer to a location with value as 0. We can also write a wrapper over this function */ bool isBalanced(struct node* root, int* height) { /* lh --> Height of left subtree rh --> Height of right subtree */ int lh = 0, rh = 0; /* l will be true if left subtree is balanced and r will be true if right subtree is balanced */ int l = 0, r = 0; if (root == NULL) { *height = 0; return 1; } /* Get the heights of left and right subtrees in lh and rh And store the returned values in l and r */ l = isBalanced(root->left, &lh); r = isBalanced(root->right, &rh); /* Height of current node is max of heights of left and right subtrees plus 1*/ *height = (lh > rh ? lh : rh) + 1; /* If difference between heights of left and right subtrees is more than 2 then this node is not balanced so return 0 */ if (abs(lh - rh) >= 2) return 0; /* If this node is balanced and left and right subtrees are balanced then return true */ else return l && r; } /* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */ /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } // Driver code int main() { int height = 0; /* Constructed binary tree is 1 / \ 2 3 / \ / 4 5 6 / 7 */ struct node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->left->left->left = newNode(7); if (isBalanced(root, &height)) printf("Tree is balanced"); else printf("Tree is not balanced"); getchar(); return 0; }
Java
/* Java program to determine if binary tree is height balanced or not */ /* A binary tree node has data, pointer to left child, and a pointer to right child */ class Node { int data; Node left, right; Node(int d) { data = d; left = right = null; } } // A wrapper class used to modify height across // recursive calls. class Height { int height = 0; } class BinaryTree { Node root; /* Returns true if binary tree with root as root is height-balanced */ boolean isBalanced(Node root, Height height) { /* If tree is empty then return true */ if (root == null) { height.height = 0; return true; } /* Get heights of left and right sub trees */ Height lheight = new Height(), rheight = new Height(); boolean l = isBalanced(root.left, lheight); boolean r = isBalanced(root.right, rheight); int lh = lheight.height, rh = rheight.height; /* Height of current node is max of heights of left and right subtrees plus 1*/ height.height = (lh > rh ? lh : rh) + 1; /* If difference between heights of left and right subtrees is more than 2 then this node is not balanced so return 0 */ if (Math.abs(lh - rh) >= 2) return false; /* If this node is balanced and left and right subtrees are balanced then return true */ else return l && r; } public static void main(String args[]) { Height height = new Height(); /* Constructed binary tree is 1 / \ 2 3 / \ / 4 5 6 / 7 */ BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.right = new Node(6); tree.root.left.left.left = new Node(7); if (tree.isBalanced(tree.root, height)) System.out.println("Tree is balanced"); else System.out.println("Tree is not balanced"); } } // This code has been contributed by Mayank Jaiswal(mayank_24)
Python3
""" Python3 program to check if Binary tree is height-balanced """ # A binary tree node class Node: # constructor to create node of # binary tree def __init__(self, data): self.data = data self.left = self.right = None # utility class to pass height object class Height: def __init__(self): self.height = 0 # function to find height of binary tree def height(root): # base condition when binary tree is empty if root is None: return 0 return max(height(root.left), height(root.right)) + 1 # helper function to check if binary # tree is height balanced def isBalanced(root): # Base condition when tree is # empty return true if root is None: return True # lh and rh to store height of # left and right subtree lh = Height() rh = Height() # Calculating height of left and right tree lh.height = height(root.left) rh.height = height(root.right) # l and r are used to check if left # and right subtree are balanced l = isBalanced(root.left) r = isBalanced(root.right) # height of tree is maximum of # left subtree height and # right subtree height plus 1 if abs(lh.height - rh.height) <= 1: return l and r # if we reach here then the tree # is not balanced return False # Driver function to test the above function """ Constructed binary tree is 1 / \ 2 3 / \ / 4 5 6 / 7 """ # to store the height of tree during traversal root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.left.left.left = Node(7) if isBalanced(root): print('Tree is balanced') else: print('Tree is not balanced') # This code is contributed by Shubhank Gupta
C#
using System; /* C# program to determine if binary tree is height balanced or not */ /* A binary tree node has data, pointer to left child, and a pointer to right child */ public class Node { public int data; public Node left, right; public Node(int d) { data = d; left = right = null; } } // A wrapper class used to modify height across // recursive calls. public class Height { public int height = 0; } public class BinaryTree { public Node root; /* Returns true if binary tree with root as root is height-balanced */ public virtual bool isBalanced(Node root, Height height) { /* If tree is empty then return true */ if (root == null) { height.height = 0; return true; } /* Get heights of left and right sub trees */ Height lheight = new Height(), rheight = new Height(); bool l = isBalanced(root.left, lheight); bool r = isBalanced(root.right, rheight); int lh = lheight.height, rh = rheight.height; /* Height of current node is max of heights of left and right subtrees plus 1*/ height.height = (lh > rh ? lh : rh) + 1; /* If difference between heights of left and right subtrees is more than 2 then this node is not balanced so return 0 */ if (Math.Abs(lh - rh) >= 2) { return false; } /* If this node is balanced and left and right subtrees are balanced then return true */ else { return l && r; } } /* The function Compute the "height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ public virtual int height(Node node) { /* base case tree is empty */ if (node == null) { return 0; } /* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + Math.Max(height(node.left), height(node.right)); } public static void Main(string[] args) { Height height = new Height(); /* Constructed binary tree is 1 / \ 2 3 / \ / 4 5 6 / 7 */ BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.right = new Node(6); tree.root.left.left.left = new Node(7); if (tree.isBalanced(tree.root, height)) { Console.WriteLine("Tree is balanced"); } else { Console.WriteLine("Tree is not balanced"); } } } // This code is contributed by Shrikant13
Javascript
<script> // JavaScript program to check if Binary tree is height-balanced // A binary tree node class Node{ // constructor to create node of // binary tree constructor(data){ this.data = data this.left = this.right = null } } // utility class to pass height object class Height { constructor() { this.height = 0 } } // function to find height of binary tree function height(root){ // base condition when binary tree is empty if(root == null) return 0 return Math.max(height(root.left), height(root.right)) + 1 } // helper function to check if binary // tree is height balanced function isBalanced(root) { // Base condition when tree is // empty return true if(root == null) return true // lh and rh to store height of // left and right subtree let lh = new Height() let rh = new Height() // Calculating height of left and right tree lh.height = height(root.left) rh.height = height(root.right) // l and r are used to check if left // and right subtree are balanced let l = isBalanced(root.left) let r = isBalanced(root.right) // height of tree is maximum of // left subtree height and // right subtree height plus 1 if(Math.abs(lh.height - rh.height) <= 1) return l && r // if we reach here then the tree // is not balanced return false } // Driver function to test the above function // Constructed binary tree is // 1 // / \ // 2 3 // / \ / // 4 5 6 / 7 // // to store the height of tree during traversal let root = new Node(1) root.left = new Node(2) root.right = new Node(3) root.left.left = new Node(4) root.left.right = new Node(5) root.right.left = new Node(6) root.left.left.left = new Node(7) if(isBalanced(root)) document.write('Tree is balanced',"</br>") else document.write('Tree is not balanced',"</br>") // This code is contributed by shinjanpatra </script>
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