Chapter 4 (Trees) Flashcards

1
Q

What are the three methods of tree traversal?

A

Preorder Postorder Inorder

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What does a splay tree do?

A

Rotates accessed node to the root to make future accesses cheaper

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a proper ancestor/descendant?

A

Refers to ancestor/descendant other than itself

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

How can an expression tree be evaluated?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the zig-zag rotation the same as?

A

Double rotation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the height of a B tree?

A

log base m of n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

Same as a double rotation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

When do you have an ancestor?

A

If path exists up the tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

O(log(n)) depth

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How is inorder traversal done?

A

Left child, root, right child

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How should a directory be printed?

A

Preorder

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Most operations for a tree run in…

A

O(log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

L/2 ceiling, L

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Tree depth is defined as

A

Length from root to deepest leaf

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

M-1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How is preorder traversal done?

A

Parent first, then children

17
Q

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

A

M/2 ceiling, M

18
Q

Length of a path is defined as

A

Number of edges on the path

19
Q

When do you have a descendant?

A

If path exists down the tree

20
Q

Where does the B+ tree store data?

A

In the leaf nodes

21
Q

How is postorder traversal done?

A

Children first, then parent

22
Q

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

23
Q

Where does a regular B tree store data?

A

Throughout the tree

24
Q

T/F An insert can violate the AVL property

25
In an expression tree, the leaves are ____ and the other nodes are \_\_\_\_
Operands, operators
26
Splay trees have ____ amortized cost per operation
O(log N)
27
T/F A binary tree depth CAN be N-1
T
28
Node depth is defined as
Length from root
29
What is the average depth of a binary tree?
O(sqrt(n))
30
Splay trees guarantee ____ over M operations starting with an empty tree
O(M log N)
31
What is the balance condition of an AVL tree?
For every node, the left and right subtrees can differ in height by at most 1.
32
An M-ary search tree uses ____ keys for ____ branches
M-1, M
33
Amortized is not the same as O(log N) cost per operation, since some operations may not be \_\_\_\_
O(log N)
34
How do you do a zig-zig rotation in a splay tree?
The node we want to bring to the top becomes the new root
35
What's special about the in-order traversal of splay trees when you do a rotation?
It remains the same
36
Node height is defined as
Length to deepest descendant leaf
37
How can a binary tree be implemented?
Storing the data for a node plus the two child pointers
38
T/F The root of a B+ tree is either a leaf or has 2 to M children
T
39
T/F Trees having more than two children may be implemented using linked lists of nodes
T