AVL Tree

py_ds.datastructures.trees.avl.AVLTree

AVLTree(items: Iterable[T] | None = None)

Bases: BinarySearchTree[T]

Initialize a binary tree.

Parameters:

Name	Type	Description	Default
items	Iterable[T] | None	Optional iterable of items to insert into the tree. If None, an empty tree is created.	None

Source code in src/py_ds/datastructures/trees/base.py

def __init__(self, items: Iterable[T] | None = None):
    """Initialize a binary tree.

    Args:
        items: Optional iterable of items to insert into the tree. If None,
            an empty tree is created.
    """
    self._root: _BinaryNode[T] | None = None
    self.size: int = 0
    items = items or []
    for item in items:
        self.insert(item)

Attributes

is_empty property

is_empty: bool

Check if the tree is empty.

Returns:

Type	Description
bool	True if the tree contains no elements, False otherwise.

height property

height: int

Get the height of the tree.

Returns:

Type	Description
int	The height of the tree. Returns -1 for an empty tree, 0 for a tree
int	with only a root node, and increases by 1 for each level below.

Functions

remove

remove(value: T) -> None

Remove a value from the AVL tree.

The tree is automatically rebalanced after removal to maintain the AVL property. If the value is not found, the tree remains unchanged.

Parameters:

Name	Type	Description	Default
value	T	The value to remove from the tree.	required

Source code in src/py_ds/datastructures/trees/avl.py

def remove(self, value: T) -> None:
    """Remove a value from the AVL tree.

    The tree is automatically rebalanced after removal to maintain the AVL
    property. If the value is not found, the tree remains unchanged.

    Args:
        value: The value to remove from the tree.
    """
    self._root, removed = self._remove_recursive(self._root, value)
    if removed:
        self.size -= 1

insert

insert(value: T) -> None

Insert a value into the AVL tree.

The tree is automatically rebalanced after insertion to maintain the AVL property, ensuring the tree remains balanced.

Parameters:

Name	Type	Description	Default
value	T	The value to insert into the tree.	required

Source code in src/py_ds/datastructures/trees/avl.py

def insert(self, value: T) -> None:
    """Insert a value into the AVL tree.

    The tree is automatically rebalanced after insertion to maintain the AVL
    property, ensuring the tree remains balanced.

    Args:
        value: The value to insert into the tree.
    """
    self._root = self._insert_recursive(self._root, value)
    self.size += 1

clear

clear() -> None

Remove all elements from the tree.

Source code in src/py_ds/datastructures/trees/base.py

def clear(self) -> None:
    """Remove all elements from the tree."""
    self._root = None
    self.size = 0

__len__

__len__() -> int

Return the number of elements in the tree.

Returns:

Type	Description
int	The number of elements in the tree.

Source code in src/py_ds/datastructures/trees/base.py

def __len__(self) -> int:
    """Return the number of elements in the tree.

    Returns:
        The number of elements in the tree.
    """
    return self.size

inorder

inorder() -> Iterator[T]

Traverse the tree in inorder (left, root, right).

Yields:

Type	Description
T	Values from the tree in inorder traversal order.

Source code in src/py_ds/datastructures/trees/base.py

def inorder(self) -> Iterator[T]:
    """Traverse the tree in inorder (left, root, right).

    Yields:
        Values from the tree in inorder traversal order.
    """

    def _inorder(node: _BinaryNode[T] | None):
        if node is None:
            return
        yield from _inorder(node.left)
        yield node.value
        yield from _inorder(node.right)

    yield from _inorder(self._root)

preorder

preorder() -> Iterator[T]

Traverse the tree in preorder (root, left, right).

Yields:

Type	Description
T	Values from the tree in preorder traversal order.

Source code in src/py_ds/datastructures/trees/base.py

def preorder(self) -> Iterator[T]:
    """Traverse the tree in preorder (root, left, right).

    Yields:
        Values from the tree in preorder traversal order.
    """

    def _preorder(node: _BinaryNode[T] | None):
        if node is None:
            return
        yield node.value
        yield from _preorder(node.left)
        yield from _preorder(node.right)

    yield from _preorder(self._root)

postorder

