Python icon indicating copy to clipboard operation
Python copied to clipboard

There is a problem in this file "data_structures/binary_tree/avl_tree.py"

Open something-19 opened this issue 3 years ago • 1 comments

In the process of my study, I found that this file can not run successfully every time.

File "D:/data_structures/binary_tree/avl_tree.py", line 148, in rl_rotation
    assert right_child is not None`
AssertionError

For example, the above is a kind of frequent error reporting. Maybe the above problems can be solved by modifying 'del_node' function.

def del_node(root: my_node, data: Any) -> my_node | None:
    left_child = root.get_left()
    right_child = root.get_right()
    if root.get_data() == data:
        if left_child is not None and right_child is not None:
            temp_data = get_leftMost(right_child)
            root.set_data(temp_data)
            root.set_right(del_node(right_child, temp_data))
        elif left_child is not None:
            root = left_child
        elif right_child is not None:
            root = right_child
        else:
            return None
    elif root.get_data() > data:
        if left_child is None:
            print("No such data")
            return root
        else:
            root.set_left(del_node(left_child, data))
    else:  # root.get_data() < data
        if right_child is None:
            return root
        else:
            root.set_right(del_node(right_child, data))

    left_child = root.get_left()  # Add these two lines of code to solve the problem
    right_child = root.get_right()  # Add these two lines of code to solve the problem

    if get_height(right_child) - get_height(left_child) == 2:
        assert right_child is not None
        if get_height(right_child.get_right()) > get_height(right_child.get_left()):
            root = left_rotation(root)
        else:
            root = rl_rotation(root)
    elif get_height(right_child) - get_height(left_child) == -2:
        assert left_child is not None
        if get_height(left_child.get_left()) > get_height(left_child.get_right()):
            root = right_rotation(root)
        else:
            root = lr_rotation(root)
    height = my_max(get_height(root.get_right()), get_height(root.get_left())) + 1
    root.set_height(height)
    return root

As shown above, we can run the entire code by adding two lines of code to the original code.

something-19 avatar Jul 25 '22 07:07 something-19

Please make it a PR.

itsamirhn avatar Aug 06 '22 12:08 itsamirhn

looks good

kaven123uuu avatar Sep 14 '22 07:09 kaven123uuu