Part 7

Question 1

when is a binary tree balanced?

Answer 1

If for every non-leaf node the number of nodes in its left child and right child differ by no more than 1

Question 2

What is the average and worst case time complexities for binary search tree operations?

Answer 2

Average O(logn)

Worst O(n)

Question 3

The depth of a balanced binary tree containing n nodes is exactly

Answer 3

floor(log₂n) + 1

Question 4

When would it make sense to ensure a binary tree stays balanced?

Answer 4

If it will be searched frequently but not inserted or removed frequently

Question 5

Rebalancing a tree takes at least ___________ time in the worst case

Answer 5

O(n)

Question 6

What is another term for dept-balanced?

Answer 6

AVL-Balanced

Question 7

What does depth balanced mean?

Answer 7

for every non-leaf node the depth of its left child and the depth of its right child differ by no more than one

Question 8

The depth of any AVL-Balanced tree containing n nodes is no more than

_________

as long as n > 1

Answer 8

2log₂n

Question 9

What is an AVL tree?

Answer 9

A depth balanced binary search tree

Question 10

The rebalancing of an AVL tree can be performed in __________ time

Answer 10

constant

Question 11

The time taken to deduce whether an AVL tree needs rebalancing is proportional to

Answer 11

its depth

Question 12

Searching, insertion and deletion for AVL trees can be performed in _________ time

Answer 12

O(logn)

Question 13

What is the most efficient way of storing information in AVL tree nodes?

Answer 13

Simply store details of which child is deeper

Question 14

Functions that are computable using the Church-Turing definitions can be implemented in which programming language?

Answer 14

Any

Question 15

What is the halting problem?

Answer 15

The question of whether a program will terminate when run with specific data, specifically:

can we write a program taking source code and input as strings that will determine whether the program in the source will terminate with the data

Question 16

Write the source code to prove the halting problem is non computable:

Answer 16

public static void main(String args[]) {

String s; // read input into s

try {

if (halts(s, s)) { while(true) {} }

catch (Exception e) {}

}