University of South Florida Create a Program Code Computer Programming Task

Implement a two-three-four tree accepting integer values. Expand the code in the Files tab under Assignment Documentation/Assignment 1.

You should get started by completing the implementation of the binary search tree from our in-class work to remind yourself how trees work and how complex references work in Java, but I will not require you to submit that code.

  Static test: first few prime numbers:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
67
71
73
79
83
89
97
Without 37:
2
3
5
7
11
13
17
19
23
29
31
41
41
43
47
53
59
67
71
73
79
83
89
97
Without 73:
2
3
5
7
11
13
17
19
23
29
31
41
41
43
47
53
59
67
71
79
83
89
97
Without 97:
2
3
5
7
11
13
17
19
23
29
31
41
41
43
47
53
59
67
71
79
83
89
CASE: 100 integers, 20 finds, 10 removals. Generating…
TwoFourTree add: 0ms find: 0ms del: 0ms (10 missing) find: 0ms
CASE: 1,000 integers, 200 finds, 100 removals. Generating…
TwoFourTree add: 1ms find: 0ms del: 0ms (38 missing) find: 0ms
CASE: 10,000 integers, 2,000 finds, 1,000 removals. Generating…
TwoFourTree add: 3ms find: 0ms del: 2ms (1,242 missing) find: 0ms
CASE: 100,000 integers, 20,000 finds, 10,000 removals. Generating…
TwoFourTree add: 19ms find: 3ms del: 1ms (4,299 missing) find: 3ms
CASE: 1,000,000 integers, 200,000 finds, 100,000 removals. Generating…
TwoFourTree add: 319ms find: 87ms del: 2ms (50,353 missing) find: 60ms
CASE: 10,000,000 integers, 2,000,000 finds, 1,000,000 removals. Generating…
TwoFourTree add: 5,881ms find: 1,291ms del: 25ms (479,865 missing) find: 986ms
public class TwoFourTree {
private class TwoFourTreeItem {
int values = 1;
int value1 = 0;
int value2 = 0;
node is a 3-node or 4-node.
int value3 = 0;
node is a 4-node.
boolean isLeaf = true;
// always exists.
// exists iff the
// exists iff the
TwoFourTreeItem parent = null;
// parent exists iff
the node is not root.
TwoFourTreeItem leftChild = null;
// left and right
child exist iff the note is a non-leaf.
TwoFourTreeItem rightChild = null;
TwoFourTreeItem centerChild = null;
// center child
exists iff the node is a non-leaf 3-node.
TwoFourTreeItem centerLeftChild = null;
// center-left and
center-right children exist iff the node is a non-leaf 4-node.
TwoFourTreeItem centerRightChild = null;
public boolean isTwoNode() {
return false;
}
public boolean isThreeNode() {
return false;
}
public boolean isFourNode() {
return false;
}
public boolean isRoot() {
return false;
}
public TwoFourTreeItem(int value1) {
}
public TwoFourTreeItem(int value1, int value2) {
}
public TwoFourTreeItem(int value1, int value2, int value3) {
}
private void printIndents(int indent) {
for(int i = 0; i < indent; i++) System.out.printf(" } public void printInOrder(int indent) { "); if(!isLeaf) leftChild.printInOrder(indent + 1); printIndents(indent); System.out.printf("%d\n", value1); if(isThreeNode()) { if(!isLeaf) centerChild.printInOrder(indent + 1); printIndents(indent); System.out.printf("%d\n", value2); } else if(isFourNode()) { if(!isLeaf) centerLeftChild.printInOrder(indent + 1); printIndents(indent); System.out.printf("%d\n", value2); if(!isLeaf) centerRightChild.printInOrder(indent + 1); printIndents(indent); System.out.printf("%d\n", value3); } if(!isLeaf) rightChild.printInOrder(indent + 1); } } TwoFourTreeItem root = null; public boolean addValue(int value) { return false; } public boolean hasValue(int value) { return false; } public boolean deleteValue(int value) { return false; } public void printInOrder() { if(root != null) root.printInOrder(0); } public TwoFourTree() { } } import java.util.ArrayList; import java.util.Random; public class App { static long RandomSeed = 1; static Random RandomGenerator = new Random(RandomSeed); private static ArrayList generateIntArrayList(int howMany) { ArrayList list = new ArrayList(howMany); for(int i = 0; i < howMany; i++) { list.add(Integer.valueOf(RandomGenerator.nextInt())); } return list; } private static ArrayList generateStrikeList(ArrayList fromList, int howMany) { ArrayList strikeList = new ArrayList(howMany); int fromLast = fromList.size() - 1; for(int i = 0; i < howMany; i++) { strikeList.add(fromList.get(RandomGenerator.nextInt(fromLast))); } return strikeList; } private static ArrayList generateRemoveList(ArrayList fromList) { ArrayList removeList = new ArrayList(fromList.size()/2); for(int i = 0; i < fromList.size() / 2; i++) { removeList.add(fromList.get(i)); } return removeList; } private static int executeFinds(TwoFourTree coll, ArrayList strikes) { boolean sentinel; int failures = 0; for (Integer e: strikes) { sentinel = coll.hasValue(e.intValue()); if(sentinel == false) { failures++; } } if(failures > 0) {
System.out.printf(“(%,d missing) “, failures);
}
return 0;
}
public static void executeIntCase(int listSize, int strikeSize,
boolean includeRemoves) {
System.out.printf(“CASE: %,d integers, %,d finds, %,d
removals. Generating…\n”, listSize, strikeSize, strikeSize/2);
ArrayList intlist = generateIntArrayList(listSize);
ArrayList strikes = generateStrikeList(intlist,
strikeSize);
ArrayList removeList = generateRemoveList(strikes);
long start;
long end;
long ms;
TwoFourTree theTree = new TwoFourTree();
System.out.printf(”
TwoFourTree “);
start = System.currentTimeMillis();
for (Integer e: intlist) {
theTree.addValue(e.intValue());
}
end = System.currentTimeMillis();
ms = end – start;
System.out.printf(“add: %,6dms “, ms);
start = System.currentTimeMillis();
executeFinds(theTree, strikes);
end = System.currentTimeMillis();
ms = end – start;
System.out.printf(“find: %,6dms “, ms);
if(includeRemoves) {
start = System.currentTimeMillis();
for (Integer e: removeList) {
// System.out.printf(“—– delete %d from tree\n”,
e.intValue());
/// theTree.printInOrder();
theTree.deleteValue(e.intValue());
}
end = System.currentTimeMillis();
ms = end – start;
System.out.printf(“del: %,6dms “, ms);
start = System.currentTimeMillis();
executeFinds(theTree, strikes);
end = System.currentTimeMillis();
ms = end – start;
System.out.printf(“find: %,6dms
“, ms);
}
System.out.printf(“\n”);
// theTree.printInOrder();
}
public static void main(String[] args) throws Exception {
TwoFourTree tft = new TwoFourTree();
tft.addValue(2);
tft.addValue(3);
tft.addValue(5);
tft.addValue(7);
tft.addValue(11);
tft.addValue(13);
tft.addValue(17);
tft.addValue(19);
tft.addValue(23);
tft.addValue(29);
tft.addValue(31);
tft.addValue(37);
tft.addValue(41);
tft.addValue(43);
tft.addValue(47);
tft.addValue(53);
tft.addValue(59);
tft.addValue(67);
tft.addValue(71);
tft.addValue(73);
tft.addValue(79);
tft.addValue(83);
tft.addValue(89);
tft.addValue(97);
System.out.println(“Static test: first few prime numbers:”);
tft.printInOrder();
tft.deleteValue(37);
System.out.println(“\nWithout 37:”);
tft.printInOrder();
tft.deleteValue(73);
System.out.println(“\nWithout 73:”);
tft.printInOrder();
tft.deleteValue(97);
System.out.println(“\nWithout 97:”);
tft.printInOrder();
executeIntCase(100, 20, true);
executeIntCase(1000, 200, true);
executeIntCase(10000, 2000, true);
executeIntCase(100000, 20000, true);
executeIntCase(1000000, 200000, true);
executeIntCase(10000000, 2000000, true);
}
}
Trees
COP3503 COMPUTER SCIENCE II
DR. MATTHEW B. GERBER
PORTIONS FROM SEAN SZUMLANSKI, MICHAEL MCALPIN, AND
WIKIPEDIA
Review: Binary Search Trees
A binary search tree is a tree in which:
◦ Each node has at most two children
◦ Each node has at least the following data elements:
◦ A parent pointer (NULL if the node is the root)
◦ A left child pointer (NULL if the node has no left child)
◦ A right child pointer (NULL if the node has no right child)
◦ An indexing key
◦ The insertion and deletion behaviors guarantee that:
◦ If node 𝑦 is the left child of node 𝑥, or any descendant of the left child of 𝑥, then 𝑦. 𝑘𝑒𝑦 ≤ 𝑥. 𝑘𝑒𝑦
◦ If node 𝑦 is the right child of node 𝑥, or any descendant of the right child of 𝑥, then 𝑦. 𝑘𝑒𝑦 ≥ 𝑥. 𝑘𝑒𝑦
Complexity of Binary Search Trees
All basic operations on BSTs take place in 𝒪 ℎ
time, where ℎ is the height of the tree
l
◦ In a well-balanced BST, this is 𝒪(log 𝑛) …
l
l
1
r
l
2
r
3
r
l
4
r
5
r
l
l
7
6
r
r
l
l
9
8
r
r
Complexity of Binary Search Trees
All basic operations on BSTs take place in 𝒪 ℎ
time, where ℎ is the height of the tree
l
◦ In a well-balanced BST, this is 𝒪(log 𝑛) …
◦ …but in a poorly-balanced one, this can
degenerate toward 𝒪(𝑛)
l
l
l
l
2
1
r
r
3
r
4
r
5
r
l
6
r
l
7
r
l
8
r
l
9
r
Searching the Tree
◦ Start at the root
◦ Look at the node we’re at
◦ If we’ve found our key, stop
◦ If our key is less than the node we’re at, go left
◦ Otherwise, go right
◦ Keep doing this until we find our key
◦ If we ever hit null instead of our key,
l 1 r
our key isn’t in the tree
◦ Can do this recursively or iteratively
l
2
l
l
r
3
r
l
4
r
5
r
l
l
7
6
r
r
l
l
9
8
r
r
Searching the Tree: Recursive
bst bstSearch(bst x, key k) {
if(x == null) {
return null;
}
if(k == x.key) {
return x;
}
l
l
l
1
r
if(k < x.key) { return bstSearch(x.left, k) l } 2 return bstSearch(x.right, k) } r 3 r l 4 r 5 r l l 7 6 r r l l 9 8 r r Searching the Tree: Iterative bst bstSearch(bst x, key k) { while(true) { l if(x == null) { return null; } if(k == x.key) { return x; } if(k < x.key) { x = x.left; } x = x.right; } // while } // bstSearch l l 1 r l 2 r 3 r l 4 r 5 r l l 7 6 r r l l 9 8 r r Inserting ◦ Start at the root ◦ Look at the node we’re at ◦ If it’s null, stop and insert the new node there ◦ If our key is less than the node we’re at, go left ◦ Otherwise, go right ◦ Keep doing this until we find null l l l 1 r l 2 r 3 r l 4 r 5 r l l 7 6 r r l l 9 8 r r Inserting bstInsert(var bst t, bstnode n) { bst x = t, y = null; l if(t == null) { t = n; return; } while(x != null) { y = x; if(n.key < x.key) { x = x.left; } else { x = x.right; } } // while n.parent = y; if(n.key < y.key) { y.left = n } else { y.right = n } } // bstSearch l l 1 r l 2 r 3 r l 4 r 5 r l l 7 6 r r l l 9 8 r r Deleting ◦ If the node has no children, easy ◦ If the node only has one child, promote it ◦ If the node has two children… l ◦ Find either its minimum right descendant or maximum left descendant ◦ That descendant has at most one child – do you see why? ◦ Move the descendant to where the deleted node was ◦ Promote the descendant’s child if it had one l l 1 r ◦ The idea is straightforward, it’s cleaning up l the links that takes all the effort 2 r 3 r l 4 r 5 r l l 7 6 r r l l 9 8 r r Deleting // Replace node dest with node src. // Handles changing parenthood of src, // ignores children of dest. // Handles the case where src is null. l 5 r bstRepl(var bst root, bst dest, bst src) { if(dest = root) { root = src; } else if(dest.parent.right = dest) { dest.parent.right = src; } else { dest.parent.left = src; } if(src != null) { src.parent = dest.parent; } } l l 1 r l 2 r 3 r l 4 r l l 7 6 r r l l 9 8 r r Deleting // Has src adopt the children of dest. bstAdopt(bst dest, bst src) { l 5 r src.left = dest.left; l if(src.left != null) { src.left.parent = src; } src.right = dest.right; if(src.right != null) { src.right.parent = src; } } l 1 r l 2 r 3 r l 4 r l l 7 6 r r l l 9 8 r r Deleting bstDel(var bst root, bst n) { if(n.left == null) { bstRepl(root, n, n.right); } else if (n.right == null) { bstRepl(root, n, n.left); } else { bst minRight = bstMin(n.right); bstRepl(root, minRight, minRight.right); bstRepl(root, n, minRight); bstAdopt(n, minRight); } } l l l 1 r l 2 r 3 r l 4 r 5 r l l 7 6 r r l l 9 8 r r Restoring the Balance: AVL Trees ◦ The balance factor of a node in a BST is the difference between the height of its left subtree and the height of its right subtree ◦ In an AVL tree, the balance of any node must have an absolute value of at most 1 l 5 r 0 l 3 r -1 l 1 r +1 l 2 r 0 l 4 r 0 l 7 r +1 l 6 r 0 l 9 r -1 l 8 r 0 Restoring the Balance: AVL Trees ◦ The balance factor of a node in a BST is the difference between the height of its left subtree and the height of its right subtree ◦ In an AVL tree, the balance of any node must have an absolute value of at most 1 ◦ If the tree gets imbalanced… l 5 r 0 l 3 r -2 l 1 r +2 l 4 r 0 l 2 r +1 l 2 r 0 l 7 r +1 l 6 r 0 l 9 r -1 l 8 r 0 Restoring the Balance: AVL Trees ◦ The balance factor of a node in a BST is the difference between the height of its left subtree and the height of its right subtree ◦ In an AVL tree, the balance of any node must have an absolute value of at most 1 ◦ If the tree gets imbalanced… ◦ We cure it by rotating l 5 r 0 l 3 r -2 l 1 r +2 l 4 r 0 l 2 r +1 l 2 r 0 l 7 r +1 l 6 r 0 l 9 r -1 l 8 r 0 Restoring the Balance: AVL Trees ◦ The balance factor of a node in a BST is the difference between the height of its left subtree and the height of its right subtree ◦ In an AVL tree, the balance of any node must have an absolute value of at most 1 ◦ If the tree gets imbalanced… ◦ We cure it by rotating l 5 r 0 l 3 r -1 l l 1 r 0 2 r 0 l 4 r 0 l 2 r 0 l 7 r +1 l 6 r 0 l 9 r -1 l 8 r 0 Restoring the Balance: AVL Trees ◦ The balance factor of a node in a BST is the difference between the height of its left subtree and the height of its right subtree ◦ In an AVL tree, the balance of any node must have an absolute value of at most 1 ◦ If the tree gets imbalanced… ◦ We cure it by rotating ◦ This keeps the tree well-balanced l ◦ So all basic operations are 𝒪(log 𝑛) l 1 r 0 l 5 r 0 l 3 r -1 2 r 0 l 4 r 0 l 2 r 0 l 7 r +1 l 6 r 0 l 9 r -1 l 8 r 0 Restoring the Balance: AVL Trees ◦ The balance factor of a node in a BST is the difference between the height of its left subtree and the height of its right subtree l 5 r 0 ◦ In an AVL tree, the balance of any node must have an absolute value of at most 1 l 3 r -1 l 7 r +1 ◦ If the tree gets imbalanced… ◦ We cure it by rotating ◦ This keeps the tree well-balanced l 2 r 0 l 4 r 0 l 6 r 0 l 9 r -1 ◦ So all basic operations are 𝒪(log 𝑛) ◦ And for any given rotation, we’ll have l 1 r 0 l 8 r 0 l 2 r 0 to rotate at most once per level… ◦ So that’s also 𝒪(log 𝑛) More Trees COP3503 COMPUTER SCIENCE II DR. MATTHEW B. GERBER PORTIONS FROM SEAN SZUMLANSKI, MICHAEL MCALPIN, AND WIKIPEDIA 2-4 Trees A 2-4 tree (or 2-3-4 tree) is a tree in which each node is one of the following: ◦ A 2-node with one data element (and associated key) and two children ◦ A 3-node with two data elements and three children ◦ A 4-node with three data elements and four children ◦ A leaf with one, two or three data elements, but no children The insertion and deletion behaviors guarantee that: ◦ The 2-3-4 structure of each node is maintained ◦ All leaves are at the same depth ◦ Data elements are sorted (more about this on the next slide) 2-3-4 Trees and Data Order ◦ 2-nodes work just like ordinary BST nodes: descendants to their left must be lower, to their right must be higher ◦ (Or equal, but we’re going to require inequality to keep things simple at the moment) 𝒗 𝒗 2-3-4 Trees and Data Order ◦ 2-nodes work just like ordinary BST nodes: descendants to their left must be lower, to their right must be higher 𝒗 𝒗 < 𝒗𝟏 (𝒗𝟏 , 𝒗𝟐 ) > 𝒗𝟐
2-3-4 Trees and Data Order
◦ 2-nodes work just like ordinary BST nodes:
descendants to their left must be lower, to their
right must be higher
𝒗
𝒗
𝒗𝟏 𝒗𝟐
◦ Nodes to the left of their left value and the right of their
right value work in the obvious fashion like BST descendants
◦ Middle-child descendants must have values falling in the
interval between the left and right values of the 3-node
< 𝒗𝟏 (𝒗𝟏 , 𝒗𝟐 ) > 𝒗𝟐
◦ And 4-nodes…
𝒗𝟏 𝒗𝟐 𝒗𝟑
◦ …simply add another interval
< 𝒗𝟏 (𝒗𝟏 , 𝒗𝟐 ) (𝒗𝟐 , 𝒗𝟑 ) > 𝒗𝟑
2-3-4 Tree Example
◦ Here we see an example of a 2-3-4 tree
◦ Note that they can be unbalanced
◦ Just not very
◦ Searching remains 𝒪(log 𝑛) because there are a
constant number of permutations at each node
30 70
◦ If we allowed an arbitrary number of children and values,
we’d lose this property – do you see why?
20
3
50
25
40
45
80 90 95
60
75
85
93
96
97
99
2-3-4 Tree Example
◦ Here we see an example of a 2-3-4 tree
◦ Note that they can be unbalanced
◦ Just not very
◦ Searching remains 𝒪(log 𝑛) because there are a
constant number of permutations at each node
30 70
◦ If we allowed an arbitrary number of children and values,
we’d lose this property – do you see why?
◦ Inserting into the tree is easy when we’re only
dealing with 2-nodes and 3-nodes. Let’s try
inserting 29.
20
3
50
25
40
45
80 90 95
60
75
85
93
96
97
99
2-3-4 Tree Example
◦ Here we see an example of a 2-3-4 tree
◦ Note that they can be unbalanced
◦ Just not very
◦ Searching remains 𝒪(log 𝑛) because there are a
constant number of permutations at each node
30 70
◦ If we allowed an arbitrary number of children and values,
we’d lose this property – do you see why?
◦ Inserting into the tree is easy when we’re only
dealing with 2-nodes and 3-nodes. Let’s try
inserting 29.
20
3
50
25
40
45
80 90 95
60
75
85
93
96
97
99
2-3-4 Tree Example
◦ Here we see an example of a 2-3-4 tree
◦ Note that they can be unbalanced
◦ Just not very
◦ Searching remains 𝒪(log 𝑛) because there are a
constant number of permutations at each node
30 70
◦ If we allowed an arbitrary number of children and values,
we’d lose this property – do you see why?
◦ Inserting into the tree is easy when we’re only
dealing with 2-nodes and 3-nodes. Let’s try
inserting 29.
20
3
25
50
29
40
45
80 90 95
60
75
85
93
96
97
99
2-3-4 Tree Example
◦ Here we see an example of a 2-3-4 tree
◦ Note that they can be unbalanced
◦ Just not very
◦ Searching remains 𝒪(log 𝑛) because there are a
constant number of permutations at each node
30 70
◦ If we allowed an arbitrary number of children and values,
we’d lose this property – do you see why?
◦ Inserting into the tree is easy when we’re only
dealing with 2-nodes and 3-nodes. Let’s try
inserting 29.
◦ And 54.
20
3
25
50
29
40
45
80 90 95
60
75
85
93
96
97
99
2-3-4 Tree Example
◦ Here we see an example of a 2-3-4 tree
◦ Note that they can be unbalanced
◦ Just not very
◦ Searching remains 𝒪(log 𝑛) because there are a
constant number of permutations at each node
30 70
◦ If we allowed an arbitrary number of children and values,
we’d lose this property – do you see why?
◦ Inserting into the tree is easy when we’re only
dealing with 2-nodes and 3-nodes. Let’s try
inserting 29.
◦ And 54.
20
3
25
50
29
40
45
80 90 95
60
75
85
93
96
97
99
2-3-4 Tree Example
◦ Here we see an example of a 2-3-4 tree
◦ Note that they can be unbalanced
◦ Just not very
◦ Searching remains 𝒪(log 𝑛) because there are a
constant number of permutations at each node
30 70
◦ If we allowed an arbitrary number of children and values,
we’d lose this property – do you see why?
◦ Inserting into the tree is easy when we’re only
dealing with 2-nodes and 3-nodes. Let’s try
inserting 29.
◦ And 54.
20
3
25
50
29
40
45
80 90 95
54
60
75
85
93
96
97
99
2-3-4 Tree Example
◦ Here we see an example of a 2-3-4 tree
◦ Note that they can be unbalanced
◦ Just not very
◦ Searching remains 𝒪(log 𝑛) because there are a
constant number of permutations at each node
30 70
◦ If we allowed an arbitrary number of children and values,
we’d lose this property – do you see why?
◦ Inserting into the tree is easy when we’re only
dealing with 2-nodes and 3-nodes. Let’s try
inserting 29.
◦ And 54.
◦ So far so good. But what about inserting 98?
20
3
25
50
29
40
45
80 90 95
54
60
75
85
93
96
97
99
2-3-4 Tree Example
◦ So far so good. But what about inserting 98?
◦ We can do this by splitting up the node. But the
trick is we don’t just split up the leaf.
30 70
20
3
25
50
29
40
45
80 90 95
54
60
75
85
93
96
97
99
2-3-4 Tree Example
◦ So far so good. But what about inserting 98?
◦ We can do this by splitting up the node. But the
trick is we don’t just split up the leaf.
◦ On our way down to the leaf we want to insert
in, whenever we encounter a 4-node, we split it.
30 70
20
3
25
50
29
40
45
80 90 95
54
60
75
85
93
96
97
99
2-3-4 Tree Example
◦ So far so good. But what about inserting 98?
◦ We can do this by splitting up the node. But the
trick is we don’t just split up the leaf.
◦ On our way down to the leaf we want to insert
in, whenever we encounter a 4-node, we split it.
30 70 90
◦ Move its middle node up to the parent…
20
3
25
50
29
40
45
80
54
60
75
95
85
93
96
97
99
2-3-4 Tree Example
◦ So far so good. But what about inserting 98?
◦ We can do this by splitting up the node. But the
trick is we don’t just split up the leaf.
◦ On our way down to the leaf we want to insert
in, whenever we encounter a 4-node, we split it.
30 70 90
◦ Move its middle node up to the parent…
◦ …and split it into two 2-nodes.
20
3
25
50
29
40
45
95
80
54
60
75
85
93
96
97
99
2-3-4 Tree Example
◦ So far so good. But what about inserting 98?
◦ We can do this by splitting up the node. But the
trick is we don’t just split up the leaf.
◦ On our way down to the leaf we want to insert
in, whenever we encounter a 4-node, we split it.
30 70 90
◦ Move its middle node up to the parent…
◦ …and split it into two 2-nodes.
◦ By always doing this when we hit a 4-node on
the way down when inserting, we make sure we
always have the ability to split the nodes below.
20
3
25
50
29
40
45
95
80
54
60
75
85
93
96
97
99
2-3-4 Tree Example
◦ So far so good. But what about inserting 98?
◦ We can do this by splitting up the node. But the
trick is we don’t just split up the leaf.
◦ On our way down to the leaf we want to insert
in, whenever we encounter a 4-node, we split it.
30 70 90
◦ Move its middle node up to the parent…
◦ …and split it into two 2-nodes.
◦ By always doing this when we hit a 4-node on
the way down when inserting, we make sure we
always have the ability to split the nodes below.
20
3
25
50
29
40
45
95 97
80
54
60
75
85
93
96
99
2-3-4 Tree Example
◦ So far so good. But what about inserting 98?
◦ We can do this by splitting up the node. But the
trick is we don’t just split up the leaf.
◦ On our way down to the leaf we want to insert
in, whenever we encounter a 4-node, we split it.
30 70 90
◦ Move its middle node up to the parent…
◦ …and split it into two 2-nodes.
◦ By always doing this when we hit a 4-node on
the way down when inserting, we make sure we
always have the ability to split the nodes below.
20
3
25
50
29
40
45
95 97
80
54
60
75
85
93
96
99
2-3-4 Tree Example
◦ So far so good. But what about inserting 98?
◦ We can do this by splitting up the node. But the
trick is we don’t just split up the leaf.
◦ On our way down to the leaf we want to insert
in, whenever we encounter a 4-node, we split it.
30 70 90
◦ Move its middle node up to the parent…
◦ …and split it into two 2-nodes.
◦ By always doing this when we hit a 4-node on
the way down when inserting, we make sure we
always have the ability to split the nodes below.
◦ So by the time we get to the leaf, we can always insert.
20
3
25
50
29
40
45
95 97
80
54
60
75
85
93
96
98
99
2-3-4 Tree Example
◦ So far so good. But what about inserting 98?
◦ We can do this by splitting up the node. But the
trick is we don’t just split up the leaf.
◦ On our way down to the leaf we want to insert
in, whenever we encounter a 4-node, we split it.
30 70 90
◦ Move its middle node up to the parent…
◦ …and split it into two 2-nodes.
◦ By always doing this when we hit a 4-node on
the way down when inserting, we make sure we
always have the ability to split the nodes below.
◦ So by the time we get to the leaf, we can always insert.
◦ The tree height grows when we have to split the
root…
20
3
25
50
29
40
45
95 97
80
54
60
75
85
93
96
98
99
2-3-4 Tree Example
◦ So far so good. But what about inserting 98?
◦ We can do this by splitting up the node. But the
trick is we don’t just split up the leaf.
◦ On our way down to the leaf we want to insert
in, whenever we encounter a 4-node, we split it.
70
30
◦ Move its middle node up to the parent…
◦ …and split it into two 2-nodes.
◦ By always doing this when we hit a 4-node on
the way down when inserting, we make sure we
always have the ability to split the nodes below.
◦ So by the time we get to the leaf, we can always insert.
◦ The tree height grows when we have to split the
root…
◦ …which always happens when we insert with a 4-node root.
20
3
25
90
50
29
40
45
95 97
80
54
60
75
85
93
96
98
99
Deletion
◦ Whenever inserting into a 2-3-4 tree, we make
sure we don’t have any 4-nodes between
ourselves and the root
◦ That way we always preserve the ability to promote the
center node
◦ Whenever deleting from a 2-3-4 tree, we make
sure we don’t have any 2-nodes between
ourselves and the root
◦ That way we always preserve the ability to promote the
value’s immediate predecessor or successor without
unbalancing the tree
Deletion
◦ Whenever inserting into a 2-3-4 tree, we make
sure we don’t have any 4-nodes between
ourselves and the root
70
◦ That way we always preserve the ability to promote the
center node
30
◦ Whenever deleting from a 2-3-4 tree, we make
sure we don’t have any 2-nodes between
ourselves and the root
◦ That way we always preserve the ability to promote the
value’s immediate predecessor or successor without
unbalancing the tree
◦ If the root is a 2-node and both its children are
2-nodes…
20
3
25
90
50
29
40
45
95 97
80
54
60
75
85
93
96
98
99
Deletion
◦ Whenever inserting into a 2-3-4 tree, we make
sure we don’t have any 4-nodes between
ourselves and the root
◦ That way we always preserve the ability to promote the
center node
30 70 90
◦ Whenever deleting from a 2-3-4 tree, we make
sure we don’t have any 2-nodes between
ourselves and the root
◦ That way we always preserve the ability to promote the
value’s immediate predecessor or successor without
unbalancing the tree
◦ If the root is a 2-node and both its children are
2-nodes…
◦ …fuse them back into a 4-node
20
3
25
50
29
40
45
95 97
80
54
60
75
85
93
96
98
99
Deletion
◦ Whenever deleting from a 2-3-4 tree, we make
sure we don’t have any 2-nodes between
ourselves and the root
◦ That way we always preserve the ability to promote the
value’s immediate predecessor or successor without
unbalancing the tree
30 70 90
◦ If the root is a 2-node and both its children are
2-nodes…
20
50
95 97
80
◦ …fuse them back into a 4-node
◦ If a sibling is a 3-node or 4-node…
3
25
29
40
45
54
60
75
85
93
96
98
99
Deletion
◦ Whenever deleting from a 2-3-4 tree, we make
sure we don’t have any 2-nodes between
ourselves and the root
◦ That way we always preserve the ability to promote the
value’s immediate predecessor or successor without
unbalancing the tree
30 70
◦ If the root is a 2-node and both its children are
2-nodes…
20
-80 90
50
95 97
◦ …fuse them back into a 4-node
◦ If a sibling is a 3-node or 4-node…
◦ Rotate the parent’s facing value down to make our 2-node a
3-node…
3
25
29
40
45
54
60
75
85
93
96
98
99
Deletion
◦ Whenever deleting from a 2-3-4 tree, we make
sure we don’t have any 2-nodes between
ourselves and the root
◦ That way we always preserve the ability to promote the
value’s immediate predecessor or successor without
unbalancing the tree
30 70 95
◦ If the root is a 2-node and both its children are
2-nodes…
20
80 90
50
97
◦ …fuse them back into a 4-node
◦ If a sibling is a 3-node or 4-node…
◦ Rotate the parent’s facing value down to make our 2-node a
3-node…
◦ Rotate the sibling’s facing value up into the parent…
3
25
29
40
45
54
60
75
85
93
96
98
99
Deletion
◦ Whenever deleting from a 2-3-4 tree, we make
sure we don’t have any 2-nodes between
ourselves and the root
◦ That way we always preserve the ability to promote the
value’s immediate predecessor or successor without
unbalancing the tree
30 70 95
◦ If the root is a 2-node and both its children are
2-nodes…
20
80 90
50
97
◦ …fuse them back into a 4-node
◦ If a sibling is a 3-node or 4-node…
◦ Rotate the parent’s facing value down to make our 2-node a
3-node…
◦ Rotate the sibling’s facing value up into the parent…
◦ And adopt the sibling’s facing descendants
3
25
29
40
45
54
60
75
85
93
96
98
99
Deletion
◦ If the root is a 2-node and both its children are
2-nodes…
◦ …fuse them back into a 4-node
◦ If a sibling is a 3-node or 4-node…
30 70 95
◦ Rotate the parent’s facing value down to make our 2-node a
3-node…
◦ Rotate the sibling’s facing value up into the parent…
◦ And adopt the sibling’s facing descendants
◦ If there’s no 3-node or 4-node sibling available…
20
3
25
80 90
50
29
40
45
54
60
75
85
97
93
96
98
99
Deletion
◦ If the root is a 2-node and both its children are
2-nodes…
◦ …fuse them back into a 4-node
◦ If a sibling is a 3-node or 4-node…
70 95
◦ Rotate the parent’s facing value down to make our 2-node a
3-node…
◦ Rotate the sibling’s facing value up into the parent…
◦ And adopt the sibling’s facing descendants
◦ If there’s no 3-node or 4-node sibling available…
◦ Fuse with the parent’s facing data element to create a 4node with the sibling 2-node
20 30 50
3
25
29
40
80 90
45
54
60
75
85
97
93
96
98
99
Deletion
◦ If the root is a 2-node and both its children are
2-nodes…
◦ …fuse them back into a 4-node
◦ If a sibling is a 3-node or 4-node…
70 95
◦ Rotate the parent’s facing value down to make our 2-node a
3-node…
◦ Rotate the sibling’s facing value up into the parent…
◦ And adopt the sibling’s facing descendants
◦ If there’s no 3-node or 4-node sibling available…
◦ Fuse with the parent’s facing data element to create a 4node with the sibling 2-node
◦ (Exact reversal of the split action!)
20 30 50
3
25
29
40
80 90
45
54
60
75
85
97
93
96
98
99
Deletion
◦ If the root is a 2-node and both its children are
2-nodes…
◦ …fuse them back into a 4-node
◦ If a sibling is a 3-node or 4-node…
70 95
◦ Rotate the parent’s facing value down to make our 2-node a
3-node…
◦ Rotate the sibling’s facing value up into the parent…
◦ And adopt the sibling’s facing descendants
◦ If there’s no 3-node or 4-node sibling available…
◦ Fuse with the parent’s facing data element to create a 4node with the sibling 2-node
◦ (Exact reversal of the split action!)
◦ With all that done, we can finally delete
directly…
20 30 50
3
25
29
40
80 90
45
54
60
75
85
97
93
96
98
99
Deletion
◦ If the root is a 2-node and both its children are
2-nodes…
◦ …fuse them back into a 4-node
◦ If a sibling is a 3-node or 4-node…
70 95
◦ Rotate the parent’s facing value down to make our 2-node a
3-node…
◦ Rotate the sibling’s facing value up into the parent…
◦ And adopt the sibling’s facing descendants
◦ If there’s no 3-node or 4-node sibling available…
◦ Fuse with the parent’s facing data element to create a 4node with the sibling 2-node
◦ (Exact reversal of the split action!)
◦ With all that done, we can finally delete
directly…
◦ …or indirectly
20 30 50
3
25
29
40
80 90
45
54
60
75
85
97
93
96
98
99
Deletion
◦ If the root is a 2-node and both its children are
2-nodes…
◦ …fuse them back into a 4-node
◦ If a sibling is a 3-node or 4-node…
70 95
◦ Rotate the parent’s facing value down to make our 2-node a
3-node…
◦ Rotate the sibling’s facing value up into the parent…
◦ And adopt the sibling’s facing descendants
◦ If there’s no 3-node or 4-node sibling available…
◦ Fuse with the parent’s facing data element to create a 4node with the sibling 2-node
◦ (Exact reversal of the split action!)
◦ With all that done, we can finally delete
directly…
◦ …or indirectly
20 29 50
3
25
40
80 90
45
54
60
75
85
97
93
96
98
99