Binary Tree Flashcards
what is a binary tree
nodes with links to left and right nodes
how to get the height of a tree with N nodes
lg N
what is binary heap
array representation of a heap ordered complete binary tree
nodes in a binary tree must always first be added from which direction
left
what is the rule about parents and children for binary trees
parent’s keys must not be smaller than their children’s keys
when a binary tree is put into a binary representation, what number do the indices start at
1
where is the largest key found in the binary tree array representation
a[1]
what is the first node (largest node) called in a binary tree
root
where is the parent of node k found in array representation of binary tree
k/2
where are the children of node k found in array representation of binary tree
2k (left)
2k+1 (right)
the left subtree of k is empty if
2k > N
the right subtree of k is empty if
2k+1 > N
when is k a leaf node
2k > n
what is a leaf node
a node without isblings
is a binary tree completely sorted
no
when inserting into a binary tree, where is node first added
add to the end
how does insert work in binary trees
add node to the end
swim node up to the top by exchanging children with parent if it is larger than the parent
how does remove work in binary trees
remove root by exchanging with the node at the end, sink this node down
what would the most number of comparisons be in the insertion method
logN
worst case would be it swims up to the root, so =height of the tree
what would the maximum number of insertions be in a delete functions
logN
worst case is it sinks all the way down
cost = logN = height of tree
ways to improve the binary tree
half swaps
d-way trees
what are half swaps
instead of swapping each time, swim one value up until it finds it position then sink all the other values down by 1
what is the height of a d-way binary tree
log vd N
where is the sweet spot of d way trees
4
constant time improvement
any more than d=4 is inefficient, why
comparisons dominate run time
is binary heap cache friendly, hwy
no
elements aren’t accessed in a linear order
(ie keys are accessed that aren’t in cache as arrays are divided up into blocks, keys could be accessed that are outside of the current block)
cost of delete in d way tree
d log vd N
two nodes that have the same parent are called what
siblings
