| 47 | |
| 48 | |
| 49 | class AVL: |
| 50 | |
| 51 | def __init__(self): |
| 52 | self.root = None |
| 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 |
| 89 | |
| 90 | while n is not None: |
| 91 | height_right = n.height |
| 92 | height_left = n.height |
| 93 | |
| 94 | if n.right is not None: |
| 95 | height_right = n.right.height |
| 96 | |
| 97 | if n.left is not None: |
| 98 | height_left = n.left.height |
| 99 | |
| 100 | if abs(height_left - height_right) > 1: |
| 101 | if height_left > height_right: |
| 102 | left_child = n.left |
| 103 | if left_child is not None: |
| 104 | h_right = (left_child.right.height |
| 105 | if (left_child.right is not None) else 0) |
| 106 | h_left = (left_child.left.height |