B-trees - Chapter 10

Question 1

In a blank each node has one key and up to two children.

Answer 1

binary tree

Question 2

A blank with order K is a tree where nodes can have up to K-1 keys and up to K children.

Answer 2

B-tree

Question 3

The blank is the maximum number of children a node can have. Ex: In a B-tree with order 4, a node can have 1, 2, or 3 keys, and up to 4 children.

Answer 3

order

Question 4

B-trees have the following 5 properties:

Answer 4

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 subtree keys are < that key, and all right subtree keys are > that key.

Question 5

As the order of a B-trees blank, the maximum number of keys and children per node increases. An internal node must have one more child than keys. Each child of an internal node can have a different number of keys than the parent internal node. Ex: An internal node in an order 5 B-tree could have 1 child with 1 key, 2 children with 3 keys, and 2 children with 4 keys.

Answer 5

increases

Question 6

A is an order 4 B-tree. Therefore, a 2-3-4 tree node contains 1, 2 or 3 keys. A leaf node in a 2-3-4 tree has no children.

Answer 6

2-3-4 tree

Question 7

The keys and children in a 2-3-4 tree node are commonly referred to by blank. So keys are called key 0, key 1, and key 2, and children are called child 0, child 1, child 2, and child 3. If a node has one key, then keys 1 and 2 and children 2 and 3 are not used.

Answer 7

index.

Question 8

If a node contains two keys, then key 2 and child 3 are not used. A 2-3-4 tree node containing three keys is said to be blank.

Answer 8

full

Question 9

A node with one key is called a blank. A node with two keys is called a blank. A node with three keys is called a blank

Answer 9

2-node.
3-node
4-node.

Question 10

Given a key, a blank 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. The table below shows conditions, which are checked in order, and the corresponding child node

Answer 10

search

Question 11

key < node’s A key Child node to search

Answer 11

left

Question 12

node has only 1 key or key < node’s B key Child node to search

Answer 12

middle1

Question 13

node has only 2 keys or key < node’s C key Child node to search

Answer 13

middle2

Question 14

not - key < node’s A key or node has only 1 key or key < node’s B key or node has only 2 keys or key < node’s C key Child node to search

Answer 14

right

Question 15

Given a new key, a 2-3-4 tree blank inserts the new key in the proper location such that all 2-3-4 tree properties are preserved. New keys are always inserted into leaf nodes in a 2-3-4 tree. Insertion returns the leaf node where the key was inserted, or null if the key was already in the tree.

Answer 15

insert operation

Question 16

An important operation during insertion is the blank, which is done on every full node encountered during insertion traversal. The split operation moves the middle key from a child node into the child’s parent node. The first and last keys in the child node are moved into two separate nodes. The split operation returns the parent node that received the middle key from the child.

Answer 16

split operation

Question 17

Splitting an internal node allocates blank, each with a single key, and the middle key from the split node moves up into the parent node. Splitting the root node allocates blank, each with a single key, and the root of the tree becomes a new node with a single key.

Answer 17

2 new nodes
3 new nodes

Question 18

During a split operation, any blank may need to gain a key from a split child node. This key may have children on either side.

Answer 18

non-full internal node

Question 19

A new key is always inserted into a blank node.

Answer 19

non-full leaf

Question 20

2-3-4 tree non-full-leaf insertion cases - New key equals an existing key in node

Answer 20

No insertion takes place, and the node is not altered.

Question 21

2-3-4 tree non-full-leaf insertion cases - New key is < node’s first key

Answer 21

Existing keys in node are shifted right, and the new key becomes node’s first key.

Question 22

2-3-4 tree non-full-leaf insertion cases - Node has only 1 key or new key is < node’s middle key

Answer 22

Node’s middle key , if present, becomes last key, and new key becomes node’s middle key.

Question 23

2-3-4 tree non-full-leaf insertion cases - Not (Node has only 1 key or new key is < node’s middle key or New key is < node’s first key or New key equals an existing key in node)

Answer 23

New key becomes node’s last key.

Question 24

Multiple insertion schemes exist for 2-3-4 trees. The blank scheme always splits any full node encountered during insertion traversal. The preemptive split insertion scheme ensures that any time a full node is split, the parent node has room to accommodate the middle value from the child.

Answer 24

preemptive split insertion

Question 25

Removing an item from a 2-3-4 tree may require rearranging keys to maintain tree properties. A blank is a rearrangement of keys between 3 nodes that maintains all 2-3-4 tree properties in the process. The 2-3-4 tree removal algorithm uses rotations to transfer keys between sibling nodes

Answer 25

rotation

Question 26

A blank on a node causes the node to lose one key and the node’s right sibling to gain one key.

