24Trees.txt

(2,4) Trees

9

2  5  7

10  14

Multi-Way Search Tree ( 9.4.1)

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

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 Inorder Traversal

Multi-Way Searching

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

2   6   8
2
6

4

11    24
8
12

15
10

1

3

5

7

9

11

13

 2004 Goodrich, Tamassia

(2,4) Trees

27    32
18

14

30
16

15

17

19

3

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 < k < ki (i = 2, ..., d  1): we continue the search in child vi
(cid:132) k > kd1: we continue the search in child vd
Reaching an external node terminates the search unsuccessfully
Example: search for 30

2   6   8

11    24

15

27    32

30

 2004 Goodrich, Tamassia

(2,4) Trees

4

(2,4) Trees ( 9.4.2)

Height of a (2,4) Tree

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

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) Since there are at least 2i items at depth i = 0, ... , h  1 and no 

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

items

items at depth h, we have

n  1 + 2 + 4 + ... + 2h1 = 2h  1

0

1

1

2

h1

2h1

h

0

 2004 Goodrich, Tamassia

(2,4) Trees

5

 2004 Goodrich, Tamassia

(2,4) Trees

6

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 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

u

15   24

v

u

12

18

27  30  32 35

12

18

v1 v2 v3 v4 v5

15 24  32
v'
27  30

v"

35

v1 v2 v3

v4

v5

 2004 Goodrich, Tamassia

(2,4) Trees

7

 2004 Goodrich, Tamassia

(2,4) Trees

8

Analysis of Insertion

Deletion

Algorithm insert(k, o)

1. We search for key k to locate the 

insertion node v

2. We add the new entry (k, o) at node v

3. while overflow(v)

if isRoot(v)

create a new empty root above v

v  split(v)

Let T be a (2,4) tree 
with n items
(cid:132) Tree T has O(log n) 

height

(cid:132) Step 1 takes O(log n)
time because we visit 
O(log n) nodes

(cid:132) Step 2 takes O(1) time
(cid:132) Step 3 takes O(log n)

time because each split 
takes O(1) time and we 
perform O(log n) splits
Thus, an insertion in a 
(2,4) tree takes O(log n)
time

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

 2004 Goodrich, Tamassia

(2,4) Trees

9

 2004 Goodrich, Tamassia

(2,4) Trees

10

Underflow and Fusion

Deleting an entry from a node v may cause an underflow, where 
node v becomes a 1-node with one child and no keys
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

10  14

v'

Underflow and Transfer

To handle an underflow at node v with parent u, we consider 
two cases
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

 2004 Goodrich, Tamassia

(2,4) Trees

11

 2004 Goodrich, Tamassia

(2,4) Trees

v

9

12

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

Implementing a Dictionary

Comparison of efficient dictionary implementations

Search

Insert

Delete

Notes

Hash 
Table

1

expected

1

expected

1

expected

no ordered dictionary 
methods
simple to implement

Skip List

log n
high prob.

log n
high prob.

log n
high prob.

randomized insertion
simple to implement

(2,4) 
Tree

log n
worst-case

log n
worst-case

log n
worst-case

complex to implement

 2004 Goodrich, Tamassia

(2,4) Trees

13

 2004 Goodrich, Tamassia

(2,4) Trees

14