Chapter 4 (Trees) Flashcards
What are the three methods of tree traversal?
Preorder Postorder Inorder
What does a splay tree do?
Rotates accessed node to the root to make future accesses cheaper
What is a proper ancestor/descendant?
Refers to ancestor/descendant other than itself
How can an expression tree be evaluated?
By recursively evaluating the left and right subtrees, then applying the operator at the root
What is the zig-zag rotation the same as?
Double rotation
What is the height of a B tree?
log base m of n
How do you do a zig-zag rotation in a splay tree?
Same as a double rotation
When do you have an ancestor?
If path exists up the tree
What does the balance condition of an AVL tree help to ensure?
O(log(n)) depth
How is inorder traversal done?
Left child, root, right child
How should a directory be printed?
Preorder
Most operations for a tree run in…
O(log n)
All leaf nodes of a B+ tree are at the same depth and have ____ to ____ data items, for some L
L/2 ceiling, L
Tree depth is defined as
Length from root to deepest leaf
Nonleaf nodes of a B+ tree store up to ____ keys
M-1
How is preorder traversal done?
Parent first, then children
All nonleaf nodes of a B+ tree have ____ to ____ children
M/2 ceiling, M
Length of a path is defined as
Number of edges on the path
When do you have a descendant?
If path exists down the tree
Where does the B+ tree store data?
In the leaf nodes
How is postorder traversal done?
Children first, then parent
If we wanted to sum the file sizes in the directory, which order should we traverse in?
Postorder
Where does a regular B tree store data?
Throughout the tree
T/F An insert can violate the AVL property
T