2-4trees1.txt

(2,4) Trees

(2,4) Trees

9

2  5  7

10  14

Multi-Way Search Tree

2   6   8

11    24

15

27    32

30

 2004 Goodrich, Tamassia

(2,4) Trees

1

 2004 Goodrich, Tamassia

(2,4) Trees

2

Multi-Way Search Tree

A multi-way search tree is an ordered tree such 
that 
(cid:132) Each internal node has at least two children and 

stores  d 1 key-element items (ki, oi), where d is the 
number of children 

(cid:132) For a node with children v1 v2 ... vd storing  keys             

k1 k2 ... kd1:
(cid:138) keys in the subtree of v1 are less than k1
(cid:138) keys in the subtree of vi are between ki1 and ki (i = 2, ..., d-1)
(cid:138) keys in the subtree of vd are greater than kd1

(cid:132) The leaves store no items and serve as placeholders

Multi-Way Inorder Traversal

We can extend the notion of inorder traversal from binary trees 
to multi-way search trees
Namely, we visit item (ki, oi) of node v between the recursive 
traversals of the subtrees of v rooted at children vi and vi + 1
An inorder traversal of a multi-way search tree visits the keys in 
increasing order

 2004 Goodrich, Tamassia

(2,4) Trees

3

 2004 Goodrich, Tamassia

(2,4) Trees

2   6   8
2
6

4

11    24
12
8

15
10

1

3

5

7

9

11

13

27    32
18

14

30
16

15

17

19

4

Multi-Way Searching

Multi-Way Searching

Searching for 

30:

2   6   8

11    24

15

27    32

30

Searching for 

30:

2   6   8

11    24

15

27    32

30

 2004 Goodrich, Tamassia

(2,4) Trees

5

 2004 Goodrich, Tamassia

(2,4) Trees

6

1

(2,4) Trees

Multi-Way Searching

Multi-Way Searching

Searching for 

30:

2   6   8

11    24

15

27    32

30

Searching for 

30:

2   6   8

11    24

15

27    32

30

 2004 Goodrich, Tamassia

(2,4) Trees

7

 2004 Goodrich, Tamassia

(2,4) Trees

8

Multi-Way Searching

(2,4) Trees

Similar to search in a binary search tree
A each internal node with children v1 v2 ... vd and keys 
k1 k2 ... kd1
(cid:132) k = ki (i = 1, ..., d  1): the search terminates successfully
(cid:132) k < k1: we continue the search in child v1
(cid:132) ki1 
(cid:132) k > kd1: we continue the search in child vd
Reaching an external node terminates the search 
unsuccessfully

< k < ki (i = 2, ..., d  1): we continue the search in child vi

A (2,4) tree (also called 2-4 tree or 2-3-4 tree) is a 
multi-way search with the following properties
(cid:132) Node-Size Property: every internal node has at most four 

children

(cid:132) Depth Property: all the external nodes have the same depth
Depending on the number of children, an internal 
node of a (2,4) tree is called a 2-node, 3-node or 4-
node

 2004 Goodrich, Tamassia

(2,4) Trees

9

 2004 Goodrich, Tamassia

(2,4) Trees

10

(2,4) Trees

Height of a (2,4) Tree

10   15   24

2   8

12

18

27    32

Theorem: A (2,4) tree storing n items has height O(log n)
Proof:
(cid:132) Let h be the height of a (2,4) tree with n items
(cid:132) As in proper binary trees, there are at least 2i items at 

depth i: n  2h  1

(cid:132) Thus, h  log (n + 1)
Searching in a (2,4) tree with n items takes O(log n) time

 2004 Goodrich, Tamassia

(2,4) Trees

11

 2004 Goodrich, Tamassia

(2,4) Trees

12

depth

items

0

1
h1

h

1

2
2h1

0

2

(2,4) Trees

Insertion

We insert a new item (k, o) at the parent v of the leaf reached by 
searching for k
(cid:132) We preserve the depth property but 
(cid:132) We may cause an overflow (i.e., node v may become a 5-node)
Example: inserting key 30 causes an overflow

10   15   24

v

2   8

12

18

27   32   35

10   15   24

v

2   8

12

18

27   30 32   35

Overflow and Split

We handle an overflow at a 5-node v with a split 
operation:
(cid:132) let v1 ... v5 be the children of v and  k1 ... k4 be the keys of v
(cid:132) node v is replaced by nodes v' and v"

(cid:138) v' is a 3-node with keys k1 k2 and children v1 v2 v3
(cid:138) v" is a 2-node with key k4 and children v4 v5

(cid:132) key k3  is inserted into the parent u of v (a new root may be 

created)

The overflow may propagate to the parent node u

 2004 Goodrich, Tamassia

(2,4) Trees

13

 2004 Goodrich, Tamassia

(2,4) Trees

14

Overflow and Split

u

15   24

v

12

18

27  30  32 35

12

18