postorder() -> Iterator[T]

Traverse the tree in postorder (left, right, root).

Yields:

Type	Description
T	Values from the tree in postorder traversal order.

Source code in src/py_ds/datastructures/trees/base.py

def postorder(self) -> Iterator[T]:
    """Traverse the tree in postorder (left, right, root).

    Yields:
        Values from the tree in postorder traversal order.
    """

    def _postorder(node: _BinaryNode[T] | None):
        if node is None:
            return
        yield from _postorder(node.left)
        yield from _postorder(node.right)
        yield node.value

    yield from _postorder(self._root)

level_order

level_order() -> Iterator[T]

Traverse the tree in level-order (breadth-first).

Yields:

Type	Description
T	Values from the tree in level-order traversal, from top to bottom
T	and left to right at each level.

Source code in src/py_ds/datastructures/trees/base.py

def level_order(self) -> Iterator[T]:
    """Traverse the tree in level-order (breadth-first).

    Yields:
        Values from the tree in level-order traversal, from top to bottom
        and left to right at each level.
    """
    visited = [self._root] if self._root else []
    while visited:
        node = visited.pop(0)
        yield node.value
        if node.left:
            visited.append(node.left)
        if node.right:
            visited.append(node.right)

__str__

__str__() -> str

Return a string representation of the tree.

Returns:

Type	Description
str	A visual string representation of the tree structure. Returns 'EMPTY'
str	if the tree is empty.

Source code in src/py_ds/datastructures/trees/base.py

def __str__(self) -> str:
    """Return a string representation of the tree.

    Returns:
        A visual string representation of the tree structure. Returns 'EMPTY'
        if the tree is empty.
    """
    if self._root is None:
        return 'EMPTY'

    def build_tree_str(node: _BinaryNode[T], prefix: str, is_left: bool) -> str:
        tree = ''

        if node.right:
            tree += build_tree_str(node.right, prefix + ('│   ' if is_left else '    '), False)

        tree += prefix + ('└── ' if is_left else '┌── ') + str(node.value) + '\n'

        if node.left:
            tree += build_tree_str(node.left, prefix + ('    ' if is_left else '│   '), True)
        return tree

    result = ''
    if self._root.right:
        right_result = build_tree_str(self._root.right, '', False)
        result += right_result

    result += f'{self._root.value}\n'

    if self._root.left:
        left_result = build_tree_str(self._root.left, '', True)
        result += left_result

    return result

min

min() -> T

Get the minimum value in the tree.

Returns:

Type	Description
T	The minimum value in the tree.

Raises:

Type	Description
ValueError	If the tree is empty.

Source code in src/py_ds/datastructures/trees/binary_search_tree.py

def min(self) -> T:
    """Get the minimum value in the tree.

    Returns:
        The minimum value in the tree.

    Raises:
        ValueError: If the tree is empty.
    """
    if self.is_empty:
        raise ValueError('Empty tree')
    return self._get_min_node(self._root).value

max

max() -> T

Get the maximum value in the tree.

Returns:

Type	Description
T	The maximum value in the tree.

Raises:

Type	Description
ValueError	If the tree is empty.

Source code in src/py_ds/datastructures/trees/binary_search_tree.py

def max(self) -> T:
    """Get the maximum value in the tree.

    Returns:
        The maximum value in the tree.

    Raises:
        ValueError: If the tree is empty.
    """
    if self.is_empty:
        raise ValueError('Empty tree')
    return self._get_max_node(self._root).value

__contains__

__contains__(item: T) -> bool

Check if a value is in the tree.

Parameters:

Name	Type	Description	Default
item	T	The value to search for.	required

Returns:

Type	Description
bool	True if the value is found in the tree, False otherwise.

Source code in src/py_ds/datastructures/trees/binary_search_tree.py

def __contains__(self, item: T) -> bool:
    """Check if a value is in the tree.

    Args:
        item: The value to search for.

    Returns:
        True if the value is found in the tree, False otherwise.
    """
    if self.is_empty:
        return False
    curr = self._root
    while curr is not None:
        if item == curr.value:
            return True
        curr = curr.left if item < curr.value else curr.right
    return False