AVL Tree

Source code: src/pydsadoc/_tree/avl.py

class AVL(*args, **kwargs)

The AVL tree impelemented with linked list.

property height: int

Return the height of the tree.

in_order() → None

Implementation of in-order traversal with stack.

insert(value: int, /) → None

Insert value to the AVL Tree.

post_order()

Implementation of post-order traversal with stacks.

pre_order() → None

Implementation of pre-order traversal with stack.

remove(value: int, /) → None

Remove value in the AVL Tree.

Implementation Details

The AVL tree is somewhat more difficult than other data structures, so there are some implementation details to be shown. These methods mainly form the basics of the AVL.insert() and AVL.remove() operations described above.

Methods for Maintaining Balance

AVL._adjust(node: AVLNode, /) → AVLNode

Adjust the tree after removing or inserting.

AVL._get_balance(node: AVLNode | None, /) → int

Return the balance factor of the node.

AVL._get_height(node: AVLNode | None, /) → int

Return the height of the node.

AVL._rotation_left(node: AVLNode, /) → AVLNode

The left rotaion of the tree.

AVL._rotation_right(node: AVLNode, /) → AVLNode

The right rotaiton of the tree.

Other Methods

AVL._get_min(node: AVLNode, /) → AVLNode

Return the minimum element in the tree.

Time complexity is \(O(\log n)\).

AVL._insert_recursion(node: AVLNode, value: int, /) → AVLNode | None

Define the function of inserting recursively.

Return the node of the sub tree after inserting the value.

AVL._remove_recursion(node: AVLNode | None, value: int, /) → AVLNode | None

Define the function of removing recursively.

Return the node of the sub tree after removing the value.