2-3 and B-Trees
Section 16.4

m-Way Search Trees

Motivation

By considering search trees of degree greater than 2, we can arrive at tree structures for which insertion and deletion algorithms are simpler than those for AVL trees, yet still have O(logn) complexity.

B-Trees are the de facto standard for organizing large database systems and for external searching and sorting

• When data is too large to fit in main memory, then the number of disk accesses becomes important.
• A disk access is unbelievably expensive compared to a typical computer instruction (mechanical limitations).
• One disk access is worth about 200,000 instructions.
• The number of disk accesses will dominate the running time.

Basically, the idea is records do not all fit in the internal main memory and are stored in a file on disk.
IBM's Virtual Storage Access Method (VSAM) file organization uses B-tree.

In a B-tree an order is used to group the keys of records so that the B-tree will not grow very high. It grows from the bottom (leaf) to outward and upward.

The grouping of keys in each node is used to minimize the disk access time.

The size of the group defines the order of the B-tree.

The keys are used for comparison and can be page numbers in a disk storage system.

Multiway Search Trees

m-Way Search Trees

• A generalization of binary search trees.
• Each node has at most m children.
• If k < m is the number of children, then the node has exactly k-1 keys.
• The tree is ordered.

Definition: A B-Tree of order m is an m-way tree such that

• All leaves are on the same level.
• All internal nodes except the root are constrained to have at most m non-empty children and at least m/2 non-empty children.
• The root has at most m non-empty children.

Online slides for B-Trees if you want more information.
We will focus on a specific B-Tree

2-3 Trees

Figure 16.25 A B-Tree of order 3, and another. (Second example illustrates a 2 node with the second side "empty".)

Remember: External nodes are introduced only for ease of communication. They are not physically represented inside the computer (rather they are references to null)

By convention, assume that no element has key MAXKEY and if only 2-node, dataR.key = MAXKEY

Its single element is kept in dataL, and LeftChild and MiddleChild reference its two children.

<KeyType> in the examples simply indicates that the Object must have a key, i.e, what we will search on. (For example, we shall assume that no element has key MAXKEY and adopt the convention that a 2 node has dataR.key=MAXKEY. In this situation, the 2 nodes single element is kept in data.L, an the LeftChild and MiddleChild point to its children. Its RightChild data member may be assigned any arbitrary value.)

Note, I thought this book had more on 2-3 trees than it did. I am sorry. I have translated the notes and (pseudo) code in these notes from a C++ book (from "Fundamentals of Data Structures in C++", Horowitz, Sahni, Mehta), so if I left pieces in by mistake, try to "read around" them - but please let me know and I will correct it)

Classes

class Two3Node {
public:
private:
   Element dataL, dataR;
   Two3Node LeftChild, MiddleChild, RightChild, parent;

   void display(int i);
   void treeprint(int i);
   int compare(Element x);
   void putIn(Element x, Two3Node node);
}

class Two3 {
private:
   Two3Node root;
   KeyType MAXKEY;

public:
   // Constructor

   boolean insert(Element x);
   boolean delete(Element x);
   Two3Node search(Element x);

   Two3Node findNode(Element x);
   void newRoot(Element x, Two3Node a);
   Element split(Two3Node node, Element x, Two3Node node2, Two3Node node3);
   void treeprint() 
   void display() 
}

public Two3Node search(Element x)
{  // Search the 2-3 tree for an element x.  If the element is not in the tree, then
   // return null.  Otherwise, return a pointer to the node that contains the element.

   for (Two3Node p = root; p;)
      switch(p.compare(x))
      {
	 case 1: p = p.LeftChild; break;
	 case 2: p = p.MiddleChild; break;
	 case 3: p = p.RightChild; break;
	 case 4: return p;
      }
   return null;
}

Insertion:

If insertion in that node puts value into dataR.key,

• children are all external nodes - no problem
  PutIn with subtree null
• only way this could be parent of someone, is if it is during a split ...
  possibly shift old middle reference
  PutIn with a subtree

A sequence of insertions from the start.

Take this as original tree Figure 16.25, insert 44 Figure 16.26, Shows both to see better.

Try this page to get it: How cool and they make you think!

Search for the unique location for indexed key finds that node (say p) full. (i.e., one is at a node with 3 values now)

Splits:

1. create a new node q
   (p is split into p, q, and a median element)
2. q will contain the element with the largest value of the three
3. the element with the smallest will stay in p (the node found)
4. the median element with the median key (and the reference to the new node q) will be inserted into the parent of p putIn

public boolean Two3 insert(Element y)
{
	// Insert the element y into the 2-3 tree only if it does not already contain
       // an element with the key

   Two3Node p;
   Element x = y;
   if (x.key == MAXKEY) return false;    // invalid key
   if (root ==null) { newRoot(x, null); return true;}    // empty 2-3 tree
   p = findNode(x);
   if (p == null) {/*insertionError(); */ return false;}   // key already in 2-3 tree
   for (Two3Node a = null;;)
      if (p.dataR.key == MAXKEY) {   // p is a 2-node
	 p.putIn(x,a);
	 return true;
      }
      else {                         // p is a 3 node
	 Two3Node olda = a;
	 a = new(Two3Node);
	 x = split(p, x, olda, a);
	 if (root == p) {
	    newRoot(x, a);
	    return true;
	 }
	 else p = p.parent();
      }
}

This method makes use of additional methods that you will need to implement: (from "Fundamentals of Data Structures in C++", Horowitz, Sahni, Mehta)

