An AVL tree doctest Examples: >>> t = AVLtree() >>> t.insert(4) insert:4 >>> print(str(t).replace(" \\n","\\n")) 4 ************************************* >>> t.insert(2) insert:2 >>> print(str(t).replace(" \\n","\\n").replace(" \\n","\\n")) 4 2
| 243 | |
| 244 | |
| 245 | class AVLtree: |
| 246 | """ |
| 247 | An AVL tree doctest |
| 248 | Examples: |
| 249 | >>> t = AVLtree() |
| 250 | >>> t.insert(4) |
| 251 | insert:4 |
| 252 | >>> print(str(t).replace(" \\n","\\n")) |
| 253 | 4 |
| 254 | ************************************* |
| 255 | >>> t.insert(2) |
| 256 | insert:2 |
| 257 | >>> print(str(t).replace(" \\n","\\n").replace(" \\n","\\n")) |
| 258 | 4 |
| 259 | 2 * |
| 260 | ************************************* |
| 261 | >>> t.insert(3) |
| 262 | insert:3 |
| 263 | right rotation node: 2 |
| 264 | left rotation node: 4 |
| 265 | >>> print(str(t).replace(" \\n","\\n").replace(" \\n","\\n")) |
| 266 | 3 |
| 267 | 2 4 |
| 268 | ************************************* |
| 269 | >>> t.get_height() |
| 270 | 2 |
| 271 | >>> t.del_node(3) |
| 272 | delete:3 |
| 273 | >>> print(str(t).replace(" \\n","\\n").replace(" \\n","\\n")) |
| 274 | 4 |
| 275 | 2 * |
| 276 | ************************************* |
| 277 | """ |
| 278 | |
| 279 | def __init__(self) -> None: |
| 280 | self.root: MyNode | None = None |
| 281 | |
| 282 | def get_height(self) -> int: |
| 283 | return get_height(self.root) |
| 284 | |
| 285 | def insert(self, data: Any) -> None: |
| 286 | print("insert:" + str(data)) |
| 287 | self.root = insert_node(self.root, data) |
| 288 | |
| 289 | def del_node(self, data: Any) -> None: |
| 290 | print("delete:" + str(data)) |
| 291 | if self.root is None: |
| 292 | print("Tree is empty!") |
| 293 | return |
| 294 | self.root = del_node(self.root, data) |
| 295 | |
| 296 | def __str__( |
| 297 | self, |
| 298 | ) -> str: # a level traversale, gives a more intuitive look on the tree |
| 299 | output = "" |
| 300 | q = MyQueue() |
| 301 | q.push(self.root) |
| 302 | layer = self.get_height() |