I wanted to get an understanding of different data structures and therefore implemented an AVL tree in python. However I somehow messed things up when it comes to insertion and therefore rotation.

If I run my module my terminal just spits out the root node and the node with value 3 for the first test and only the root for the second one. What is it I am doing wrong? I would appreciate another pairs of eyes as I miss the forest for the trees by trying to debug this π

`"""AVL-Tree implementation.""" class Node(): """Class representating an AVL node.""" __slots__ = ["data", "height", "key", "left", "right"] def __init__(self, key, data=None): """ Create new node. :param {any} key: Key to use for operations. :param {any} data: Payload to store. """ self.data = [data] self.height = 1 self.key = key self.left = self.right = None def __repr__(self): """Return string representation.""" return "{} ({} => {})".format(self.height, self.key, self.data) def get_height(node): """ Return height for node. :param {Node} node: Node to get height for. """ return node.height if node else 0 def in_order(node): """ Return node values in order. :param {Node} node: Node to process. """ if not node: return in_order(node.left) print(node) in_order(node.right) def insert(node, key, data=None): """ Insert new data. :param {Node} node: Current node. :param {any} key: Node key. :param {any} data: Payload. """ if not node: return Node(key, data) elif key == node.key: node.data.append(data) return node elif key < node.key: node.left = insert(node.left, key, data) else: node.right = insert(node.right, key, data) left_height = get_height(node.left) right_height = get_height(node.right) node.height = max(left_height, right_height) + 1 balance = left_height - right_height # Inbalance left if balance == 2: # left right => left left if key > node.left.key: node.left = rotate_left(node.left) # left left rotate_right(node) # Inbalance right elif balance == -2: # right left => right right if key < node.right.key: node.right = rotate_right(node.right) # right right rotate_left(node) return node def pre_order(node): """.""" if node: print(node) pre_order(node.left) pre_order(node.right) def rotate_left(node): r""" Left node rotation (balance == -2). 1 (node) \ 2 2 => / \ \ 1 3 3 :param {Node} node: Node to rotate. """ child = node.right child.left, node.right = node, child.left return node def rotate_right(node): r""" Right node rotation. 3 (node) / 2 2 => / \ / 1 3 1 :param {Node} node: Node to rotate on. """ child = node.left child.right, node.left = node, child.right return node if __name__ == "__main__": root = Node(0) for i in range(1, 4): root = insert(root, i) in_order(root) print(".....") root2 = Node(0) for i in range(1, 4): root2 = insert(root, i) in_order(root2) `

Thank you for your help!