Binary Search Tree (BST)
1. Binary Search Tree (BST)
Let's explore binary search trees, which are a special kind of binary tree.2. Definition
Recall that a binary tree is a tree where each node has zero, one, or two children. In a binary search tree, the left subtree of a node contains only nodes with values less than the node itself, whereas the right subtree contains nodes with values greater than the node. The left and right subtrees must also be binary search trees.3. Implementation
To work with binary search trees, we will use the familiar TreeNode class. The BinarySearchTree class will implement the main operations and provide the root node's value.4. Searching
Suppose are searching for the value 72.5. Searching
We begin by comparing the root node with the search number. As 72 is greater than 60,6. Searching
we continue searching in the right subtree and compare the first node of this subtree, 70, with 72. As 72 is greater,7. Searching
we continue searching in the right subtree. 72 is less than 75,8. Searching
so we continue with the left tree.9. Searching
In this example, we do find the number.10. Searching
To implement this operation, we set current_node as the root. As long as we have nodes to visit, we check if search_value is equal to current_node's data. If yes, we return True. If it is less, current_node becomes current_node's left child. Otherwise, current_node becomes current_node's right child. If the loop ends without finding the search_value, we return False.11. Inserting
Let's implement the insert operation. We first create a new_node with the data. If the tree doesn't have a root node,12. Inserting
the root is the new_node, and the execution finishes.13. Inserting
If the tree has a root,14. Inserting
current_node is the root. We iterate until we insert the new_node. We check if the data to insert is less than current_node's data. If yes, we check if current_node has a left node. If it doesn't,15. Inserting
new_node becomes the current_node's left_child, and execution finishes.16. Inserting
However, if current_node has a left_child,17. Inserting
we set current_node as the left_child. We iterate until we find the place for the new_node.18. Inserting
Let's look at inserting a value greater than current_node's data. If current_node doesn't have a right_child,19. Inserting
new_node becomes the right_child, and the execution finishes.20. Inserting
But if current_node has a right_child,21. Inserting
current_node is set as the right_child and iteration continues. Let's finish by comparing new_node with current_node. As 68 is less than 70 and current_node doesn't have a left_child,22. Inserting
the new_node will become the left_child.23. Deleting
We'll now have a look at the delete operation. If the node we want to delete has no children,24. Deleting
we delete it.25. Deleting
If the node has one child,26. Deleting
we delete the node and connect the child with27. Deleting
the node's parent.28. Deleting
If the node being deleted has two children, we29. Deleting
replace it with its successor. The successor is the node with the smallest value greater than the value of the node we want to delete. To find the successor,30. Deleting
visit the right child of the node being deleted,31. Deleting
and keep visiting its left nodes32. Deleting
until the end.33. Deleting
Then, we replace34. Deleting
the node with its successor.35. Deleting
If the successor has a right child,36. Deleting
this child becomes the left child of the successor's parent.37. Uses
BSTs can be used to order lists efficiently. When adding or removing elements, there is no need to re-order all of them again. BSTs are faster at searching than arrays and linked lists and faster at inserting and deleting than arrays. They are also used to implement more advanced data structures like dynamic sets, lookup tables, and priority queues.38. Let's practice!
Let's practice!Create Your Free Account
or
By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.