Overview A binary search tree is a common tool for storing data that we want to...

Transcribed Image Text:

Overview A binary search tree is a common tool for storing data that we want to retrieve quickly. In this assignment we will build a naive binary search tree. We call it 'naive' because it will not try to keep itself balanced. Binary search trees are an upgrade to all lists because under most conditions they can maintain a logarithmic run time for all three primary functions: insert, delete, and search. While you should test your data structure yourself, we will put the binary search tree to the task from Assignment 2 - Unique Words. So for this assignment we will upgrade the Unique Words class. To complete this you will upgrade one class and implement one public class and one private class: ■ MyBinarySearch Tree<Type> (with a private Node) UniqueWords Formal Specifications MyBinarySearchTree<Type extends Comparable<Type>> -rootNode -size: int +comparisons long +add(item Type) -add(item Type, subTreeNode) : Node +remove (item: Type) -remove (item Type, subTree Node) : Node +find(item Type): Type -find(item Type, subTreeNode) : Type +height() int +size() int +isEmpty() boolean. -updateHeight(node: Node) +toString() String Field summary ⚫ root - Stores the root node of the binary search tree. ⚫ size - Stores the number of items stored in the binary search tree. ■ comparisons - Stores the number of comparisons made in the find method (one per recursive call). Method summary ⚫ add - Adds the item into the binary search tree where it belongs. The public method should call the private recursive method on the root. The private method adds the item to the sub-tree (recursively) and returns the root of the new sub-tree. This method should run in O(d) time where d is the depth the item added. ⚫ remove - Removes the item from the binary search tree. The public method should call the private recursive method on the root. The private method removes the item from the sub-tree (recursively) and returns the root of the new sub-tree. This method should run in O(d) time where d is the depth of the item removed. ⚫ find - Returns the item found if the item is in the binary search tree and null otherwise. The public method should call the private recursive method on the root. The private method searches the appropriate sub-tree recursively for the item.This method should run in O(d) time where d is the depth of the item found. height - Returns the height of the binary search tree. This method should run in O(1) time. ⚫ size - Returns the number of elements in the binary search tree. This method should run in O(1) time. ⚫ is Empty - Returns true if the trie is empty and false otherwise. This method should run in O(1) time. . updateHeight - Updates the height of the node. This method should run in O(1) time. ⚫ toString - Returns the contents of the binary search tree, in ascending order, as a string. This method should run in O(n) time where n is the number of items stored in the trie. +item Type +leftNode +right: Node +height: int +toString() String Method summary • item - The item stored in the node. Node ■ left -The left subtree. . right - The right subtree. height - The height of the node (the distance to the leaf nodes). We will count edges so leaves have height 0. Method summary ⚫ toString - Returns the contents of the node in this format: <item>H<height> UniqueWords +addUniqueWordsToBST() Method summary ■ addUniqueWords ToBST - Adds the unique words to a MyBinarySearch Tree. a. For each word in the list stored in book: ■Check to see if the word is stored in the binary search tree of unique words. If it is not, add it to the binary search tree. Otherwise, skip this word. b. Calls toString from the binary search tree to extract the words in order. Overview A binary search tree is a common tool for storing data that we want to retrieve quickly. In this assignment we will build a naive binary search tree. We call it 'naive' because it will not try to keep itself balanced. Binary search trees are an upgrade to all lists because under most conditions they can maintain a logarithmic run time for all three primary functions: insert, delete, and search. While you should test your data structure yourself, we will put the binary search tree to the task from Assignment 2 - Unique Words. So for this assignment we will upgrade the Unique Words class. To complete this you will upgrade one class and implement one public class and one private class: ■ MyBinarySearch Tree<Type> (with a private Node) UniqueWords Formal Specifications MyBinarySearchTree<Type extends Comparable<Type>> -rootNode -size: int +comparisons long +add(item Type) -add(item Type, subTreeNode) : Node +remove (item: Type) -remove (item Type, subTree Node) : Node +find(item Type): Type -find(item Type, subTreeNode) : Type +height() int +size() int +isEmpty() boolean. -updateHeight(node: Node) +toString() String Field summary ⚫ root - Stores the root node of the binary search tree. ⚫ size - Stores the number of items stored in the binary search tree. ■ comparisons - Stores the number of comparisons made in the find method (one per recursive call). Method summary ⚫ add - Adds the item into the binary search tree where it belongs. The public method should call the private recursive method on the root. The private method adds the item to the sub-tree (recursively) and returns the root of the new sub-tree. This method should run in O(d) time where d is the depth the item added. ⚫ remove - Removes the item from the binary search tree. The public method should call the private recursive method on the root. The private method removes the item from the sub-tree (recursively) and returns the root of the new sub-tree. This method should run in O(d) time where d is the depth of the item removed. ⚫ find - Returns the item found if the item is in the binary search tree and null otherwise. The public method should call the private recursive method on the root. The private method searches the appropriate sub-tree recursively for the item.This method should run in O(d) time where d is the depth of the item found. height - Returns the height of the binary search tree. This method should run in O(1) time. ⚫ size - Returns the number of elements in the binary search tree. This method should run in O(1) time. ⚫ is Empty - Returns true if the trie is empty and false otherwise. This method should run in O(1) time. . updateHeight - Updates the height of the node. This method should run in O(1) time. ⚫ toString - Returns the contents of the binary search tree, in ascending order, as a string. This method should run in O(n) time where n is the number of items stored in the trie. +item Type +leftNode +right: Node +height: int +toString() String Method summary • item - The item stored in the node. Node ■ left -The left subtree. . right - The right subtree. height - The height of the node (the distance to the leaf nodes). We will count edges so leaves have height 0. Method summary ⚫ toString - Returns the contents of the node in this format: <item>H<height> UniqueWords +addUniqueWordsToBST() Method summary ■ addUniqueWords ToBST - Adds the unique words to a MyBinarySearch Tree. a. For each word in the list stored in book: ■Check to see if the word is stored in the binary search tree of unique words. If it is not, add it to the binary search tree. Otherwise, skip this word. b. Calls toString from the binary search tree to extract the words in order.

Answer rating: 100% (QA)

You can go for this solution Binary Tree in Java Node creation class Node int key Node left right pu... View the full answer