Binary Tree

Question 1

what is a binary tree

Answer 1

nodes with links to left and right nodes

Question 2

how to get the height of a tree with N nodes

Answer 2

lg N

Question 3

what is binary heap

Answer 3

array representation of a heap ordered complete binary tree

Question 4

nodes in a binary tree must always first be added from which direction

Answer 4

left

Question 5

what is the rule about parents and children for binary trees

Answer 5

parent’s keys must not be smaller than their children’s keys

Question 6

when a binary tree is put into a binary representation, what number do the indices start at

Answer 6

1

Question 7

where is the largest key found in the binary tree array representation

Answer 7

a[1]

Question 8

what is the first node (largest node) called in a binary tree

Answer 8

root

Question 9

where is the parent of node k found in array representation of binary tree

Answer 9

k/2

Question 10

where are the children of node k found in array representation of binary tree

Answer 10

2k (left)

2k+1 (right)

Question 11

the left subtree of k is empty if

Answer 11

2k > N

Question 12

the right subtree of k is empty if

Answer 12

2k+1 > N

Question 13

when is k a leaf node

Answer 13

2k > n

Question 14

what is a leaf node

Answer 14

a node without isblings

Question 15

is a binary tree completely sorted

Answer 15

no

Question 16

when inserting into a binary tree, where is node first added

Answer 16

add to the end

Question 17

how does insert work in binary trees

Answer 17

add node to the end

swim node up to the top by exchanging children with parent if it is larger than the parent

Question 18

how does remove work in binary trees

Answer 18

remove root by exchanging with the node at the end, sink this node down

Question 19

what would the most number of comparisons be in the insertion method

Answer 19

logN

worst case would be it swims up to the root, so =height of the tree

Question 20

what would the maximum number of insertions be in a delete functions

Answer 20

logN

worst case is it sinks all the way down
cost = logN = height of tree

Question 21

ways to improve the binary tree

Answer 21

half swaps

d-way trees

Question 22

what are half swaps

Answer 22

instead of swapping each time, swim one value up until it finds it position then sink all the other values down by 1

Question 23

what is the height of a d-way binary tree

Answer 23

log vd N

Question 24

where is the sweet spot of d way trees

Answer 24

4

constant time improvement

Question 25

any more than d=4 is inefficient, why

Answer 25

comparisons dominate run time

Question 26

is binary heap cache friendly, hwy

Answer 26

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)

Question 27

cost of delete in d way tree

Answer 27

d log vd N

Question 28

two nodes that have the same parent are called what

Answer 28

siblings