In Chapter 16, we introduce the TNode class to describe the nodes in a binary tree. A tree node object has three instance variables that include the value and references to the left and right children. For the STree class, we extend the structure of a tree node to include a fourth variable, which provide a link to the parent of the node. The STNode class defines the modified tree node object.
In the STree class, we maintain and update the parent field when we add or remove an element from the tree. The implementation of the STree iterator relies on information in the parent field. The iterator scans the tree in ascending order using an iterative version of the inorder traversal. The parent link enables us to identify the next element in the scan, which may involve retracing steps along a path of parents from the current node. Below example gives a tree view and a node view of an STree object. Dotted lines represent the parent links. Note that the parent of the root node is null :
The STree Class Private Members and Constructor :
The study of the STree class implementation begins with its variables. The instance variable, root, is an STNode reference that is the starting point for the binary tree which stores the elements. The integer variable treeSize maintains the number of elements in the tree. The add() and remove() methods are responsible for updating the size. To ensure the integrity of iterator operations, the class maintains an integer value modCount, which is updated each time the tree structure changes.
Private methods simplify the implementation of the STree class and promote code reuse. The remove() method must use a search algorithm to locate the node to be deleted. This is the same search algorithm used by contains(). Rather than duplicating code, we create a private method findNode() that returns an STNode
The following is a declaration of the instance variables, the private methods and constructor in the STree class :
Inserting and Locating a Node :
The add() method inserts an element in an STree collection by iterating down a path from the root to an empty subtree. The private method findNode() uses the same algorithm although it looks for a match. Arriving at an empty tree indicates that the item is not found. The method returns a reference to the STNode object in the tree.
The implementation on add() and find() are shown below :
Deleting a Node :
The private method removeNode() erases a node from the tree by finding a replacement node somewhere else in the tree and using it as a substitute for the deleted node. Issues surrounding the replacement node are critical to understanding the algorithm. First, we must choose the node so that, when it takes the place of the deleted node, its value maintains the search ordering of the tree. Second, subtrees for the deleted node and the replacement node may become orphaned during the process and must be reconnected in such a way that the new tree maintains ordering. Our discussion uses the following notation. The reference dNode identifies the deleted node D. A second reference, pNode, identifies the parent P of the deleted node. Note that when pNode is null, we are deleting the root. The removeNode() method sets out to find a replacement node R with reference rNode. The algorithm for finding a replacement node considers two cases that depend on the number of children attached to node D. We begin with the first case, in which the deleted node has at least one empty subtree; that is, there is one null child. In the next section, we analyze the second case, in which the deleted node has two nonempty subtrees.
- Deleted Node Has an Empty subtree
When the deleted node has a null child, the other child becomes the replacement node R. If the deleted node is a leaf node, it has two null children. In this case, the other node R is null. Below figure illustrates situations in which the replacement node is nonnull. Part(a) deletes node 35. The parent is node 30 and the replacement node is 33. In part(b), the deleted node is 25 with parent 30 and the replacement node is 26. Remove the node by having P link to the R with the same orientation that the parent had to the deleted node. By updating the parent field field for R, we create a link from R to P. The effect is to cut D out of the tree :
From upper figure(a), node D with value 35 is a right child of parent P=30 and has a non-null left child 33 which becomes the replacement node R. Attach R to the parent P as a right child and have R point back to P as its parent. In upper figure(b), node D with value 25 is a left child of 30 with a right child 26. The right child is the replacement node R and connects to P as a left child. Update the parent filed for R to point at P.
The removeNode() algorithm must address two special cases, one in which the deleted node is a leaf node and the other in which the deleted node is the root. In below figure(a), leaf node 50 is deleted. The replacement node R is null and becomes the right child of the parent. There is no update the the parent field for R.
When the parent is null, the deletion removes the root node. In this case, the replacement node becomes the new root. In below figure(b), we delete the root 40. The parent field of the replacement node 65 is null. The examples illustrate the different situations that can occur when the node to be deleted has a null child. The implementation of removeNode() tests for this condition and then uses a series of conditional statement to update the tree. The method uses the variables dNode, pNode and rNode to reference the deleted node, the parent node, and the replacement node respectively.
Below is the implementation on method removeNode() on case which the deleted node has one child to be null subtree :
- Deleted Node has Two Nonnull Children
A node with two children has some elements in its subtrees that are less than its value and some elements that are greater than its value. Deleting such a node requires finding a replacement node that maintains the correct ordering among the items. Once the replacement node is found, the algorithm employs a new strategy. Rather than removing the deleted node, it keeps the node in place but updates its value with that of the replacement node. The algorithm then removes the replacement node from the tree. Two examples illustrate the different situations which occur. In below figure, we delete node 25(a) and node 30(b) :
Method removeNode() selects as the replacement node R, a value that is "just after" the value of the deleted node. Thus, it selects the node which has the smallest value that is greater than the value of the deleted node. In upper figure(a), node 26 is the replacement node. It is the right child of 25. In figure(b), node 33 is the smallest value that is greater than 30. Locate 33 as the leftmost node in the right subtree of D. Note that in both cases, node R has an empty left subtree. Once we determine R, we copy its value to the deleted node and then splice out(delete) R from the tree. This is done by simply reconnecting the right subtree of R to the parent of R. Both part(a) and part(b) involve the same strategy. For instance, when deleting 30, the replacement node 33 has the right subtree 34. Copy 33 as the new value for the deleted node and attach the right subtree of R to 35, the parent of R. We show the final result in below figure :
The idea is simple, but the devil lies in the details. The problem is to find the replacement node and its parent so that the right subtree can be reconnected to the tree. To find the replacement node, start with the right child of the deleted node and then process down the path of the left children. At each step in the iterative process, update a reference to the parent of the current node, which is denoted by PofR. After the first step, PofR is the node D. If the right child of D has an empty left subtree, the process terminates. Otherwise, the replacement node is at the end of the path of left children with PofR a node on the path.
Splice out R from the tree by copying its value to D and then connect its right subtree to its parent PofR. The implementation of removeNode() uses a block of code to handle a situation in which the deleted node has two nonempty children. The block uses a loop to identify the replacement node and its parent. The method uses the reference variable pOfRNode for the node PofR. See implementation as below :
Complexity of Binary Search Tree Operations :
The best-case complexity for the add() and remove() operations occurs when the tree is complete. For a complete tree, the maximum number of comparisons needed to reach a leaf node is O(log2n). If follows that these operations have O(log2n) complexity in their best case. The worst case for these operations occurs when the tree is degenerate. In the degenerate case, the tree reduces to a linked list and the methods have O(n) complexity. An advance mathematical analysis shows that the average case have complexity O(log2n). In general, the binary search tree algorithms work well; however, the worst case is linear. In Chapter 27, we eliminate the worst-case condition by extending the search tree concept to balanced AVL trees and red-black trees.
沒有留言:
張貼留言