Skip to content

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

@something-9

Description

@something-9

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions