| 53 | self.size = 0 |
| 54 | |
| 55 | def insert(self, value): |
| 56 | node = Node(value) |
| 57 | |
| 58 | if self.root is None: |
| 59 | self.root = node |
| 60 | self.root.height = 0 |
| 61 | self.size = 1 |
| 62 | else: |
| 63 | # Same as Binary Tree |
| 64 | dad_node = None |
| 65 | curr_node = self.root |
| 66 | |
| 67 | while True: |
| 68 | if curr_node is not None: |
| 69 | |
| 70 | dad_node = curr_node |
| 71 | |
| 72 | if node.label < curr_node.label: |
| 73 | curr_node = curr_node.left |
| 74 | else: |
| 75 | curr_node = curr_node.right |
| 76 | else: |
| 77 | node.height = dad_node.height |
| 78 | dad_node.height += 1 |
| 79 | if node.label < dad_node.label: |
| 80 | dad_node.left = node |
| 81 | else: |
| 82 | dad_node.right = node |
| 83 | self.rebalance(node) |
| 84 | self.size += 1 |
| 85 | break |
| 86 | |
| 87 | def rebalance(self, node): |
| 88 | n = node |