Binary Search Tree
Heaps
AVL Trees
Red Black Trees
Hashing
100
A Binary Search tree is a binary tree with two additional rules what are they (invariant of BST)
•Elements in the left sub-tree of a node have values less than the value of the node.
•Elements in the right sub-tree of a node have values greater than the value of the node.
100
A min heap is a BST with two additional properties, what are they?
•It is a complete tree.
•Minheap: For each node, the node is less than or equal to both the left child and the right child.
100
In an AVL tree a balance factor greater or less than what will result in a re-balancing?
1 and -1
100
A node inserted into a red black tree is always ____ and always has color ____.
a leaf, red
100
When hashing 3498 into a hash table of size 13 using shift folding of the first two digits and the last two digits, what is the resulting index?
2
200
Post order traversal traverses a tree in what order?
Left, Right, Root
200
What is the avg, best, and worst run times for HeapSort?
O(nlogn)
200
There are only two ways that a tree or a sub tree can become unbalanced, what are they?
Adding or removing an element.
200
When inserting into a red black tree, what would have to happen for it to be a trivial case? (No more operations needed)
The parent of the node is black.
200
What is the worst case run time of trying to search, insert, and delete from a hash table?
O(N)
300
When removing from a BST, and the item you are removing has two children what do you do?
we swap the node to be deleted with a suitable replacement node in one of its sub-trees and remove it from its new position instead.
300
index 0 1 2 3 4 5 6 7 8 9
ele A B C D E F G H I J
This array is a Binary Heap
What is the parent of G?
C
300
When encountering a node that needs to be re-balanced in an AVL tree, what is the maximum number of rotations?
2
300
The root of a Red black tree always gets recolored to what?
black
300
When hashing 102 into a table of size 11 with a radix transformation and a new base of 8, what will the resulting index be?
3
400
All operations on a correctly implemented balanced BST list have an average run time of log n, except for two of them, what are those two?
isEmpty() O(1)
size() O(1)
400
When using a linked implementation of a heap, the addElement() operation needs to do three things, What are they?
add the new node at the appropriate location, reorder the heap to maintain the ordering property, and then reset the lastNode pointer to point to the new last node
400
Recall that rebalancing is only necessary
along __________
This means at most ______need to be checked for
imbalance.
-path of nodes from the altered node to the root
-the depth of the tree’s worth of nodes
400
Name the three rules that govern a red black tree
•The root is black.
•All children of a red node are black.
•Every path from the root to a leaf contains the same number of black nodes.
400
The formula for determining the index of a key when using quadratic probing is:
newHashCode = (hashcode(x) + 2 ^i) % size
TRUE/FALSE
FALSE
newHashCode = (hashcode(x) + i^2) % size
500
The correct IN-ORDER traversal for the above tree is
4, 2, 5, 3, 1 TRUE/FALSE
FALSE
500
A linked implementation of a min Heap's removeMin() operation runs in O(log n) describe why.
•The first process must remove the root element and replace it with the element from the last node (accomplished with simple assignment statements) = O(1)
•The next step must reorder the heap, if necessary, from the root down to a leaf (heapify) = log n because the maximum path length from the root to a leaf is log n.
•Finally, we must determine the new last node (the worst case is that we must traverse from a leaf through the root and down to another leaf) = 2*log n.
500
50
40 60
Null 45
If you remove the 60 from the above tree, what kind of rotation is required to re-balance the tree?
Left-Right
45
40 50
500
When inserting a new node into a red black tree and the parent is red, the parent's sibling is null and the node is outside relative to grandparent, what do you do?
rotate parent and grandparent then recolor
500
Your are trying to hash 7 into a hashtable of size 11 using linear probing to resolve collisions, there have been five collisions before a success, what index is 7 stored at?
hashCode = value % size
1