Summary - AVL tree

Reinforce AVL logic with a mini task.

Summary - AVL tree

AVL: |bf| ≤ 1 at every node. When balance breaks a rotation (right, left, double) fixes it. Insert/delete/search are always O(log n).

Four cases: left-left (right), right-right (left), left-right (double), right-left (double). Rotation is O(1), BST property preserved.

AVL is ideal for frequent search and rare insert; for frequent insert red-black trees are preferred.

Exercise Summary: AVL height

Write height(node). In AVL height ≤ 1.44 log n. Print 1 with root = Node(1); root.left = Node(2); print(height(root)).

Show example solution

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def height(node):
    # Height
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))
root = Node(1)
root.left = Node(2)
print(height(root))

Test yourself

Summary - AVL tree: match the terms

Balance

|bf| ≤ 1
Left-left

Right rotate
Right-right

Left rotate
Cost

O(log n)
Balance factor bound
```
|bf| ____ 1
```
Show answer
```
|bf| <= 1
```
When is AVL preferred?
- Frequent search, rare insert
- No insert at all
- Always
- Frequent insert, rare search
Show answer

Frequent search, rare insert — Frequent search, rare insert

Next lesson: Min and max heap

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies