Binary Search Tree (1) Flashcards
what is a binary search tree
a binary tree in symmetric order
what does the symmetric order property of a binary search tree mean
each node’s key is:
larger than all the keys in its left subtree
smaller than all the keys in its right subtree
what is a leaf of a tree
a node with no children
what is the height of a BST
the maximum number of links from the root to a leaf
what is a level of a BST
the maximum number of nodes from the root to a leaf (includes the root and leaf)
what is the size of a BST
number of nodes in the tree
what is the depth of a BST
number of links from the root to the node
at most, how often does every key appear in a BST
once
every node must have at most how many parents
1
the root has 0
the rest have 1
generally what is the number of levels in a BST
height + 1
in general, how do we search through a BST
currentNode = root
if key we are searching for is less than the currentNode, go left
if the key we are searching for is greater than the currentNode, go right
if the key we are searching for is equal to the key in the currentNode, return
in general, how do we insert into a BST
search for the key we want to insert
if found: do nothing
else: create a new node in the space where the search finished
what does the BST java definition reference
the root node
what are the four values that a BST node is composed on
key
value
left ref
right ref
which of the fields in the node of the BST should be comparable
key
the types key and value in the BST node are …
generic
what does the get function do
return value corresponding to given key
or null if no such key
how does the get function work
while the node is not null
if the key we are looking for is less than the given key go left
if the key we are looking for is greater than the given key go right
else if the keys are equal, return the value of that node
what parameter does the get function take
key
what is the runtime cost of get
1 + depth
so depth as we ignore constant
what is the worst case input for get
asking to get an element that is not in the tree
the get method is the only method that doesn’t use …
recursion
what is the worst possible arrangement of a binary search tree, or any tree
when it looks more like a linked list (each node has either 0 or 1 children)
what is the worst case height of a binary search tree
N-1
what does the put method do
associates a value with a key
how does the put method work
search for the key
if the key is in the tree, reset its value
if the key is not in the tree, add a new node
worst case run time of put function
depth + 1
what does tree shape depend on
order of insertion
what does the best case BST look like
each node has 2 children
balanced
what does the minimum function do
returns the smallest key
what does the maximum function do
returns the largest key
what does the floor function do
finds the largest key that is less than or equal to a given key
what does the ceiling key do
finds the smallest key that is greater than or equal to a given key
what are the three cases in the method for finding the floor
floor(k)
CASE 1:
k equals the key in the node
CASE 2:
floor of k is in the left subtree
CASE 3:
Floor of k is in the right subtree (if there is any key <= k in the right subtree) otherwise it is the key in the node
how is the minimum function implemented
follow left links until the one with a null left link
how is the maximum function implemented
follow right links until find the one with a null right link
what does the rank function do
returns how may keys are less than k
what parameters does the rank function take
k
what does the select function do
tells us what key has a rank n
what parameter does the select function take
int n
how to implement rank and select effectivelu
in each node, we store the number of nodes in the subtree rooted at that node
how does the rank function work
count what’s in the left subtree and in the left tree of the parent (as these are all definitely less) using recursion
add one for the parent
how does the select function work
compare rankings on either side of node
go to side which contains the ranking
what does it mean to traverse through a tree
process all the nodes in the tree
what are the 3 kinds of traversals of BST
in order
pre order
post order
how does pre order traversal work
- prints root
- prints left subtree
- prints right subtree
what is the in order traversal
process left tree until null
process the node
process the right subtree
in what order does the in order traversal print nodes
ascending
what is post order traversal
process all of lefr subtree
process all of right subtree
process node
which of the traversals tells us nothing of the structure of the BST
in order traversal
what does the delete function take as a parameter
key
what are the 3 cases in Hibbard deletion
case 0: node we want to delete has 0 children (delete by setting parent link to null)
case 1: node we want to delete has 1 child (delete by replacing parent link)
case 2: node we want to delete has 2 children (find successor node, delete it from subtree and replace in space of node we want to delete)
what is the average case time complexity of the delete funtion
sq(N)
what determines shape of BST
order of insertion
how many worse case trees can be created from an array with N elements
2^n-1 trees
what does the size method return
the number of nodes below that node in the subtree
trees lean in what direction
left
why do we expect a BST to lean to the left
always deletes from right subtree, creating a left spine
why is it bad that a BST will start to lean to the left
run times worsen with deletions