1. void newRoot(Element x, Two3Node a)
   This is invoked when the root of the 2-3 tree is to change. The single element x is inserted into the new root, while a is made its MiddleChild. The old root becomes the LeftChild of the new root
2. Two3Node findNode(Element x)
   This is a modified version of search(Element x) (above). It searches a nonempty 2-3 tree for the presence of an element with key x.key. If this key is present, then it returns null. Otherwise, it returns the leaf node encountered in the search. Method insert() uses the variable p to store the node returned by findNode. findNode also creates a data structure that enables us to return from p to root. This data structure could be a list of the nodes on the path from root to p. Such a data structure is needed, as following a node split, it is necessary to access the parent of the node that was split.
3. void insertionError(Element x, Two3Node root)
   When an attempt to insert an element whose key corresponds to that of an element already in the 2-3 tree is made, an insertion error occurs. This method signals an error.
4. void putIn(Element x, Two3Node node)
   This method is used to insert an element x into a node (this) that has exactly one element in it. The subtree a is to be placed immediately to the right of x. So, if x becomes dataL, then a becomes MiddleChild, and the previous values of dataL and MiddleChild move to dataR and RightChild, respectively. If x becomes dataR, then a becomes RightChild
5. Element split(Two3Node p, Element x, Two3Node olda, Two3Node a)
   This operates on a Two3Node (p) that initially contains two elements as follows: The newly created, empty node pointed at by a will contain the element with the largest key from among the two elements initially in p and the element x.
   The element with the smallest key will be the only element left in p. The three original children of p and the olda will occupy the four children data members that need to be defined in p and a. The method returns the element with the median key.

Deletions:

Deletion from a 2-3 tree is conceptually no harder than insertion. If we are deleting an element that is not in a leaf node, then we transform this into a deletion from a leaf node by replacing the deleted element with a suitable element that is in a leaf. For example, if we are to delete the element with key 50 that is in the root of , then this element can be replaced by either the element with key 20 or the element with key 60. Both are leaf nodes. In a general situation, we may use either the element with the largest key in the subtree on the left or the element with the smallest key in the subtree on the right of the element being deleted.

Deletion examples:

A sequence of deletions.

A delete Figure 16.27, delete 44 Figure 16.28, delete 44 conclusion to see better.

Remember: If we are deleting an element that is not a leaf node, then we transform this into a deletion from a leaf node by replacing the deleted node by a suitable element that is in a leaf.

Thus we only have to "worry" about deletions from leaf nodes.

Also, the text these notes came from, say in the above example, "to delete the element with key 70, we must merely set dataR.key = MAXKEY in node C". Note that this implies that the code they provide herein, does not delete or make a cell null, but rather just sets its key value to be the specified conventional value for keys not allowed.

The patterns of what can happen will most certainly help you with writing your code.

• The three cases of rotation
  1. p is the left child of r
  2. p is the middle child of r
  3. p is the right child of r
• Combine cases
• Split cases

1. Modify node p as necessary to reflect its status after the desired element has been deleted

2. for ( ; p has zero elements && p != root ; p = r)
       {
   	let r be the parent of p, and let q be the left or right sibling of p (as appropriate);
   	if (q is a 3-node) perform a rotation
   	else perform a combine;
        }  

3. If p has zero elements, then p must be the root. The left child of p becomes the new root, and node p is deleted.

public void deleteKey(Two3Node p, Element x)
  // Key x.key is to be deleted from the leaf node p
{
   if (x.key == p.dataL.key)  // delete first element
	if (p.dataR.key != MAXKEY)
	{  // p is a 3-node
		p.dataL = p.dataR;
		p.dataR.key = MAXKEY;
	}
	else
		p.dataL.key = MAXKEY;  // p is a 2-node
    else
	p.dataR.key = MAXKEY;  // delete second element
}

  // Rotation when p is a left child of r, q is a middle child of r
   	p.dataL =  r.dataL;
	p.MiddleChild =  q.LeftChild; 
	r.dataL =  q.dataL;

	q.dataL =  q.dataR;
	q.LeftChild = q.MiddleChild;
	q.MiddleChild = q.RightChild;
   	q.dataR.key = MAXKEY;  

  // Combine when p is a left child of r, q is a right sibling of p

   	p.dataL =  r.dataL;
	p.dataR =  q.dataL;
	p.MiddleChild =  q.LeftChild;
	p.RightChild =  q.MiddleChild;  

	if (r.dataR.key == MAXKEY) // r was a 2-node
		r.dataL = MAXKEY;
	else
		{
		r.dataL.key = r.dataR;   
   		r.dataR.key = MAXKEY;  
		r.MiddleChild = r.RightChild;
		}

Analysis of 2-3 tree deletion: It should be evident that an individual rotation or combine takes O(1) time. If a rotation is performed, deletion is completed. If a combine is performed, p moves up a level in the 2-3 tree. Hence , the number if combines that can be performed cannot exceed the height of the 2-3 tree.
Consequently, deletion from a 2-3 tree with n elements takes O(log n) time.

Summary of methods you will need to do for 2-3 Tree implementation:

*Public methods for TwoThreeTree<p> constructor (could be the Create in specification) search (compare()) insert delete *Private methods (with method that uses them) insert (above) newRoot findNode insertionError putIn split delete (steps and code snippets above) findDelNode rotate (3 cases: figures above) p is the left child of r (code snippet above) p is the middle child of r p is the right child of r combine (3 cases each with possible subcases) p is the left child of r (shown in figures above) p is the middle child of r p is the right child of r (r must have right and left children) deletionError

By the way, I have seen a recursive delete method for 2-3 trees...

Don't forget about this helpful applet page