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
