Binary Search Tree
Stacks and Queues
AVL Trees
Red Black Trees
Algorithmic Complexity
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
Operations of a queue
What is push, pop and peek?
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
The time complexity of pushing an element into a linked list
What is O(1)? (or: constant time)
200
Post order traversal traverses a tree in what order?
Left, Right, Root
200
How do elements behave in a stack?
What is FILO(First in last out)
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
True or False:
O(log(n)) is a faster algorithm than O(n)
True
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
If I "push" to the stack the element is here.
What is the top
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
The time complexity of accessing the third element in an array
What is O(1)? (or: constant time)
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
The stack that results from the following operations:
Push(1)
Push(2)
Push(3)
Pop()
Pop()
Push(4)
Push(5)
Push(6)
Pop()
Push(7)
1 4 5 7 <- Top
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 time complexity of merge sort
What is O(n log(n))?
500
The correct IN-ORDER traversal for the above tree is
4, 2, 5, 3, 1 TRUE/FALSE
FALSE
500
If I have a stack of queues of stacks is this operations valid?
stack.push().peek().pop()
What is True
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
The time complexity of an algorithm with a for loop that iterates "size" times inside another for loop that iterates "size" times
What is O(n^2)