-
-
Save ispapadakis/53e8e6dcbdca8108eddcd0f660365458 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
| # Extended the class to address previous comments: a) redundant inserts, b) delete method | |
| class Node: | |
| def __init__(self, val): | |
| self.val = val | |
| self.parent = None | |
| self.__left = None | |
| self.__right = None | |
| self.code = 3 | |
| @property | |
| def L(self): | |
| return self.__left | |
| @L.setter | |
| def L(self,node): | |
| if node.__class__.__name__ != 'Node': | |
| raise TypeError('node of type Node expected') | |
| if self.__left is None: | |
| self.code -= 1 | |
| self.__left = node | |
| @L.deleter | |
| def L(self): | |
| self.__left = None | |
| self.code += 1 | |
| @property | |
| def R(self): | |
| return self.__right | |
| @R.setter | |
| def R(self,node): | |
| if node.__class__.__name__ != 'Node': | |
| raise TypeError('node of type Node expected') | |
| if self.__right is None: | |
| self.code -= 2 | |
| self.__right = node | |
| @R.deleter | |
| def R(self): | |
| self.__right = None | |
| self.code += 2 | |
| def __repr__(self): | |
| return 'Node({})'.format(self.val) | |
| class BST: | |
| def __init__(self): | |
| self.root = None | |
| def __str__(self): | |
| out = [] | |
| def tprint(node,side='_',prefix=''): | |
| out.append('{}{}:{:3d})'. \ | |
| format(prefix,side,node.val)) | |
| if node.L: | |
| tprint(node.L,'L',prefix+' ') | |
| if node.R: | |
| tprint(node.R,'R',prefix+' ') | |
| if self.root: | |
| tprint(self.root) | |
| return '\n'.join(out) | |
| def insert(self, val): | |
| def insertNode(node, val): | |
| if val < node.val: | |
| if node.L: | |
| return insertNode(node.L, val) | |
| else: | |
| node.L = Node(val) | |
| node.L.parent = (node,'L') | |
| return True | |
| elif val > node.val: | |
| if node.R: | |
| return insertNode(node.R, val) | |
| else: | |
| node.R = Node(val) | |
| node.R.parent = (node,'R') | |
| return True | |
| else: | |
| return False | |
| if self.root is None: | |
| self.root = Node(val) | |
| return True | |
| else: | |
| return insertNode(self.root, val) | |
| def find(self, val): | |
| def findNode(node, val): | |
| if node is None: | |
| return None | |
| elif val == node.val: | |
| return node | |
| elif val < node.val: | |
| return findNode(node.L, val) | |
| else: | |
| return findNode(node.R, val) | |
| return findNode(self.root, val) | |
| def max(self,node=None): | |
| level = 0 | |
| def right(node): | |
| nonlocal level | |
| level += 1 | |
| if node.R: | |
| return right(node.R) | |
| return level, node | |
| if node: | |
| return right(node) | |
| else: | |
| return right(self.root) | |
| def min(self,node=None): | |
| level = 0 | |
| def left(node): | |
| nonlocal level | |
| level += 1 | |
| if node.L: | |
| return left(node.L) | |
| return level, node | |
| if node: | |
| return left(node) | |
| else: | |
| return left(self.root) | |
| def delete(self, val): | |
| def deleteNode(node): | |
| if node.parent: | |
| p,dir = node.parent | |
| def replaceWith(node): | |
| if node is None: | |
| delattr(p,dir) | |
| else: | |
| setattr(p,dir,node) | |
| node.parent = (p,dir) | |
| else: | |
| def replaceWith(node): | |
| self.root = node | |
| if node and node.parent: | |
| node.parent = None | |
| if node.code == 3: | |
| replaceWith(None) | |
| elif node.code is 2: | |
| replaceWith(node.L) | |
| elif node.code is 1: | |
| replaceWith(node.R) | |
| else: | |
| lmr, minR = self.min(node.R) | |
| lml, maxL = self.max(node.L) | |
| if lml < lmr: | |
| node.val = minR.val | |
| deleteNode(minR) | |
| else: | |
| node.val = maxL.val | |
| deleteNode(maxL) | |
| node = self.find(val) | |
| if node: | |
| deleteNode(node) | |
| if __name__ == '__main__': | |
| print("Testing ...") | |
| lst = [1,15,-4,9,22,3,4,6,5,3,8,1,0,9,-1,-5] | |
| t = BST() | |
| for k in lst: | |
| t.insert(k) | |
| print('Example BST','\n'*4,t) | |
| print('Find Max from Root Left') | |
| print(t.max(t.root.L)) | |
| print('Find Min from Root Right') | |
| print(t.min(t.root.R)) | |
| print('\nFind 4 ',t.find(4)) | |
| print('\nDelete 9') | |
| t.delete(9) | |
| print(t) | |
| print('\nDelete 1') | |
| t.delete(1) | |
| print(t) | |
| print('Construct New Tree') | |
| t = BST() | |
| t.insert(1) | |
| print(t) | |
| print('\nDelete 1') | |
| t.delete(1) | |
| print('Print Tree',t) | |
| print('Nothing is Left Over!') | |
| print('\n\nFinal Test\n\n') | |
| print('Construct Tree') | |
| lst = [1,-6,15,-4,9,22,3,4,6,5,3,8,1,0,9,-1,-5] | |
| t = BST() | |
| for k in lst: | |
| print('\n\t\tInsert ',k) | |
| t.insert(k) | |
| print('Tree is Now\n',t) | |
| print('Now Delete All These Elements') | |
| for k in lst: | |
| print('\n\t\tDeleting ',k) | |
| t.delete(k) | |
| print('Tree is Now\n',t) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Extended the class to address previous comments: a) redundant inserts, b) delete method