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
In an expression tree, the leaves are ____ and the other nodes are ____
Operands, operators
Splay trees have ____ amortized cost per operation
O(log N)
T/F A binary tree depth CAN be N-1
T
Node depth is defined as
Length from root
What is the average depth of a binary tree?
O(sqrt(n))
Splay trees guarantee ____ over M operations starting with an empty tree
O(M log N)
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.
An M-ary search tree uses ____ keys for ____ branches
M-1, M
Amortized is not the same as O(log N) cost per operation, since some operations may not be ____
O(log N)
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
What’s special about the in-order traversal of splay trees when you do a rotation?
It remains the same
Node height is defined as
Length to deepest descendant leaf
How can a binary tree be implemented?
Storing the data for a node plus the two child pointers
T/F The root of a B+ tree is either a leaf or has 2 to M children
T
T/F Trees having more than two children may be implemented using linked lists of nodes
T
