Ch 6: Balanced Trees I Flashcards
what is a B-tree?
a tree with order K where nodes can have up to K-1 trees and up to K children
what is order?
the maximum number of children a node can have
what are the 5 properties of B-trees?
- all keys in a B-tree must be distinct
- all leaf nodes must be at the same level
- an internal node with N keys must have N+1 children
- keys in a node are stored in sorted order from smallest to largest
- each key in a B-tree internal node has one left subtree and one right subtree. all left subtrees are < that key, and all right subtree keys are > that key
what makes a node full?
a 2-3-4 tree node that has exactly 3 keys
what are the key labels of a 2-3-4 tree?
A,B,C
what are the child node labels of a 2-3-4 tree?
left, middle 1, middle 2, right
how many children can a node with K keys have?
K+1
explain the 2-3-4 tree search algorithm
returns the first node found matching that key, or returns null if a matching node is not found. Searching a 2-3-4 tree is a recursive process that starts with the root node. If the search key equals any of the keys in the node, then the node is returned. Otherwise, a recursive call is made on the appropriate child node. Which child node is used depends on the value of the search key in comparison to the node’s keys.
explain what the insert operation does
new keys are inserted into leaf nodes in a 2-3-4 tree, returns the leaf node where the key was inserted or null if the key was already in the tree
what is the split operation?
an operation that is executed on every full node encountered during insertion traversal
explain the split operation
- moves middle from a child node into the child’s parent node
- the first and last keys in the child node are moved into separate nodes
- returns the parent node that received the middle key from the child
how many new nodes are allocated during split?
- 2 when splitting an internal node
- 3 when splitting root
what is the preemptive split?
an insertion scheme that always splits any full node encountered during an insertion traversal
what does the preemptive split ensure?
ensures that any time a full node is split, the parent node has room to accommodate the middle value from the child
what is rotation?
a rearrangement of keys between 3 nodes that maintains all 2-3-4 tree properties in the process
what are the 2 different rotations? explain
right rotation - causes node to lose one key and the node’s right sibiling to gain one key
left rotation - causes node to lose one key and the node’s left sibling to gain one key
does rotation allocate any new nodes?
no
during delete, what type of nodes do rotations not operate on?
nodes that do not have a sibling with 2+ keys (nodes that have siblings with only 1 key)
what is fusion?
an operation that is a combination of 3 keys: 2 from adjacent sibling nodes that have 1 key each, and a third from the parent of the siblings
how is fusion related to split?
fusion is the inverse operation of split
when is the root node a special case for fusion and explain what happens
special case: when root and root’s children each have 1 key
- the 3 keys from the 3 nodes are combined into a single node that becomes the new root node
explain fusion operation for non-root nodes
- operates on 2 adjacent siblings that each have 1 key
- the key in the parent node that is between the 2 adjacent siblings is combined with the 2 keys from the two siblings to make a single, fused noe
- parent node must have at least 2 keys
what is merge?
an operation on a node with 1 key and increases the node’s keys to 2 or 3 using either rotation or fusion
explain merge operation
A node’s 2 adjacent siblings are checked first during a merge, and if either has 2 or more keys, a key is transferred via a rotation. Such a rotation increases the number of keys in the merged node from 1 to 2. If all adjacent siblings of the node being merged have 1 key, then fusion is used to increase the number of keys in the node from 1 to 3.
what type of node can merge operation be performed on?
a node that has 1 key and a non-null parent node with at least 2 keys
what are the two possible cases when removing a key?
- key is leaf node
- key is internal node
what is the requirement for removal of a leaf node?
leaf node must have 2+ keys
what is preemptive merge?
a removal scheme that involves increasing the number of keys in all single-key, non-root nodes encountered during traversal
when does preemptive merge occur?
before any key removal is attempted
what does preemptive merge ensure?
that any leaf node encountered during removal will have 2+ keys, allowing a key to be removed from the leaf node without violating the 2-3-4 tree rules
explain removal operation
To remove a key from an internal node, the key to be removed is replaced with the minimum key in the right child subtree (known as the key’s successor), or the maximum key in the leftmost child subtree. First, the key chosen for replacement is stored in a temporary variable, then the chosen key is removed recursively, and lastly the temporary key replaces the key to be removed.