v1 v2 v3 v4 v5

u

15 24  32

v'
27  30

v"

35

v1

v2 v3

v4

v5

Analysis of Insertion
Let T be a (2,4) tree with n items
(cid:132) Tree T has O(log n) height
(cid:132) Finding insertion point takes O(log n) time 

because we visit O(log n) nodes

(cid:132) Inserting the new entry takes O(1) time
(cid:132) Dealing with overflow takes O(log n) time 
because each split takes O(1) time and we 
perform O(log n) splits in the worst case.

Thus, an insertion in a (2,4) tree takes O(log n) time

 2004 Goodrich, Tamassia

(2,4) Trees

15

 2004 Goodrich, Tamassia

(2,4) Trees

16

Exercise

Starting with an empty (2,4) tree, insert 

items with keys 1,2,3,4,5,6,7

Exercise

1

1  2

1 2  3

 2004 Goodrich, Tamassia

(2,4) Trees

17

 2004 Goodrich, Tamassia

(2,4) Trees

18

3

(2,4) Trees

Exercise

Exercise

1

1  2

1 2  3

1

1  2

1 2  3

inserting 4 causes a split:

1  2  3  4

3

3

inserting 4 causes a split:

1  2  3  4

3

3

1  2

4

1  2

4  5

1  2

4

1  2

4  5

 2004 Goodrich, Tamassia

(2,4) Trees

19

 2004 Goodrich, Tamassia

7 causes a split
(2,4) Trees

3

1  2

4 5  6

3  6

4  5

1  2

7

20

Deletion

We reduce deletion of an entry to the case where the item is at the 
node with leaf children
Otherwise, we replace the entry with its inorder successor (or, 
equivalently, with its inorder predecessor) and delete the latter entry
Example: to delete key 24, we replace it with 27 (inorder successor)

10   15   24

2   8

12

18

27   32   35

10   15   27

2   8

12

18

32   35

Underflow

Deleting an entry from a node v may cause an 
underflow, where node v becomes a 1-node with one 
child and no keys

u

9  14

2  5  7

w

10

v

 2004 Goodrich, Tamassia

(2,4) Trees

21

 2004 Goodrich, Tamassia

(2,4) Trees

22

Underflow and Fusion

To handle an underflow at node v with parent u, we 
consider two cases
Case 1: the adjacent siblings of v are 2-nodes
(cid:132) Fusion operation: we merge v with an adjacent sibling w and 

move an entry from u to the merged node v'

(cid:132) After a fusion, the underflow may propagate to the parent u

u

9  14

u

9

2  5  7

w

10

v

2  5  7

v'

10  14

 2004 Goodrich, Tamassia

(2,4) Trees

23

 2004 Goodrich, Tamassia

(2,4) Trees

Underflow and Transfer

Case 2: an adjacent sibling w of v is a 3-node or a 4-
node
(cid:132) Transfer operation:

1.  we move a child of w to v
2.  we move an item from u to v
3.  we move an item from w to u

(cid:132) After a transfer, no underflow occurs

u
4  9

w

6  8

2

v

2

u
4  8

w

6

v

9

24

4

(2,4) Trees

Analysis of Deletion

Let T be a (2,4) tree with n items
(cid:132) Tree T has O(log n) height
In a deletion operation
(cid:132) We visit O(log n) nodes to locate the node from 

which to delete the entry

(cid:132) We handle an underflow with a series of O(log n)

fusions, followed by at most one transfer
(cid:132) Each fusion and transfer takes O(1) time
Thus, deleting an item from a (2,4) tree takes 
O(log n) time

Exercise delete 3,7

3  6

4  5

7

1  2

 2004 Goodrich, Tamassia

(2,4) Trees

25

 2004 Goodrich, Tamassia

(2,4) Trees

26

Exercise delete 3,7

delete 3: 
replace by 4

3  6

4  5

4  6

5

7

7

1  2

1  2

Exercise delete 3,7

delete 3: 
replace by 4

delete 7: 
underflow

7

7

3  6

4  5

4  6

5

4  6

5

1  2

1  2

1  2

 2004 Goodrich, Tamassia

(2,4) Trees

27

 2004 Goodrich, Tamassia

(2,4) Trees

28

Exercise delete 3,7

3  6

4  5

4  6

5

4  6

5

1  2

1  2

1  2

delete 3: 
replace by 4

delete 7: 
underflow

7

7

fusion

4

1  2

5  6 

Complexity comparison

Comparison of hash tables and (2,4) trees

Search

Insert

Delete

Notes

Hash 
Table

(2,4) 
Tree

1

1

1

expected

expected

expected

simple to implement
Requires allocating a 

lot of memory in 
advance

log n
worst-case

log n
worst-case

log n
worst-case

complex to implement
dynamic memory use

 2004 Goodrich, Tamassia

(2,4) Trees

29

 2004 Goodrich, Tamassia

(2,4) Trees

30

5