Contents:
2-3 Trees (p.563ff)
Insertion: First locate the leaf at which the search for the value
to insert would terminate. Insert the value there. If the leaf now
contains only 2 data items, we are done. Else, we split the leaf into two
new leaves, one containing the smallest value, and one containing the
greatest, attaching the new leaves to the parent, and moving the middle data
item to the parent. In case the parent now has 3 data items, we re-do the
above splitting, until we hit the root (whose parent has no data items so
cannot overflow). For code for this, see my code for the
first programming assignment.
Deletion: Find the value to delete in the tree. If it is not in a
leaf, swap it with its inorder successor (which *must* live in a leaf
-- make sure you understand why this is!). Then the value to delete lives
in a leaf. If it is not the only value in that leaf, we may just delete
it. However, if it is the only value in the leaf, we delete it and then
"fix" the resulting tree (since the leaf now contains no data items and as
such is not a valid 2-3 Node). To fix, you either redistribute from the
parent and sibling or merge with a sibling as illustrated on p.580. Again,
for code for this, see my code for the
first programming assignment.
Effeciency: One should note that although a 2-3 tree is not always
guaranteed to be "full" in the sense of a full binary search tree (i.e.,
every node has the maximal number of children and data items possible), it
is guaranteed to be "semi-full", in that one never has a node with children
of different heights, so no linear "branches" can develop. This means that
all table operations can be completed in O(log(n)) time.
Class relationships (Carrano: p.343ff):
The defining property: Each node is either a 2-node or a 3-node. If
it is a 2-node, it has 1 data item and 2 children. If it is a 3-node, it
has 2 data items and 3 children. In any case all of the children must have
the exact same height (which we allow to be zero, in which case the node is
a leaf). In any case, a data item must be greater than all of the data
items in any children to its left, and less than all of the data items in
any children to its right.
For traverse and search pseudo-code, see
Carrano, p.566-567. Here's pseudo-code to extract a range of values:
VisitRange(T, fromKey, toKey)
// Visits each item in T with key between fromKey and toKey
if (T's root is a leaf)
if (fromKey<=T.ldata <=toKey) // visit T.ldata
if (fromKey<=T.rdata <=toKey) // visit T.rdata
else
if (T has 2 items)
if (fromKey < T.ldata)
VisitRange(T.lChild, fromKey, toKey)
if (fromKey<=T.ldata <=toKey) // visit T.ldata
if ((fromKey < T.rdata)&&(toKey > T.ldata))
VisitRange(T.mChild, fromKey, toKey)
if (fromKey<=T.rdata <=toKey) // visit T.rdata
if (toKey > T.rdata)
VisitRange(T.rChild, fromKey, toKey)
else // T has 1 data item
if (fromKey < T.ldata)
VisitRange(T.lChild, fromKey, toKey)
if (fromKey<=T.ldata <=toKey) // visit T.ldata
if (toKey > T.ldata)
VisitRange(T.mChild, fromKey, toKey)
2-3-4 Trees (p.583ff)
The defining property: Each node is either a 2-node, a 3-node, or a
4-node. If
it is a 2-node, it has 1 data item and 2 children. If it is a 3-node, it
has 2 data items and 3 children. If it is a 4-node, it has 3 data items and
4 children. In any case all of the children must have
the exact same height (which we allow to be zero, in which case the node is
a leaf). In any case, a data item must be greater than all of the data
items in any children to its left, and less than all of the data items in
any children to its right.
Traverse and search for 2-3-4 Trees are simple extensions of
the same functions for 2-3 trees, as is Range Extraction. You should
make sure you can write pseudo-code to perform these three functions without
to much heartache.
Insertion: Insertion is
Deletion: Similarly to the deletion from 2-3 trees, we begin by swapping the value to be deleted with its inorder successor if the value doesn't live in a leaf. So we always delete values out of leaves. If the leaf is a 3-node or a 4-node, we can just delete the value and be done. However, if there is a 2-node there, we are in trouble. We circumvent this problem by transforming each 2-node we see on the way from the root to the leaf into a 3 or 4-node, depending on what siblings are available, according to the figures 12-28, 12-29, and 12-30, with the left-to-right arrows being reversed.
[ S L ] \ [L] [S] / | \ ---------\ { \ / } / | \ ---------/ [S] c OR: a [L] a b c / / \ / \ a b b cand 4-nodes as:
[ S M L ] \ [M] / | | \ ----------\ { } / | | \ ----------/ [S] [L] a b c d / / \ / \ a b c d(where the {'s and }'s denote red pointers). Insertion and Deletion in Red-Black trees are inherited from 2-3-4 trees, by converting a red-black tree to 2-3-4, operating there, and converting back. Note that one 2-3-4 tree may have more than one red-black representation, but a given red-black tree has precisely one 2-3-4 tree corresponding to it.
Search and Traverse are exactly the same as for a binary search tree.
Insertion and deletion are implemented similarly to BST's as well. To insert or delete a value in an AVL tree, you first insert or delete it as if the tree was a binary search tree. If the balance condition was not upset, we are done. Otherwise, we work from the leaf we inserted into/deleted from up towards the root, and at each step, if the node is unbalanced (i.e., the left subtree's height is more than one away from the height of the right subtree), we either perform a double or single rotation. For diagrams of the two cases, see figures 12-38 through 12-43, p.595-597. You can see some (unguaranteed and *very* shabby) implementation of AVL trees by me from a couple of years ago for illustration.
class Base { public: void mytype() { cout << "My type is Base" << endl;}; } class Derived : public Base { public: void mytype() { cout << "My type is Derived" << endl;}; }and then you had a sequence of calls like the following:
Derived d; Base *bptr=&d; Derived *dptr=&d; bptr->mytype(); dptr->mytype();then even though the same function was called (d.mytype()), two different functions will be executed, and the computer will print out Base the first time and Derived the second. If we change the definition of mytype() in Base to:
virtual void mytype() {cout << "My type is Base" << endl;};then the compiler will decide which function to execute at run time, deciding according to the type of object that each pointer is pointing to, rather than at compile time, based on what type of object the pointer was declared to be pointing at.
template < class TYPE > class ClassName { ... }Recall the syntax for a template member function:
template[return-type] Specification of the return type. ClassName[return-type] ClassName < TYPE > ::FunctionName( parameters ) { ... }
You should have seen and gotten comfortable with templates in PIC 10B. If you haven't, see me asap.
. .* :: ?: sizeof
= == != < <= => >