What is a Balanced Binary Tree?

BBT is a tree where the key of a node is less than its right child’s key but greater than its left child’s key.

leftchild(v).key < v.key < rightchild(v).key

What is a Rank-Balanced Tree?

Rank-Balanced Trees are binary trees with logarithmic height. By performing some kind of restructuring actions (rotation), we can change a tree to a rank-balanced tree.

What is a Balance Factor?

BF(v) = height(left-subtree) - height(right-subtree)

AVL Tree

Red Black Tree