Last active
June 14, 2017 18:26
-
-
Save ajhanwar/a47324987b1944a82dfdd5bffa601730 to your computer and use it in GitHub Desktop.
A simple implementation of a binary search tree in Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class BinarySearchTree: | |
| """ | |
| A simple program implementing a Binary Search Tree using only the key values | |
| Node for the BST is implemented as a private class for encapsulation | |
| """ | |
| class __Node: | |
| def __init__(self, key): | |
| self.key, self.left, self.right = key, None, None | |
| def __init__(self): | |
| self.reinit() | |
| def reinit(self): | |
| self.__root = None | |
| def is_empty(self): | |
| return self.__root is None | |
| def insert(self, key): | |
| if self.__root: | |
| try: | |
| self.__insert_helper(key, self.__root) | |
| except KeyError: | |
| print("Duplicate key:", key) | |
| else: | |
| self.__root = self.__Node(key) | |
| def __insert_helper(self, key, current_node): | |
| if current_node.key == key: | |
| raise KeyError | |
| elif key < current_node.key: | |
| if current_node.left and current_node.key is None: | |
| current_node.left.key = key | |
| elif current_node.left: | |
| self.__insert_helper(key, current_node.left) | |
| else: | |
| current_node.left = self.__Node(key) | |
| else: | |
| if current_node.right and current_node.key is None: | |
| current_node.right.key = key | |
| elif current_node.right: | |
| self.__insert_helper(key, current_node.right) | |
| else: | |
| current_node.right = self.__Node(key) | |
| def remove(self, key): | |
| try: | |
| self.__remove_helper(key, self.__root) | |
| except KeyError: | |
| print("Key:", key, "does not exist") | |
| def __remove_helper(self, key, current, parent=None): | |
| if key < current.key: # Keep searching to the left | |
| if current.left: | |
| self.__remove_helper(key, current.left, current) | |
| else: | |
| raise KeyError | |
| elif key > current.key: # Keep searching to the right | |
| if current.right: | |
| self.__remove_helper(key, current.right, current) | |
| else: | |
| raise KeyError | |
| else: | |
| if current.left is None and current.right is None: | |
| if parent.left is current: | |
| parent.left = None | |
| else: | |
| parent.right = None | |
| elif current.right is None: | |
| if parent.left is current: | |
| parent.left = current.left | |
| else: | |
| parent.right = current.left | |
| elif current.left is None: | |
| if parent.left is current: | |
| parent.left = current.right | |
| else: | |
| parent.right = current.right | |
| else: | |
| # Finding in-order predecessor | |
| switch = current.left | |
| while switch.right: | |
| parent = switch | |
| switch = switch.right | |
| # Swapping the key value of the predecessor with the node "to be deleted" | |
| # The predecessor may have children to its left. The key values of these nodes | |
| # will be greater than that of the "switch" node | |
| current.key = switch.key | |
| parent.right = switch.left | |
| def pre_order(self): | |
| self.__pre_order_helper(self.__root) | |
| def __pre_order_helper(self, current_node): | |
| if current_node is not None: | |
| print(current_node.key) | |
| self.__pre_order_helper(current_node.left) | |
| self.__pre_order_helper(current_node.right) | |
| def in_order(self): | |
| self.__in_order_helper(self.__root) | |
| def __in_order_helper(self, current_node): | |
| if current_node is not None: | |
| self.__in_order_helper(current_node.left) | |
| print(current_node.key) | |
| self.__in_order_helper(current_node.right) | |
| def post_order(self): | |
| self.__post_order_helper(self.__root) | |
| def __post_order_helper(self, current_node): | |
| if current_node is not None: | |
| self.__post_order_helper(current_node.left) | |
| self.__post_order_helper(current_node.right) | |
| print(current_node.key) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment