|
A balanced binary tree is where the depth of all the leaves differs by at most 1. Balanced trees have a predictable depth (how many nodes are traversed from the root to a leaf, root counting as node 0 and subsequent as 1, 2, ..., depth). This depth is equal to the integer part of log2(n) where n is the number of nodes on the balanced tree. Example 1: balanced tree with 1 node, log2(1)=0 (depth = 0). Example 2: balanced tree with 3 nodes, log2(3)=1.59 (depth=1). Example 3: balanced tree with 5 nodes, log2(5)=2.32 (depth of tree is 2 nodes).
|