Java Reference
In-Depth Information
if
(comparison == 0)
{
result = rootNode.getData();
rootNode.setData(newEntry);
}
else if
(comparison < 0)
{
if
(rootNode.hasLeftChild())
{
BinaryNodeInterface<T> leftChild = rootNode.getLeftChild();
result = addEntry(leftChild, newEntry);
rootNode.setLeftChild(rebalance(leftChild));
}
else
rootNode.setLeftChild(
new
BinaryNode<T>(newEntry));
}
else
{
assert
comparison > 0;
if
(rootNode.hasRightChild())
{
BinaryNodeInterface<T> rightChild = rootNode.getRightChild();
result = addEntry(rightChild, newEntry);
rootNode.setRightChild(rebalance(rightChild));
}
else
rootNode.setRightChild(
new
BinaryNode<T>(newEntry));
}
// end if
return
result;
}
// end addEntry
Although
rebalance
is called several times during the course of executing these methods, a
rebalancing of the tree occurs at most once. Most calls to
rebalance
simply check whether a rebal-
ancing is needed.
As attractive as an AVL tree might seem, better search trees have been developed, as you will
now see.
27.13
A
2-3 tree
is a general search tree whose interior nodes must have either two or three children.
A
2-node
contains one data item
s
and has two children, like the nodes in a binary search tree.
This data
s
is greater than any data in the node's left subtree and less than any data in the right
subtree. That is, the data in the node's left subtree is less than
s
, and any data in the right subtree
is greater than
s
, as Figure 27-11a shows.
A
3-node
contains two data items,
s
and
l,
and has three children. Data that is less than the
smaller data item
s
occurs in the node's left subtree. Data that is greater than the larger data item
l
occurs in the node's right subtree. Data that is between
s
and
l
occurs in the node's middle subtree.
Figure 27-11b shows a typical 3-node.
Because it can contain 3-nodes, a 2-3 tree tends to be shorter than a binary search tree. To make
the 2-3 tree balanced, we require that all leaves occur on the same level. Thus, a 2-3 tree is com-
pletely balanced.
VideoNote
2-3 trees
