(W11) Data Structures

Question 1

What is the special property of an AVL tree

Answer 1

It’s a self balancing binary tree

Question 2

What is the definition of balanced in an AVL tree & how do you calculate it?

Answer 2

Balance = height(left) - height(right)

importantly, a tree is balanced if, for each node, at most, the height of the right and left subtree differ by at most 1

Question 3

AVL Tree circumstance:
Balance Factor = 2, left child has a balance of 0 or 1

Answer 3

Left-Left case (only 1 operation)

Question 4

AVL tree circumstance:
Balance Factor = 2, left child has a balance of -1

Answer 4

Left-right case

Perform left on the child, right on the parent

Question 5

AVL tree circumstance:
Balance Factor = -2, right child has a balance of 0 or -1

Answer 5

Right-right case

Question 6

AVL tree circumstance:
Balance Factor = -2, right child has a balance of 1

Answer 6

Right-left case

Perform right on the child, left on the parent

Question 7

Time Complexity of AVL operations?

Answer 7

O(log n) for all operations. this is because the BST tree is balanced. rotations are O(1)

except traversal O(n)

Question 8

What are the types of nodes in a 2-3 Tree?

Answer 8

2-nodes: single key, two children
3-nodes: 2 keys, three children

Question 9

How to insert into a 2-3 Tree

Answer 9

• Do a search, find the leaf node
  ○ If the leaf is a 2-node, turn it into a three node, and add the key
  ○ If it’s a 3-node, temp make it a 4 node
• If there is a 4 node, then promote the middle key. Do this recursively (including if you need to add a new root node)

Question 10

Do you ever increase the height of a 2-3 tree from the base?

Answer 10

No, if the height of the tree ever increases, it will be the result of adding a node to the parent

Question 11

What are the different complexities of operations in a 2-3 tree?

Answer 11

O(log n) for insert/search/delete

Question 12

What is the practical purpose of a Red-Black-Tree?

Answer 12

It’s a faster implementation of 2-3 tree. Lower constants

Question 13

What are the 4 properties of a red-black tree?

Answer 13

The colour of a non-root node is determined by the colour of its
single incoming edge. The root is by definition black.

All red links lean left, i.e., all red links go to a left child.

No node is adjacent to two red edges.

The tree has perfect black balance: the number of black edges
between any node and each of its descendant leaves are the same.

Question 14

AVL trees vs RBTs regarding complexity?

Answer 14

In terms of worst-case complexity - they are both equivalent

AVL trees are more strictly balanced - so this makes them better for lookups (in terms of concrete efficiency)

RBT’s are better for insertion (less rotations that need to be done)