A red-black tree is a type of self-balancing binary tree.
Note: Read more about a red-black tree here.
In this Answer, we'll learn how to check if a tree is balanced. A red-black tree is balanced if the following conditions are met:
For every node in the tree, the number of black nodes on both subtrees is the same.
There are no two consecutive red nodes.
The root node is black.
class Node:def __init__(self, value, color=RED):self.value = valueself.left = Noneself.right = Noneself.color = colorclass RedBlackTree:def __init__(self):self.root = Nonedef _numBlack(self, root):if not root:return 0black_left = self._numBlack(root.left)black_right = self._numBlack(root.right)if black_left != black_right or black_left == -1:return -1if root.color == BLACK:return 1 + black_leftelse:return 0 + black_leftdef isBalanced(self):if not self.root or self.root.color != BLACK:return Falseblack_left = self._numBlack(self.root.left)black_right = self._numBlack(self.root.right)if black_left != black_right or black_left == -1:return Falsereturn Truetree = RedBlackTree()tree.root = Node(3, BLACK)tree.root.right = Node(4, RED)tree.root.left = Node(2, RED)tree.root.left.right = Node(2.5, BLACK)print("The tree is", "balanced" if tree.isBalanced() else "not balanced")
Lines 1–6: We define a Node
class that stores a node.
Lines 12–26: We define a function isBalanced()
that calls _numBlack()
. The function _numBlack()
returns the number of black nodes on any single path from that node. The function isBalanced()
then checks if there are an equal number of black nodes on both left and right subtree and returns a boolean value.
Lines 34–40: We manually define a red-black tree and call the function isBalanced()
to see if the tree is balanced.
Note: You may change the structure of the tree to see how
isBalanced()
behaves.
Free Resources