AVL Tree

AVL trees are a type of self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. If they differ by more than one at any time, rebalancing is performed to restore this property.

class trees.binary_trees.avl_tree.AVLNode(key: Any, data: Any, left: AVLNode | None = None, right: AVLNode | None = None, parent: AVLNode | None = None, height: int = 0): Definition of AVL Tree Node.

class trees.binary_trees.avl_tree.AVLTree

AVL Tree class that support basic operations.

Examples

>>> from trees.binary_trees import avl_tree
>>> tree = avl_tree.AVLTree()
>>> tree.insert(key=23, data="23")
>>> tree.insert(key=4, data="4")
>>> tree.insert(key=30, data="30")
>>> tree.insert(key=11, data="11")
>>> tree.insert(key=7, data="7")
>>> tree.insert(key=34, data="34")
>>> tree.insert(key=20, data="20")
>>> tree.insert(key=24, data="24")
>>> tree.insert(key=22, data="22")
>>> tree.insert(key=15, data="15")
>>> tree.insert(key=1, data="1")
>>> tree.get_leftmost().key
1
>>> tree.get_leftmost().data
'1'
>>> tree.get_height(tree.root)
4
>>> tree.search(24).data
`24`
>>> tree.delete(15)

delete(key: Any) → None

Delete the node by the given key.

Parameters:: key (Any) – The key of the node to be deleted.
Raises:: KeyNotFoundError – Raised if the key does not exist.

property empty: bool

True if the tree is empty; False otherwise.

Notes

This property is read-only.

Type:: bool

get_height(node: AVLNode | None) → int

Return the height of the given node.

Parameters:: node (NodeType) – The node to get its height.
Returns:: The height of the given node.
Return type:: int

get_leftmost(node: AVLNode) → AVLNode

Return the leftmost node from a given subtree.

The key of the leftmost node is the smallest key in the given subtree.

Parameters:: node (NodeType) – The root of the subtree.
Returns:: The node whose key is the smallest from the subtree of the given node.
Return type:: NodeType

insert(key: Any, data: Any) → None

Insert a (key, data) pair into the AVL tree.

Parameters:

key (Any) – The key associated with the data.
data (Any) – The data to be inserted.

Raises:

DuplicateKeyError – Raised if the key to be inserted has existed in the tree.

search(key: Any) → AVLNode

Look for an AVL node by a given key.

Parameters:: key (Any) – The key associated with the data.
Returns:: The node found by the given key.
Return type:: AVLNode
Raises:: KeyNotFoundError – Raised if the key does not exist.