Ch. 6 Flashcards
(27 cards)
Transform and Conquer
Solve a problem by transformation via
1. Instance Simplification
2. Representation Change
3. Problem Reduction
Instance Simplification
Transform to a simpler/more convenient instance of the same problem.
- Presorting
Representation Change
Transform to a different representation of the same instance.
Problem Reduction
Transform to a different problem for which an algorithm is already available.
Presorting
Instance simplification method to solving complex tasks like searching, computing median, element uniqueness, etc.
Presorting for searching
- Sort the array by an efficient sorting algo
- Apply binary search
O(nlogn) more efficient in the long-term
Presorting for element uniqueness
- Sort the array by an efficient sorting algo
- Scan array for pairs of adjacent elements
O(nlogn) better than O(n^2)
Binary Search Tree
A binary tree in which the key of an internal node is greater than the keys in its left subtree and less than or equal to the keys in its right subtree.
Dictionary Operations on BST
Searching
Insertion - search and insert where search terminated
Deletion - delete leaf, delete node w/ one child, delete node w/ 2 children.
Worst cases: O(n)
Average cases: O(logn)
Pre-order traversal
Root, left, right
In-order traversal
Left, root, right
Produces a sorted list
Post-order traversal
Left, right, root
AVL tree
A BST in which, for every node, the balance factor is at most 1.
Balance factor
The difference between the heights of a node’s left and right subtrees.
Single R rotation
Performed after a new key is inserted into the left subtree of the left child of a tree whose root had the balance of +1 before its insertion.
Single L rotation
Performed after a new key is inserted into the right subtree of the right child of a tree whose root had the balance of -1 before its insertion.
Double LR rotation
Performed after a new key is inserted into the right subtree of the left child of a tree whose root had the balance of +1 before its insertion. Perform the L rotation of the left subtree followed by the
R rotation of the root.
How to perform tree rotations
Rotate the edge connecting the root and its (left or right) child.
Double RL rotation
Performed after a new key is inserted into the left subtree of the right child of a tree whose root had the balance of -1 before its insertion. Perform the R rotation of the right subtree followed by the L rotation of the root.
2-3 trees
May have 2 nodes and 3 nodes, and all leaves are on the same level.
Heap
A binary tree with keys at its nodes such that it is near-complete (only the rightmost nodes at the bottom level are missing)
Every key is greater than the keys of its children
Heap array representation
Root node at position 1
A node at position j has its left child at 2j, right child at 2j+1, and parent at ⌊j/2⌋
Priority Queue
Ordered set with operations:
find element with highest priority
delete element with highest priority
insert element with assigned priority
Heaps can implement them
Heap construction
Bottom-up: put everything in then fix
Top-down: successively insert elements into an initially empty heap
