(node: MyNode | None, data: Any)
| 148 | |
| 149 | |
| 150 | def insert_node(node: MyNode | None, data: Any) -> MyNode | None: |
| 151 | if node is None: |
| 152 | return MyNode(data) |
| 153 | if data < node.get_data(): |
| 154 | node.set_left(insert_node(node.get_left(), data)) |
| 155 | if ( |
| 156 | get_height(node.get_left()) - get_height(node.get_right()) == 2 |
| 157 | ): # an unbalance detected |
| 158 | left_child = node.get_left() |
| 159 | assert left_child is not None |
| 160 | if ( |
| 161 | data < left_child.get_data() |
| 162 | ): # new node is the left child of the left child |
| 163 | node = right_rotation(node) |
| 164 | else: |
| 165 | node = lr_rotation(node) |
| 166 | else: |
| 167 | node.set_right(insert_node(node.get_right(), data)) |
| 168 | if get_height(node.get_right()) - get_height(node.get_left()) == 2: |
| 169 | right_child = node.get_right() |
| 170 | assert right_child is not None |
| 171 | if data < right_child.get_data(): |
| 172 | node = rl_rotation(node) |
| 173 | else: |
| 174 | node = left_rotation(node) |
| 175 | h1 = my_max(get_height(node.get_right()), get_height(node.get_left())) + 1 |
| 176 | node.set_height(h1) |
| 177 | return node |
| 178 | |
| 179 | |
| 180 | def get_right_most(root: MyNode) -> Any: |
no test coverage detected