Two-Three Trees & Red Black Trees Flashcards
1
Q
Two-three trees maintains constant depth for every leaf.
A
True.
2
Q
Red black trees allow depth of every leaf to vary by at most a factor of 2.
A
True.
3
Q
What is the max depth of a two three tree?
A
O(logn)
4
Q
What is the worst case complexity of searching in a BST?
A
theta(N)
5
Q
What is the worst case complexity of inserting into a BST?
A
theta(N)
6
Q
What is the worst case complexity of searching in a 2-3 tree? (red black implementation)
A
theta(2 lg N)
7
Q
What is the worst case complexity of insterting into a 2-3 tree? (red black implementation)
A
theta(2 lg N)
8
Q
Are red black trees BSTs?
A
Yes.
9
Q
Are red black trees 2-3 trees?
A
Yes.
