balanced BST

Work in Progress

Summary

Binary search tree(BST)

implements table

Operation	Method	Performance
`search(v)`	tree traversal	-
`insert(v)`	tree traversal, rebalance	-
`remove(v)`	tree traversal, rebalance	-

implements priority queue

Operation	Method	Performance
`insert(v)`	insert into the tree	-
`extractMax()`/`extractMin()`	remove max/min, rebalance	-

Concept

Adelson-Velskii Landis tree(AVL tree)

balanced BST
AVL tree invariant
- balance factor
- the heights of the subtrees can only differ by at most 1

Minimum size of an AVL tree

subtree of h-1 + subtree of h-2 + root node

similar recurrence relation to exponential order of growth

Height of an AVL tree

Rotations

applied when insert(v) or remove(v) causes the tree to be unbalanced
needs to preserve the BST property
left-left case: insert(1) -> rotateRight(5)

java

TreeNode rotateRight(TreeNode root) { // b > 1 implies that it has a left subtree
	// store the left subtree
	TreeNode L = root.left;
	// modify the left subtree of the root
	if (L.right != null)
		root.left = L.right;
	else
		root.left = null;
	// move the modified root into the right subtree
	L.right = root;
	// left subtree will now take over as root
	return L;
}

right-right case: remove(1) -> rotateLeft(3)

rotateLeft(v) is the mirror of rotateRight(v)

left-right case: insert(3) -> rotateLeft(2) -> rotateRight(5)

right-left case: remove(2) -> rotateRight(6) -> rotateLeft(3)

Application

Kattis: Compound Words

java

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);

List<String> words = new ArrayList<>();
TreeSet<String> comp = new TreeSet<>();
StringTokenizer st;
String line;

while ((line = br.readLine()) != null && !line.isEmpty()) {
	st = new StringTokenizer(line);

	while (st.hasMoreTokens()) {
		String curr = st.nextToken();
		for (int i = 0; i < words.size(); i++) {
			String other = words.get(i);
			comp.add(other + curr);
			comp.add(curr + other);
		}
		words.add(curr);
	}
}

while (!comp.isEmpty())
	pw.println(comp.pollFirst());

pw.close();

Kattis: Bacon, Eggs and Spam

fairly convoluted
use tree map to map menu items to a priority queue of people who ordered it, preserve sorted order on both

java

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);

TreeMap<String, PriorityQueue<String>> orders = new TreeMap<>();
StringTokenizer st;

int n = Integer.parseInt(br.readLine());

while (n != 0) {
	for (int i = 0; i < n; i++) {
		st = new StringTokenizer(br.readLine());
		String name = st.nextToken();

		while (st.hasMoreTokens()) {
			String key = st.nextToken();
			PriorityQueue<String> pq = orders.getOrDefault(key, new PriorityQueue<>());
			pq.offer(name);
			orders.put(key, pq);
		}
	}

	Entry<String, PriorityQueue<String>> elem = orders.firstEntry();
	for (int j = 0; j < orders.size(); j++) {
		pw.print(elem.getKey());
		pw.print(" ");
		PriorityQueue<String> pq = elem.getValue();
		while (!pq.isEmpty()) {
			pw.print(pq.poll());
			pw.print(" ");
		}
		pw.println();
		elem = orders.higherEntry(elem.getKey());
	}
	pw.println();

	orders.clear();
	n = Integer.parseInt(br.readLine());
}

pw.close();

Extra

Min size function in python

python

def S(h):
	if h == 0:
		return 1
	elif h == 1:
		return 2
	
	return S(h-1) + S(h-2) + 1