Binary Search Tree (Module 8.2) PART I Flashcards
If using a poor hash function, hash tables could run in _________ time complexity.
O(n)
When developing a data structure, make sure that it always guarantees _________ worst-case complexity for lookup, insert, and find_min.
O(1)
When searching for a number x using binary search, always start by looking at the ________.
midpoint
In a tree, what should blank left/right fields point to?
null
Each sequence of left/right pointers works like what kind of list?
null-terminated list
What is the best case time complexity for lookup, insert, and find_min?
O(log n)
What is a tree with ordered nodes?
Binary Search Tree
In an ordered tree, smaller values are on the ______ and larger values are on the_____.
left, right
In an empty tree, the key is __________.
not found
In a non-empty tree, if the root contains the key, it’s ________.
found
In a non-empty tree, if the key is smaller than the root’s, go ____.
left
In a non-empty tree, if the key is bigger than the root’s, go _____.
right
True or false: ‘<, ==, and >’ only work for integers.
true
Should a tree store entries for any type?
yes!
What does a binary search tree need to declare a method to compare two keys?
client interface
When checking nodes ordering, the data in every node must be ________ than its right child and ________ than its left child.
smaller, larger
To make sure a tree is ordered, what do we need?
global constraint
What is the global contraint?
T(L) < y < T(R)
What is the local contraint?
x < y < z
What is the difference between global constraint and local constraint?
global checks the whole subtrees while local only checks the child of each node
