Ch 6: Balanced Trees I

Question 1

what is a B-tree?

Answer 1

a tree with order K where nodes can have up to K-1 trees and up to K children

Question 2

what is order?

Answer 2

the maximum number of children a node can have

Question 3

what are the 5 properties of B-trees?

Answer 3

• 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

Question 4

what makes a node full?

Answer 4

a 2-3-4 tree node that has exactly 3 keys

Question 5

what are the key labels of a 2-3-4 tree?

Answer 5

A,B,C

Question 6

what are the child node labels of a 2-3-4 tree?

Answer 6

left, middle 1, middle 2, right

Question 7

how many children can a node with K keys have?

Answer 7

K+1

Question 8

explain the 2-3-4 tree search algorithm

Answer 8

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.

Question 9

explain what the insert operation does

Answer 9

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

Question 10

what is the split operation?

Answer 10

an operation that is executed on every full node encountered during insertion traversal

Question 11

explain the split operation

Answer 11

• 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

Question 12

how many new nodes are allocated during split?

Answer 12

• 2 when splitting an internal node

- 3 when splitting root

Question 13

what is the preemptive split?

Answer 13

an insertion scheme that always splits any full node encountered during an insertion traversal

Question 14

what does the preemptive split ensure?

Answer 14

ensures that any time a full node is split, the parent node has room to accommodate the middle value from the child

Question 15

what is rotation?

Answer 15

a rearrangement of keys between 3 nodes that maintains all 2-3-4 tree properties in the process

Question 16

what are the 2 different rotations? explain

Answer 16

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

Question 17

does rotation allocate any new nodes?

Answer 17

no

Question 18

during delete, what type of nodes do rotations not operate on?

Answer 18

nodes that do not have a sibling with 2+ keys (nodes that have siblings with only 1 key)

Question 19

what is fusion?

Answer 19

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

Question 20

how is fusion related to split?

Answer 20

fusion is the inverse operation of split

Question 21

when is the root node a special case for fusion and explain what happens

Answer 21

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

Question 22

explain fusion operation for non-root nodes

Answer 22

• 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

Question 23

what is merge?

Answer 23

an operation on a node with 1 key and increases the node’s keys to 2 or 3 using either rotation or fusion

Question 24

explain merge operation

Answer 24

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.

Question 25

what type of node can merge operation be performed on?

Answer 25

a node that has 1 key and a non-null parent node with at least 2 keys

Question 26

what are the two possible cases when removing a key?

Answer 26

• key is leaf node

- key is internal node

Question 27

what is the requirement for removal of a leaf node?

Answer 27

leaf node must have 2+ keys

Question 28

what is preemptive merge?

Answer 28

a removal scheme that involves increasing the number of keys in all single-key, non-root nodes encountered during traversal

Question 29

when does preemptive merge occur?

Answer 29

before any key removal is attempted

Question 30

what does preemptive merge ensure?

Answer 30

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

Question 31

explain removal operation

Answer 31

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.