A binary search tree (BST) is a specialized form of a standard binary tree. We have already built a binary tree inside of our heaps class so the structure will feel familiar as we implement our changes to make a true BST. Binary search trees are a very efficient storage system for data storage, lookup, and removal with the time complexity of all operations directly proportional to the height of the tree. Since a binary tree can have at most two children, we eliminate half the remaining tree with each iteration of a function or in Big O notation, O(log n), where n is the number of nodes in the tree. This is true as long as the tree is reasonably balanced. If addition into the tree is performed on sorted data, it will result in a tree that always only uses either the left or right branch, leading the height of the tree to be as large as the data set and bringing the time complexity to O(n) time.
The basic rules of a binary search tree are:
- The left child and its subtree contain values less than the parent node’s values
- The right child and its subtree contain values greater than the parent node’s values
- Each left and right subtree is in itself an implementation of a BST
Throughout this implementation, we will create methods to add, remove, search, and print a BST as well as retrieve the minimum value in our tree.
At the conclusion of our Tree lesson, we provided a generic implementation of a Tree to start you down the path of creating generic data structures. In this lesson, we will be creating a generic BST throughout and teaching you how to add additional restrictions to your generics to ensure your code isn’t broken by someone trying to pass in custom objects.
Instructions
Create two empty classes, BinarySearchTree and BinaryNode.
In the BinaryNode class, right after the class name and before the curly brackets, at a set of angle brackets and the generic type T between them.
Do the same for BinarySearchTree.
We want the generic in BinarySearchTree to conform to two protocols, Comparable and CustomStringConvertible. We will use these when adding/finding/removing items from the BST and printing the tree.
When requiring conformance to multiple protocols, use the & operator between the protocols, this is called protocol composition and ensures that the object conforms to the combined requirements of the protocols.
Inside the BinaryNode class, add three instance variables:
dataof typeTleftChild, an optionalBinaryNoderightChild, an optionalBinaryNode
And an initializer with a parameter, data of type T, that sets self.data to data.
Inside the BinarySearchTree class, add a private instance variable, root as a BinaryNode optional, remember you need to include the generic reference <T> beside the class name, this ensures our BinarySearchTree and BinaryNodes are of the same type, T.
At the bottom of the file, create a new variable, numberTree, equal to a new BinarySearchTree with the type Int passed into the angle brackets of the class instantiation.