Closed
Description
Description of the problem
The existing methods of _left_rotate and _right_rotate in the SelfBalancingBinaryTree are not working properly as it assumes j as the left child of parent in _right_rotate and right child of parent in _left_rotate, which causes conflict in some nodes.
Example of the problem
>>> tree = SelfBalancingBinaryTree()
>>> tree.insert(5,5)
>>> tree.insert(5.5,5.5)
>>> tree.insert(4.5,4.5)
>>> tree.insert(4.6,4.6)
>>> tree.insert(4.4, 4.4)
>>> tree.insert(4.55, 4.55)
>>> tree.insert(4.65, 4.65)
>>> print(tree)
[(2, 5, 5, 1), (None, 5.5, 5.5, None), (4, 4.5, 4.5, 3), (5, 4.6, 4.6, 6), (None, 4.4, 4.4, None), (None, 4.55, 4.55, None), (None, 4.65, 4.65, None)]
>>> tree._right_rotate(3, 5)
>>> print(tree)
[(2, 5, 5, 1), (None, 5.5, 5.5, None), (5, 4.5, 4.5, 3), (None, 4.6, 4.6, 6), (None, 4.4, 4.4, None), (None, 4.55, 4.55, 3), (None, 4.65, 4.65, None)]
>>> tree.tree[3].parent
5
>>> tree.tree[2].right
3
In this example node at index 3 has parent 5, while node at index 2 has 3 as one of its children. Since there cannot be two parents at the same time, this is a conflict.