809 CHAPTER 9 2-4 Trees and B-Trees Objectives • To know what a 2-4 tree is (§9.1). • To design the Tree24 class that implements the Tree interface (§9.2). • To search an element in a 2-4 tree (§9.3). • To insert an element in a 2-4 tree and know how to split a node (§9.4). • To delete an element from a 2-4 tree and know how to perform transfer and fusion operations (§9.5). • To traverse elements in a 2-4 tree (§9.6). • To know how to implement the Tree24 class (§9.7). • To use B-trees for indexing large amount of data (§9.10).810 9.1 Introduction <Side Remark: completely-balanced tree> <Side Remark: 2-node> <Side Remark: 3-node> <Side Remark: 4-node> A 2-4 tree, also known as a 2-3-4 tree, is a complete balanced search tree with all leaf nodes appearing on the same level. In a 2-4 tree, a node may have one, two, or three elements. An interior 2-node contains one element and two children. An interior 3-node contains two elements and three children. An interior 4-node contains three elements and four children, as shown in Figure 9.1. e0 c0 c1 e0 e1c0c2c1 e0 e1 e2 c0c2 c1 c3 (a) 2-node (b) 3-node (c) 4-node Figure 9.1 An interior node of a 2-4 tree has two, three, or four children. <Side Remark: ordered> Each child is a sub 2-4 tree, possibly empty. The root node has no parent and leaf nodes have no children. The elements in the tree are distinct. The elements in a node are ordered such that )()()()()(433221100cEecEecEecEecE<<<<<<<< <Side Remark: E(kc)> <Side Remark: left subtree> <Side Remark: right subtree> Where E(kc) denote the elements in kc. Figure 9.1 shows an example of a 2-4 tree. kc is called the left subtree of ke and 1+kc is called the right subtree of ke. 20 27 34 15 3 16 23 24 25 29 50 60 70 Figure 9.2 A 2-4 tree is a full complete search tree. <Side Remark: binary vs. 2-4>811 In a binary tree, each node contains one element. A 2-4 tree tends to be shorter than a corresponding binary search tree, since a 2-4 tree node may contain two or three elements. 9.2 Designing Classes for 2-4 Trees The Tree24 class can be designed by implementing the Tree interface, as shown in Figure 9.3. The Tree24Node class defines tree nodes. The elements in the node are stored in a list named elements and the links to the child nodes are stored in a list named child, as shown in Figure 9.5. ***New Figure <PD: UML Class Diagram> Tree24<E> -root: Tree24Node<E>; +size: int +Tree24() +Tree24(objects: E[]) +search(e: E): boolean +insert(e: E): boolean +delete(e: E): boolean -matched(e: E, node: TreeNode<E>): boolean -getChildNode(e: E, node: TreeNode<E>): Tree24Node<E> -insert23(e: E, rightChildOfe: Tree24Node<E>, node: Tree24Node<E>): void -split(e: E, rightChildOfe: Tree24Node<E>, u: Tree24Node<E>, v: Tree24Node<E>): E -locate(e: E, node: Tree24Node<E>): int -delete(e: E, node: Tree24Node<E>): void -validate(e: E, u: Tree24Node<E>, path: ArrayList<Tree24Node<E>>): void -path(e: E): ArrayList<E> -leftSiblingTransfer(e: E): ArrayList<E> 1 mTree24Node<E> elements: ArrayList<E> child: ArrayList<Tree24Node<E>> +Tree24() +Tree24(o: E) Link 0 The root of the tree. The size of the tree. Creates a default 2-4 tree. Creates a 2-4 tree from an array of objects. Returns true if the element is in the tree. Returns true if the element is added successfully. Returns true if the element is removed from the tree successfully. Returns true if element e is in the specified node. Returns the next child node to search for e. Inserts element and along with the reference to its right child to a 2- or 3- node. Splits a 4-node u into u and v, inserts e to u or v, and returns the median element. Locates the insertion point of the element in the node. Deletes the specified element from the node. Performs a transfer and confusion operation if node u is empty. Return a search path that leads to element e Tree<E> An array list for storing the elements. An array list for storing the links to the child nodes. Creates an empty tree node. Creates a tree node with an initial element. Figure 9.3 The Tree24 class implements Tree.812 elements.get(0) elements.get(1) elements.get(2) elements.get(3)child.get(0) child.get(1) child.get(2)child.get(4) child.get(3) Figure 9.5 A 2-4 tree node stores the elements and the links to the child nodes in array lists. Pedagogical NOTE <side remark: 2-4 tree animation> Run from www.cs.armstrong.edu/liang/jds/exercisejds/Exercise10_5.html to see how a 2-4 tree works, as shown in Figure 9.4. Figure 9.4 The animation tool enables you to insert, delete, and search elements in a 2-4 tree visually. ***End NOTE 9.3 Searching an Element Searching an element in a 2-4 tree is similar to searching an element in a binary tree. The difference is that you have to also search an element within a node in addition to searching elements along the path. To search an element in a 2-4 tree, you start from the root and scan down. If an element is not in the node, move to an appropriate subtree. Repeat the process until a match is found or you arrive at an empty subtree. The algorithm is described in Listing 9.1. Listing 9.1 Searching an Element in a 2-4 Tree ***PD: Please add line numbers in the following code*** <Side Remark line 2: start from root> <Side Remark line 6: found> <Side Remark line 9: search a subtree> <Side Remark line 13: not found> boolean search(E e) { current = root; // Start from the root while (current != null) {813 if (match(e, current)) { // Element is in the node return true; // Element is found } else { current = getChildNode(e, current); // Search in a subtree } } return false; // Element is not in the tree } The match(e, current) method checks whether element e is in the current node. The getChildNode(e, current) method returns the root of the subtree for further search. Initially, let current point to the root (line 2). Repeat searching the element in the current node until current is null (line 4) or the element matches element (line 5) matches current.element. 9.4 Inserting an Element into a 2-4 Tree <Side Remark: overflow> <Side Remark: split> To insert an element e to a 2-4 tree, locate a leaf node in which the element will be inserted. If the leaf node is a 2-node or 3-node, simply insert the element into the node. If the node is a 4-node, inserting a new element would cause an overflow. To resolve overflow, perform a split