Algorithm
A balanced binary tree is a binary tree in which the depth of the left and right subtrees of any node differ by at most one. In other words, the tree is balanced if, for every node in the tree, the heights of its left and right subtrees differ by no more than one.
A binary tree is a hierarchical data structure composed of nodes, where each node has at most two children, referred to as the left child and the right child.
The balance property is important because it ensures that the tree remains relatively shallow, which helps in maintaining efficient operations like insertion, deletion, and search. Unbalanced trees can lead to degenerate cases, where the tree essentially becomes a linked list, and the time complexity of operations increases significantly.
There are different algorithms and techniques for ensuring or checking the balance of a binary tree. One common approach is to use a self-balancing binary search tree (AVL tree or Red-Black tree), where the tree is automatically balanced during insertion and deletion operations.
Here's a brief overview of how balancing is typically achieved in AVL trees:
-
Balance Factor: Each node in an AVL tree has a balance factor, which is the difference between the height of the left subtree and the height of the right subtree. The balance factor can be -1, 0, or 1.
-
Rotations: When an insertion or deletion operation violates the balance property, rotations are performed to restore balance. There are four types of rotations: left rotation, right rotation, left-right rotation (or double right rotation), and right-left rotation (or double left rotation).
-
Recursive Update: After performing a rotation, the balance factors of the affected nodes are updated, and the balancing process may need to be recursively applied to the ancestors of the rotated nodes.
Maintaining the balance property ensures that the height of the tree remains logarithmic in relation to the number of nodes, leading to efficient search, insertion, and deletion operations.
Code Examples
#1 Balanced Binary Tree Implement in Python
Code -
Python Programming
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1 # Height of the node, initialized to 1
class AVLTree:
def __init__(self):
self.root = None
def height(self, node):
if node is None:
return 0
return node.height
def update_height(self, node):
if node:
node.height = 1 + max(self.height(node.left), self.height(node.right))
def balance_factor(self, node):
if node is None:
return 0
return self.height(node.left) - self.height(node.right)
def rotate_right(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(self.height(y.left), self.height(y.right))
x.height = 1 + max(self.height(x.left), self.height(x.right))
return x
def rotate_left(self, x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = 1 + max(self.height(x.left), self.height(x.right))
y.height = 1 + max(self.height(y.left), self.height(y.right))
return y
def insert(self, root, key):
if root is None:
return TreeNode(key)
if key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
self.update_height(root)
balance = self.balance_factor(root)
# Left Heavy
if balance > 1:
if key < root.left.key:
return self.rotate_right(root)
else:
root.left = self.rotate_left(root.left)
return self.rotate_right(root)
# Right Heavy
if balance < -1:
if key > root.right.key:
return self.rotate_left(root)
else:
root.right = self.rotate_right(root.right)
return self.rotate_left(root)
return root
def insert_key(self, key):
self.root = self.insert(self.root, key)
def inorder_traversal(self, root):
result = []
if root:
result += self.inorder_traversal(root.left)
result.append(root.key)
result += self.inorder_traversal(root.right)
return result
def print_tree(self):
result = self.inorder_traversal(self.root)
print("AVL Tree:", result)
# Example usage:
avl_tree = AVLTree()
keys = [9, 5, 10, 0, 6, 11, -1, 1, 2]
for key in keys:
avl_tree.insert_key(key)
avl_tree.print_tree()
#2 Balanced Binary Tree Implement in Java
Code -
Java Programming
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
public class BalancedBinaryTree {
public static void main(String[] args) {
BalancedBinaryTree tree = new BalancedBinaryTree();
int[] values = {3, 9, 20, 15, 7};
for (int value : values) {
tree.insert(value);
}
System.out.println("Is the tree balanced? " + tree.isBalanced());
}
private TreeNode root;
public BalancedBinaryTree() {
this.root = null;
}
public void insert(int value) {
root = insertNode(root, value);
}
private TreeNode insertNode(TreeNode root, int value) {
if (root == null) {
return new TreeNode(value);
}
if (value < root.val) {
root.left = insertNode(root.left, value);
} else if (value > root.val) {
root.right = insertNode(root.right, value);
}
return root;
}
public boolean isBalanced() {
return isBalanced(root);
}
private boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (Math.abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
private int getHeight(TreeNode node) {
if (node == null) {
return 0;
}
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
}
#3 Balanced Binary Tree Implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Structure for a tree node
struct Node {
int data;
struct Node* left;
struct Node* right;
int height; // Height of the subtree rooted at this node
};
// Function to get the height of a node
int height(struct Node* node) {
if (node == NULL)
return 0;
return node->height;
}
// Function to get the maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// Function to create a new node with a given data
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->height = 1; // New node is initially at height 1
return node;
}
// Function to perform a right rotation
struct Node* rightRotate(struct Node* y) {
struct Node* x = y->left;
struct Node* T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
// Return new root
return x;
}
// Function to perform a left rotation
struct Node* leftRotate(struct Node* x) {
struct Node* y = x->right;
struct Node* T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
// Return new root
return y;
}
// Function to get the balance factor of a node
int getBalance(struct Node* node) {
if (node == NULL)
return 0;
return height(node->left) - height(node->right);
}
// Function to insert a node into the AVL tree
struct Node* insert(struct Node* root, int data) {
// Perform standard BST insertion
if (root == NULL)
return newNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
else // Duplicate keys are not allowed
return root;
// Update height of the current node
root->height = 1 + max(height(root->left), height(root->right));
// Get the balance factor to check whether this node became unbalanced
int balance = getBalance(root);
// Left Left Case
if (balance > 1 && data < root->left->data)
return rightRotate(root);
// Right Right Case
if (balance < -1 && data > root->right->data)
return leftRotate(root);
// Left Right Case
if (balance > 1 && data > root->left->data) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right Left Case
if (balance < -1 && data < root->right->data) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
// No rotation needed, return the unchanged root
return root;
}
// Function to print the inorder traversal of the tree
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
// Driver program to test above functions
int main() {
struct Node* root = NULL;
// Inserting elements into the tree
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
// Print the inorder traversal of the tree
printf("Inorder traversal of the constructed AVL tree is: \n");
inorder(root);
return 0;
}
#4 Balanced Binary Tree Implement in C++
Code -
C++ Programming
#include <iostream>
#include <algorithm>
class Node {
public:
int key;
int height;
Node* left;
Node* right;
Node(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
};
class AVLTree {
public:
Node* root;
int height(Node* node) {
if (node == nullptr)
return 0;
return node->height;
}
int getBalance(Node* node) {
if (node == nullptr)
return 0;
return height(node->left) - height(node->right);
}
Node* rotateRight(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
y->height = 1 + std::max(height(y->left), height(y->right));
x->height = 1 + std::max(height(x->left), height(x->right));
return x;
}
Node* rotateLeft(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = 1 + std::max(height(x->left), height(x->right));
y->height = 1 + std::max(height(y->left), height(y->right));
return y;
}
Node* insert(Node* node, int key) {
if (node == nullptr)
return new Node(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node; // Duplicate keys are not allowed
node->height = 1 + std::max(height(node->left), height(node->right));
int balance = getBalance(node);
// Left Left Case
if (balance > 1 && key < node->left->key)
return rotateRight(node);
// Right Right Case
if (balance < -1 && key > node->right->key)
return rotateLeft(node);
// Left Right Case
if (balance > 1 && key > node->left->key) {
node->left = rotateLeft(node->left);
return rotateRight(node);
}
// Right Left Case
if (balance < -1 && key < node->right->key) {
node->right = rotateRight(node->right);
return rotateLeft(node);
}
return node;
}
void insert(int key) {
root = insert(root, key);
}
void inorderTraversal(Node* node) {
if (node != nullptr) {
inorderTraversal(node->left);
std::cout << node->key << " ";
inorderTraversal(node->right);
}
}
void inorderTraversal() {
inorderTraversal(root);
}
};
int main() {
AVLTree avlTree;
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30);
avlTree.insert(40);
avlTree.insert(50);
std::cout << "Inorder traversal of the AVL tree: ";
avlTree.inorderTraversal();
return 0;
}
Demonstration
Balanced Binary Tree-DevsEnv