Notes - ADS HT24, Binary search trees

Created: January 22, 2024

Flashcards

Suppose:

  • $T$ is a binary tree

What is the binary search tree property?
  • For all nodes $x$ in $T$:
    • $val[x]$ is greater than all values in the left subtree of $x$
    • $val[x]$ is smaller than all values in the right subtree of $x$

What are the 7 operations on a binary search tree?
  • Insert
  • Delete
  • Search
  • Min
  • Max
  • Predecessor
  • Successor

Give the pseudocode for Search($T$, $v$), which searches a binary tree and returns $x$ such that $val[x] = v$ and $NIL$ otherwise.

 
SEARCH(T, v):
	x = root(T)
	while x != NIL and val[x] != v:
		if v < val[x]:
			x = left[x]
		else:
			x = right[x]
	
	return x

Give the pseudocode for Insert($T$, $z$), which inserts a node $z$ with value $val[z]$ into a binary search tree $T$.

 
INSERT(T, z):
	x = root(T);
	y = NIL

	while x != NIL:
		y = x
		if val[z] < val[x]:
			x = left[x]
		else:
			x = right[x]

	p[z] = y # parent
	if val[z] < val[y]:
		left[y] = z
	else:
		right[y] = z

Give a very high-level description of how to implement Successor($x$) for a binary tree, which returns the smallest value $y$ such that $val[x] < val[y]$.
  • If $x$ has a right child (i.e. right[x] != NIL), return left-most descendant of right[x]
  • Otherwise, follow the path from $x$ to the root and return the first node where we “turn right” to get there

Give a very high-level description of how to implement Delete($x$), which deletes node $x$ from a binary tree $T$, breaking down into three cases.
  • Case 1: If $x$ has no child, immediate
  • Case 2: If $x$ has one child, promote the child in place of $x$
  • Case 3: If $x$ has two children, find $y$ = Successor($x$). Swap $x$ and $y$ and delete $x$.

What does it mean for a binary tree to be balanced?

Its height is $O(\log n)$.

Draw a figure representing the change made by left-rotations and right-rotations on binary search trees with nodes $x$ and $y$, and subtrees $\alpha, \beta, \gamma$.

What’s the difference between a full and complete binary tree?
  • Full binary tree: either zero or two children
  • Complete binary tree: all levels are fully filled except possibly for the last level

Proofs



Related posts