This AVL Trees lesson is for a beginner. Read the short notes, run each example, then change one name or number and run it again.
An AVL tree is a binary search tree that stays balanced. The heights of the two children of any node differ by at most one.
The example computes that balance factor. A full insert rotates the tree when the factor leaves the range -1 to 1.
Example 1: Start here
A balance of 0, 1, or -1 is acceptable. Anything else needs a rotation.
def height(node): # define the function; it runs when you call it
if node is None: # run the indented lines only when this is true
return 0 # send this value back to the caller
return 1 + max(height(node[1]), height(node[2])) # send this value back to the caller
node = (8, (3, None, None), (10, None, None)) # a tuple; a fixed group of values
balance = height(node[1]) - height(node[2]) # the value at this position
print(balance)
Example 2: Walk the values
AVL Trees starts by visiting one value at a time. Read the printed lines from top to bottom.
values = [35, 3, 11, 7] # a list; the values stay in this order
for value in values: # repeat the indented lines once per value
print(value)
Example 3: Keep the largest
Many data-structure lessons reduce a list to one answer. This one remembers the largest number seen so far.
values = [35, 3, 11, 7] # a list; the values stay in this order
best = values[0] # the first value
for value in values: # repeat the indented lines once per value
if value > best: # run the indented lines only when this is true
best = value # another name for the same value
print(best)
Example 4: Search for a target
A search asks one yes-or-no question: is the target in the collection? AVL Trees builds on that question.
values = [3, 35, 11] # a list; the values stay in this order
target = 35 # a whole number
print(target in values) # in is True when the value is found
A balance of 0, 1, or -1 is acceptable. Anything else needs a rotation.
