Chapter 4 (Trees)

Question 1

What are the three methods of tree traversal?

Answer 1

Preorder Postorder Inorder

Question 2

What does a splay tree do?

Answer 2

Rotates accessed node to the root to make future accesses cheaper

Question 3

What is a proper ancestor/descendant?

Answer 3

Refers to ancestor/descendant other than itself

Question 4

How can an expression tree be evaluated?

Answer 4

By recursively evaluating the left and right subtrees, then applying the operator at the root

Question 5

What is the zig-zag rotation the same as?

Answer 5

Double rotation

Question 6

What is the height of a B tree?

Answer 6

log base m of n

Question 7

How do you do a zig-zag rotation in a splay tree?

Answer 7

Same as a double rotation

Question 8

When do you have an ancestor?

Answer 8

If path exists up the tree

Question 9

What does the balance condition of an AVL tree help to ensure?

Answer 9

O(log(n)) depth

Question 10

How is inorder traversal done?

Answer 10

Left child, root, right child

Question 11

How should a directory be printed?

Answer 11

Preorder

Question 12

Most operations for a tree run in…

Answer 12

O(log n)

Question 13

All leaf nodes of a B+ tree are at the same depth and have ____ to ____ data items, for some L

Answer 13

L/2 ceiling, L

Question 14

Tree depth is defined as

Answer 14

Length from root to deepest leaf

Question 15

Nonleaf nodes of a B+ tree store up to ____ keys

Answer 15

M-1

Question 16

How is preorder traversal done?

Answer 16

Parent first, then children

Question 17

All nonleaf nodes of a B+ tree have ____ to ____ children

Answer 17

M/2 ceiling, M

Question 18

Length of a path is defined as

Answer 18

Number of edges on the path

Question 19

When do you have a descendant?

Answer 19

If path exists down the tree

Question 20

Where does the B+ tree store data?

Answer 20

In the leaf nodes

Question 21

How is postorder traversal done?

Answer 21

Children first, then parent

Question 22

If we wanted to sum the file sizes in the directory, which order should we traverse in?

Answer 22

Postorder

Question 23

Where does a regular B tree store data?

Answer 23

Throughout the tree

Question 24

T/F An insert can violate the AVL property

Answer 24

T

Question 25

In an expression tree, the leaves are ____ and the other nodes are ____

Answer 25

Operands, operators

Question 26

Splay trees have ____ amortized cost per operation

Answer 26

O(log N)

Question 27

T/F A binary tree depth CAN be N-1

Answer 27

T

Question 28

Node depth is defined as

Answer 28

Length from root

Question 29

What is the average depth of a binary tree?

Answer 29

O(sqrt(n))

Question 30

Splay trees guarantee ____ over M operations starting with an empty tree

Answer 30

O(M log N)

Question 31

What is the balance condition of an AVL tree?

Answer 31

For every node, the left and right subtrees can differ in height by at most 1.

Question 32

An M-ary search tree uses ____ keys for ____ branches

Answer 32

M-1, M

Question 33

Amortized is not the same as O(log N) cost per operation, since some operations may not be ____

Answer 33

O(log N)

Question 34

How do you do a zig-zig rotation in a splay tree?

Answer 34

The node we want to bring to the top becomes the new root

Question 35

What’s special about the in-order traversal of splay trees when you do a rotation?

Answer 35

It remains the same

Question 36

Node height is defined as

Answer 36

Length to deepest descendant leaf

Question 37

How can a binary tree be implemented?

Answer 37

Storing the data for a node plus the two child pointers

Question 38

T/F The root of a B+ tree is either a leaf or has 2 to M children

Answer 38

T

Question 39

T/F Trees having more than two children may be implemented using linked lists of nodes

Answer 39

T