| 42 | self.rightChild.parent = self |
| 43 | |
| 44 | class BinarySearchTree: |
| 45 | def __init__(self): |
| 46 | self.root = None |
| 47 | self.size = 0 |
| 48 | |
| 49 | def length(self): |
| 50 | return self.size |
| 51 | |
| 52 | def __len__(self): |
| 53 | return self.size |
| 54 | |
| 55 | def __iter__(self): |
| 56 | return self.root.__iter__() |
| 57 | |
| 58 | def put(self, key, val): |
| 59 | if self.root: |
| 60 | self._put(key, val, self.root) |
| 61 | else: |
| 62 | self.root = TreeNode(key, val) |
| 63 | self.size = self.size + 1 |
| 64 | |
| 65 | def _put(self, key, val, currentNode): |
| 66 | if key < currentNode.key: |
| 67 | if currentNode.hasLeftChild(): |
| 68 | self._put(key, val, currentNode.leftChild) |
| 69 | else: |
| 70 | currentNode.leftChild = TreeNode(key, val, parent=currentNode) |
| 71 | else: |
| 72 | if currentNode.hasRightChild(): |
| 73 | self._put(key, val, currentNode.rightChild) |
| 74 | else: |
| 75 | currentNode.rightChild = TreeNode(key, val, parent=currentNode) |
| 76 | |
| 77 | def __setitem__(self, k, v): |
| 78 | self.put(k, v) |
| 79 | |
| 80 | def get(self, key): |
| 81 | if self.root: |
| 82 | res = self._get(key, self.root) |
| 83 | if res: |
| 84 | return res.payload |
| 85 | else: |
| 86 | return None |
| 87 | else: |
| 88 | return None |
| 89 | |
| 90 | def _get(self, key, currentNode): |
| 91 | if not currentNode: |
| 92 | return None |
| 93 | elif currentNode.key == key: |
| 94 | return currentNode |
| 95 | elif key < currentNode.key: |
| 96 | return self._get(key, currentNode.leftChild) |
| 97 | else: |
| 98 | return self._get(key, currentNode.rightChild) |
| 99 | |
| 100 | def __getitem__(self, key): |
| 101 | return self.get(key) |