CISC 220: Trees Exam

AVL Tree vs. Standard Binary Tree

Standard BST has no balance restrictions

AVL tree is self-balancing, -2<height difference<2

Preorder

Current node first, then left subtree, then right subtree (Root $\rightarrow$ Left $\rightarrow$ Right)

Inorder

Left subtree first, then current node, then right subtree (Left $\rightarrow$ Root $\rightarrow$ Right). Makes sorted values in a BST

Postorder

Left subtree first, then right subtree, then current node (Left $\rightarrow$ Right $\rightarrow$ Root)

Right Rotation

Use when you insert to the left subtree of a left child and it’s unbalanced, left child becomes root, unbalanced node goes down and becomes right child

Left Rotation

Use when you insert to the right subtree of a right child and it’s unbalanced, right child becomes root, unbalanced node goes down and becomes left child

Left-Right Rotation

Use when you insert to the right subtree of a left child and it’s unbalanced, Left Rotation on left child, then Right Rotation on unbalanced node

Right-Left Rotation

Use when you insert to the left subtree of a right child and it’s unbalanced, Right Rotation on right child, then Left Rotation on unbalanced node

Merge Sort

Divide-and-conquer, repeatedly divides array/array parts into halves until each part only has one element, then repeatedly combines the one number lists in sorted order.

Worst-case runtime: O(n log(n))

Selection Sort

Repeatedly searches the unsorted portion of a list for the smallest element and swaps it to the end of the sorted portion.

Worst-case runtime:O(n^2)