Answer 26

right rotation

Question 27

A blank on a node causes the node to lose one key and the node’s left sibling to gain one key.

Answer 27

left rotation

Question 28

Blank returns a pointer to the left sibling of a node or null if the node has no left sibling. BTreeGetLeftSibling returns null, left, middle1, or middle2 if the node is the left, middle1, middle2, or the right child of the parent, respectively. Since the parent node is required, a precondition of this function is that the node is not the root.

Answer 28

BTreeGetLeftSibling

Question 29

Blank returns a pointer to the right sibling of a node or null if the node has no right sibling.

Answer 29

BTreeGetRightSibling

Question 30

Blank takes a parent node and a child of the parent node as arguments, and returns the key in the parent that is immediately left of the child.

Answer 30

BTreeGetParentKeyLeftOfChild

Question 31

Blank takes a parent node, a child of the parent node, and a key as arguments, and sets the key in the parent that is immediately left of the child.

Answer 31

BTreeSetParentKeyLeftOfChild

Question 32

Blank operates on a non-full node, adding one new key and one new child to the node. The new key must be greater than all keys in the node, and all keys in the new child subtree must be greater than the new key. Ex: If the node has 1 key, the newly added key becomes key B in the node, and the child becomes the middle2 child. If the node has 2 keys, the newly added key becomes key C in the node, and the child becomes the right child.

Answer 32

BTreeAddKeyAndChild

Question 33

Blank removes a key from a node using a key index in the range [0,2]. This process may require moving keys and children to fill the location left by removing the key.

Answer 33

BTreeRemoveKey

Question 34

The blank operates on a node, causing a net decrease of 1 key in that node. The key removed from the node moves up into the parent node, displacing a key in the parent that is moved to a sibling. No new nodes are allocated, nor existing nodes deallocated during rotation. The code simply copies key and child pointers.

Answer 34

rotation algorithm

Question 35

When rearranging values in a 2-3-4 tree during deletions, rotations are not an option for nodes that do not have a sibling with 2 or more keys. Blank provides an additional option for increasing the number of keys in a node. A fusion 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.

Answer 35

Fusion

Question 36

Fusion is the inverse operation of a blank. The key taken from the parent node must be the key that is between the 2 adjacent siblings. The parent node must have at least 2 keys, with the exception of the root.

Answer 36

split

Question 37

Fusion of the blank is a special case that happens only when the root and the root’s 2 children each have 1 key. In this case, the 3 keys from the 3 nodes are combined into a single node that becomes the new root node.

Answer 37

root node

Question 38

For the non-root case, fusion operates on blank 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 node. The parent node must have at least 2 keys.

Answer 38

2 adjacent siblings

Question 39

In the fusion algorithm below, the blank function returns an integer in the range [0,2] that indicates the index of the key within the node. The blank functions sets the left, middle1, middle2, or right child pointer based on an index value of 0, 1, 2, or 3, respectively.

Answer 39

BTreeGetKeyIndex
BTreeSetChild

Question 40

A B-Tree blank operates on a node with 1 key and increases the node’s keys to 2 or 3 using either a rotation or fusion. 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. The merge operation can be performed on any node that has 1 key and a non-null parent node with at least 2 keys.

Answer 40

merge

Question 41

Blank returns the minimum key in a subtree.

Answer 41

BTreeGetMinKey

Question 42

Blank returns a pointer to a node’s left, middle1, middle2, or right child, if the childIndex argument is 0, 1, 2, or 3, respectively.

Answer 42

BTreeGetChild

Question 43

blank returns the child of a node that would be visited next in the traversal to search for the specified key.

Answer 43

BTreeNextNode

Question 44

Blank swaps one key with another in a subtree. The replacement key must be known to be a key that can be used as a replacement without violating any of the 2-3-4 tree rules.

Answer 44

BTreeKeySwap

Question 45

Given a key, a 2-3-4 tree blank removes the first-found matching key, restructuring the tree to preserve all 2-3-4 tree rules. Each successful removal results in a key being removed from a leaf node. Two cases are possible when removing a key, the first being that the key resides in a leaf node, and the second being that the key resides in an internal node.

Answer 45

remove operation

Question 46

A key can only be removed from a leaf node that has 2 or more keys. The blank removal scheme involves increasing the number of keys in all single-key, non-root nodes encountered during traversal. The merging always happens before any key removal is attempted. Preemptive merging ensures that any leaf node encountered during removal will have 2 or more keys, allowing a key to be removed from the leaf node without violating the 2-3-4 tree rules.

Answer 46

preemptive merge

Question 47

To remove a key from an blank, 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.

Answer 47

internal node