General knowledge
write the c++ definition of an array binary tree
private:
DT* array
int capacity
int size
public:
BT(int capacity)
~BT
isEmpty
size
height
root
leftChildIndex
rightchildIndex
parentIndex
insert
what is the min height of a BST with 10 nodes
4
define what a Red black tree is
a self adjusting BST tree that maintains balance following the red property and black height property
what are the operations that can be done on a min heap?
find min, delete min, insert
what are is the best and worst case complexity for searching a binary search tree?
Best: O(1)
Worst: O(n)
perform a pre order traversal of this tree:
7
/ \
3 10
/ \ / \
1 4 8 13
\ \
6 14
7, 3, 1, 4, 6, 10, 8, 13, 14
write an algorithm to sort a binary search tree along with its time complexity
in order traversal and O(n)
which direction is a zig rotation
clockwise
which direction is a zag rotation
counterclockwise
what are the three conditions that should be checked before removing a node?
1. is it a leaf?
2. does it have one child?
3. does it have 2 children?
preform an inorder traversal of this tree:
7
/ \
3 10
/ \ / \
1 4 8 13
\ \
6 14
1, 3, 4, 6, 7, 8, 10, 13, 14
write an algorithm to perform heap sort and and time complexity
O(nlogn)
or (int i = 0; i < n; i++) {
heap.insert(A[i])
}
for (int i = 0; i < n; i++) {
sortedArr.add(heap.findMin())
heap.removeMin()
}
given this max heap, insert 100 then show the heap after you insert, show all steps
15
/ \
10 9
/ \ / \
8 9 6 3
/ \
4 2
100
/ \
15 9
/ \ / \
8 10 6 3
/ \ /
4 2 9
construct a min max structure with the following list:
46, 31, 71, 10, 31, 21, 8 13, 11, 41, 16
8
/ \
46 71
/ \ / \
10 1113 16
/ \ / \
21 3131 41
what is the max height of a binary tree with n nodes?
n or n-1
preform post order traversal of this tree:
7
/ \
3 10
/ \ / \
1 4 8 13
\ \
6 14
1, 6, 4, 3, 8, 14, 13, 10, 7
what are the properties of a red black tree
Red condition: a red tree/node can’t be adjacent to another red tree/node (sibling or parent)
Black Height: every path from the root to a leaf has the same number of black nodes, ensuring no path is twice as long as another
what are the allowed values of the balance factor of AVL trees?
-1, 0, 1
name the four binary search trees we covered this semester
splay trees, AVL trees, red black, 2-3 trees
write the code to perform a zig rotation
node * x = y->left;
y->left = x->right
x->right = y
return x
How many ways can a binary search tree be stored?
Left pointer, Right pointer, and Node
Array Implementation
Generalized List
Parent Array
Pre-order and Post Order traversal
Complete Binary Tree Representation
insert the following values into a 2-3 tree
10,20,30,40,50,60
IN NOTES SORRY I CAN'T INSERT PICS
show the tree after splaying 3
7
/ \
6 8
/ \
2 9
/ \ \
1 4 10
/ \
3 8
3
/ \
2 4
/ \
1 5
\
6
\
7
\
8.....
insert 35 into the tree below and rebalance it after:
70
/ \
50 90
/ \ / \
30 60 80 100
/ \
20 40
i have no idea how to balance it sorry guys
write the code to for a zag rotation
node* x = y->right
y->right = x->left
x->left = y
return x