Assignment3Data.txtChapter 1 Chapter 25: Binary Search Trees Chapter 26: AVL Trees Dr. Adriana Badulescu Chapter 25 Objectives ▪ To design and implement a binary search tree (§25.2). ▪ To represent binary trees using linked data structures (§25.2.1). ▪ To search an element in binary search tree (§25.2.2). ▪ To insert an element into a binary search tree (§25.2.3). ▪ To traverse elements in a binary tree (§25.2.4). ▪ To delete elements from a binary search tree (§25.3). ▪ To display binary tree graphically (§25.4). ▪ To create iterators for traversing a binary tree (§25.5). ▪ To implement Huffman coding for compressing data using a binary tree (§25.6). Binary Trees A list, stack, or queue is a linear structure that consists of a sequence of elements. A binary tree is a hierarchical structure. It is either empty or consists of an element, called the root, and two distinct binary trees, called the left subtree and right subtree. 60 55 100 57 67 107 45 G F R M T A (A) (B) See How a Binary Search Tree Works https://liveexample.pearsoncmg.com/dsanimation/BSTeBook.html Binary Tree Terms The root of left (right) subtree of a node is called a left (right) child of the node. A node without children is called a leaf. A special type of binary tree called a binary search tree is often useful. A binary search tree (with no duplicate elements) has the property that for every node in the tree the value of any node in its left subtree is less than the value of the node and the value of any node in its right subtree is greater than the value of the node. The binary trees in Figure 25.1 are all binary search trees. This section is concerned with binary search trees. Representing Binary Trees A binary tree can be represented using a set of linked nodes. Each node contains a value and two links named left and right that reference the left child and right child, respectively, as shown in Figure 25.2. Searching an Element in a Binary Search Tree Inserting an Element to a Binary Search Tree If a binary tree is empty, create a root node with the new element. Otherwise, locate the parent node for the new element node. If the new element is less than the parent element, the node for the new element becomes the left child of the parent. If the new element is greater than the parent element, the node for the new element becomes the right child of the parent. Here is the algorithm: Inserting an Element to a Binary Tree Trace Inserting 101 into the following tree Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Trace Inserting 101 into the following tree, cont. Inserting 59 into the Tree Tree Traversal Tree traversal is the process of visiting each node in the tree exactly once. There are several ways to traverse a tree. This section presents inorder, preorder, postorder, depth- first, and breadth-first traversals. The inorder traversal is to visit the left subtree of the current node first recursively, then the current node itself, and finally the right subtree of the current node recursively. The postorder traversal is to visit the left subtree of the current node first, then the right subtree of the current node, and finally the current node itself. Tree Traversal, cont. The preorder traversal is to visit the current node first, then the left subtree of the current node recursively, and finally the right subtree of the current node recursively. Tree Traversal, cont. The breadth-first traversal is to visit the nodes level by level. First visit the root, then all children of the root from left to right, then grandchildren of the root from left to right, and so on. For example, in the tree in Figure 25.2, the inorder is 45 55 57 59 60 67 100 101 107. The postorder is 45 59 57 55 67 101 107 100 60. The preorder is 60 55 45 57 59 100 67 107 101. The breadth-first traversal is 60 55 100 45 57 67 107 59 101. The Tree Interface The Tree interface defines common operations for trees. «interface» Tree
+search(e: E): boolean +insert(e: E): boolean +delete(e: E): boolean +inorder(): void +preorder(): void +postorder(): void +getSize(): int +isEmpty(): boolean +clear(): void Override the add, isEmpty, remove, containsAll, addAll, removeAll, retainAll, toArray(), and toArray(T[]) methods defined in Collection using default methods. Returns true if the specified element is in the tree. Returns true if the element is added successfully. Returns true if the element is removed from the tree successfully. Prints the nodes in inorder traversal. Prints the nodes in preorder traversal. Prints the nodes in postorder traversal. Returns the number of elements in the tree. Returns true if the tree is empty. Removes all elements from the tree. «interface» java.lang.Collection Tree https://liveexample.pearsoncmg.com/html/Tree.html The BST Class Let’s define the binary tree class, named BST with A concrete BST class can be defined to extend AbstractTree. BST> #root: TreeNode #size: int +BST() +BST(objects: E[]) +path(e: E): java.util.List<>> 1 m TreeNode Link 0 The root of the tree. The number of nodes in the tree. Creates a default BST. Creates a BST from an array of elements. Returns the path of nodes from the root leading to the node for the specified element. The element may not be in the tree. «interface» Tree BST https://liveexample.pearsoncmg.com/html/BST.html Example: Using Binary Trees Write a program that creates a binary tree using BST. Add strings into the binary tree and traverse the tree in inorder, postorder, and preorder. TestBST https://liveexample.pearsoncmg.com/html/TestBST.html Tree After Insertions Deleting Elements in a Binary Search Tree To delete an element from a binary tree, you need to first locate the node that contains the element and also its parent node. Let current point to the node that contains the element in the binary tree and parent point to the parent of the current node. The current node may be a left child or a right child of the parent node. There are two cases to consider: Deleting Elements in a Binary Search Tree Case 1: The current node does not have a left child, as shown in this figure (a). Simply connect the parent with the right child of the current node, as shown in this figure (b). parent current No left child Subtree parent Subtree current may be a left or right child of parent Subtree may be a left or right subtree of parent current points the node to be deleted Deleting Elements in a Binary Search Tree For example, to delete node 10 in Figure 25.9a. Connect the parent of node 10 with the right child of node 10, as shown in Figure 25.9b. 20 10 40 30 80 root 50 16 27 20 40 30 80 root 50 16 27 Deleting Elements in a Binary Search Tree Case 2: The current node has a left child. Let rightMost point to the node that contains the largest element in the left subtree of the current node and parentOfRightMost point to the parent node of the rightMost node, as shown in Figure 25.10a. Note that the rightMost node cannot have a right child, but may have a left child. Replace the element value in the current node with the one in the rightMost node, connect the parentOfRightMost node with the left child of the rightMost node, and delete the rightMost node, as shown in Figure 25.10b. Deleting Elements in a Binary Search Tree Case 2 diagram parent current . . . rightMost parentOfRightMost parent . . . parentOfRightMost Content copied to current and the node deleted Right subtree Right subtree current current may be a left or right child of parent current points the node to be deleted The content of the current node is replaced by content by the content of the right-most node. The right-most node is deleted. leftChildOfRightMost leftChildOfRightMost Deleting Elements in a Binary Search Tree Case 2 example, delete 20 rightMost 20 10 40 30 80 root 50 16 27 16 10 40 30 80 root 50 27 14 14 Examples Delete this node George Adam Michael Daniel Jones Tom Peter Daniel Adam Michael Jones Tom Peter Examples Daniel Adam Michael Jones Tom Peter Delete this node Daniel Michael Jones Tom Peter Examples Daniel Michael Jones Tom Peter Delete this node Daniel Jones Tom Peter TestBSTDelete https://liveexample.pearsoncmg.com/html/TestBSTDelete.html Binary Tree Time Complexity It is obvious that the time complexity for the inorder, preorder, and postorder is O(n), since each