Java Reference
In-Depth Information
Note:
A 2-3 tree is a general search tree whose interior nodes must have either two or three
children and whose leaves occur on the same level. A 2-3 tree is completely balanced.
FIGURE 27-11
(a) A 2-node; (b) a 3-node
(a)
(b)
s
l
s
s
s
s
s
l
l
27.14
If we had a 2-3 tree, such as the one in Figure 27-12, how would we search it? Notice that each
2-node adheres to the ordering of a binary search tree. The 3-node leaf <35 40> contains values that
are between the values in its parent. Knowing this, we can search for the 40, for example, by first
comparing 40 with the root value 60. We then move to 60's left subtree and compare 40 with the
values in the root of this subtree. Since 40 lies between 20 and 50, it would occur in the middle sub-
tree, if it appears at all. While searching the middle subtree, we compare 40 with 35 and then finally
with 40.
FIGURE 27-12
A 2-3 tree
60
20 50
80
10
35 40
55
70
90
The search algorithm is an extension of the search algorithm for a binary search tree:
Algorithm
search23Tree(23Tree, desiredObject)
//
Searches a 2-3 tree for a given object.
//
Returns true if the object is found.
if
(23Tree
is empty
)
return false
else if
(desiredObject
is in the root of
23Tree)
return true
else if
(
the root of
23Tree
contains two entries
)
{
if
(desiredObject
<
smaller object in the root
)
return
search23Tree(
left subtree of
23Tree, desiredObject)
