26.1.4. Balanced Trees

Try these first

1. 1.

   What is the balance factor of a node in an AVL Tree?

   Hint

   Recall the AVL balance property.

2. 2.

   What color options are there for nodes in Red-Black Trees?

   Hint

   Think of it like organizing a color-coded system.

3. 3.

   What is a property of an AVL Tree?

   • It is always full
   • Balance factor is between -1 and 1
   • All nodes are red

   Hint

   Think of what keeps the AVL tree balanced.

4. 4.

   True or False: In a Red-Black Tree, two red nodes can be adjacent.

   • True
   • False

   Hint

   Recall the red-black properties.

5. 5.

   Given a sequence of insertions into an AVL Tree, demonstrate the tree structure after each insertion and highlight the rotations applied.

   Hint

   Start with an empty tree, proceed with one insertion at a time.

6. 6.

   Explain how you would determine whether a tree is a Red-Black Tree based on its properties, and provide an example of a violation.

   Hint

   Focus on color arrangements and parent-child relationships.