Trees

• What time complexity does binary search have for an n-element sorted array?

  $O(\log n)$
• Why can't binary search implement a dictionary storing an array of key-value pairs sorted by key?

  • Insertion and removal in the middle of a sorted array take $\Omega(n)$ time
  • Finding the halfway point in a linked list also takes $\Omega(n)$ time
• What data structure can be used instead of a sorted array or linked list to implement a dictionary with efficient insertion and deletion?

  Binary search tree
• What characterizes a binary search tree in terms of node structure and child relationships?

  • Each node has 0–2 children
  • For a node with value $x:$
  • All left descendants have values < $x$
  • All right descendants have values > $x$
  • Values are assumed to be distinct
• What are the time complexities for finding, inserting, and deleting nodes in a binary search tree?

  • Finding: $O(\log n)$ on average
  • Insertion and deletion: $O(d)$ time where $d$ is the depth of the tree
• What is the main idea behind 2-3-4 trees?

  • Force the tree to be perfectly balanced with all levels full
  • Allow nodes to contain more than one value to maintain balance
• How many children can a $k-node$ have in a 2-3-4 tree, and how many values can it contain?


  • Up to $k$ children
  • Contains $k-1$ values
  • Allowed values for $k:$ {2, 3, 4}
• What is the time complexity for finding a value in a 2-3-4 tree?

  $O(\log n)$
• What problem can arise in binary search trees that is solved by using 2-3-4 trees?

  • An unbalanced binary search tree can lead to a depth of $\Omega(n)$
  • 2-3-4 trees force perfect balance, keeping the depth at $\Theta(\log n)$
• How does inserting a value in a 2-3-4 tree differ depending on whether the leaf node is a 2-node or a 3-node?

  • For 2-nodes or 3-nodes: Simply add the new value
  • For 4-nodes: Split the node, sending one value to the parent and keeping the others as 2-nodes
• What happens when inserting a value into a 4-node in a 2-3-4 tree?

  It is split into two 2-nodes, with the middle value sent up to the parent node.
• What is the first step to insert a value k in a 2-3-4 tree?

  • Find the leaf that would contain k if it was there
• What can be done if the leaf is a 2-node or a 3-node when inserting a new value k?

  Add the new value to the leaf.
• What happens if the leaf is a 4-node when inserting a new value k?

  First split it, sending one value up to its parent and keeping the others as 2-nodes.
• What is the first step to insert a value k in a 2-3-4 tree?

  Find the leaf that would contain k if it was there.
• What is the time complexity of splitting 4-nodes in a 2-3-4 tree?

  O(d)
• What happens if a 4-node is encountered during insertion in a 2-3-4 tree, and its parent is also a 4-node?

  • Split all 4-nodes encountered on the way down
• What happens if a 4-node is encountered during insertion in a 2-3-4 tree, and its parent is also a 4-node?

  • Split all 4-nodes encountered on the way down
• What happens if a 4-node is encountered during insertion in a 2-3-4 tree, and its parent is also a 4-node?

  • Split all 4-nodes encountered on the way down
• What happens if a 4-node is encountered during insertion in a 2-3-4 tree, and its parent is also a 4-node?

  • Split all 4-nodes encountered on the way down
• What happens if a 4-node is encountered during insertion in a 2-3-4 tree, and its parent is also a 4-node?

  • Split all 4-nodes encountered on the way down
• What happens if a 4-node is encountered during insertion in a 2-3-4 tree, and its parent is also a 4-node?

  • Split all 4-nodes encountered on the way down
• What happens if a 4-node is encountered during insertion in a 2-3-4 tree, and its parent is also a 4-node?

  • Split all 4-nodes encountered on the way down
• What happens to the height d if the root of a 2-3-4 tree is split during insertion?

  d increases by 1.
• What can be done if the leaf is a 2-node or a 3-node when inserting a new value k?

  Add the new value to the leaf.
• What happens if the leaf is a 4-node when inserting a new value k?

  First split it, sending one value up to its parent and keeping the others as 2-nodes.
• What happens if a 4-node is encountered during insertion in a 2-3-4 tree, and its parent is also a 4-node?

  • Split all 4-nodes encountered on the way down
• What is the time complexity of splitting 4-nodes in a 2-3-4 tree?

  O(d)
• What does a 2-3-4 tree with distinct values look like so far?

  • A balanced tree with nodes that can hold 2, 3, or 4 keys
• How do you find a value v in a 2-3-4 tree?

  1. Let x be the root.
  2. If v ∈ x, return a pointer to x.
  3. Otherwise, if x is a leaf, return Not Found.
  4. Let x be a k-node.
  5. Let x1 ≤ · · · ≤ xk−1 be the values in x.
  6. Let x0 = −∞ and xk = ∞.
  7. Find xi−1 < v < xi for some i.
  8. Let c be the i’th child of x.
  9. Repeat the process with x = c.
• How do you insert a value v in a 2-3-4 tree?

  1. Attempt to find v as in finding a value.
  2. Split any 4-nodes encountered, including the root.
  3. After reaching a leaf L, split it if it is a 4-node.
  4. Add v to L.
• When is deleting a value v in a 2-3-4 tree handled?

  Next time!
• What is the first step in finding a value $v$ in a 2-3-4 tree?


  Let x be the root.
• If $v$ is found in the root $x,$ what is the function's return value?


  A pointer to $x.$
• If $v$ is not found in the root $x$ and $x$ is a leaf, what is the function's return value?


  Not Found.
• What defines a $k-node$ in a 2-3-4 tree?


  • A node containing $k$ distinct values
• In finding a value in a $k-node,$ how are the values $x_0$ and $x_k$ defined?


  • $x_0 =$$−∞$
  • $x_k =$$∞$
• What is the recursive step in finding a value in a 2-3-4 tree?

  Repeat the process from the start, taking $x =$$c,$ where $c$ is the $i-th$ child of $x.$
• What is the first step in inserting a value $v$ into a 2-3-4 tree?


  Attempt to find $v$ using the finding algorithm, splitting any 4-nodes encountered.
• After reaching a leaf and splitting it if it is a 4-node, what is the next step in inserting a value into the tree?

  Add $v$ to the leaf.