AVL Tree

AVL is a self-balancing binary search tree which is a non-linear data structure that stores numbers hierarchical with the assertion that any operation, like insertion, searching, and deletion, will be done in log(n) time-complexity where n is the number of elements in the AVL. AVL was named after the initials of its inventors: Adel’son-Vel’skii and Landis.

../../_images/avl.gif

⏱ Time-Complexity

The following table sums up all the different public functionality in this class and also provides the worst-case time complexity along side with the optimal time complexity that I will try to reach in future releases Insha’Allah. Generally, we are going to use the following indicators in the table:

  • n is the number of elements currently in the AVL tree.
  • h is the AVL tree’s height which approximatley equals to log(n).
Method Description Worst-case Optimal
is_empty() Checks if the AVL tree is empty. O(1) O(1)
__len__() Returns the number of the nodes of the AVL Tree. O(1) O(1)
__repr__() Represents the AVL Tree as a string. O(n) O(n)
__iter__() Iterates over the AVL Tree. O(n) O(n)
__contains__() Checks the existence of the given item. O(h) O(h)
get_height() Gets the AVL Tree’s height. O(n) O(1)
get_depth() Gets the AVL Tree’s depth. O(n) O(1)
get_nodes_per_level() Returns a list of all nodes per level. O(n) O(n)
is_balanced() Checks if the AVL Tree is balanced. O(n) O(1)
is_perfect() Checks if the AVL Tree is perfect. O(n) O(1)
is_strict() Checks if the AVL Tree is strict. O(n) O(1)
count_leaf_nodes() Counts all leaf nodes in the tree. O(n) O(n)
clear() Clears the whole AVL tree instance. O(1) O(1)
to_list() Converts the AVL tree instance to a normal list. O(n) O(n)
traverse() Traverses the AVL Tree based on given method. O(n) O(n)
preorder_traverse() Traverses the AVL Tree in an pre-order manner. O(n) O(n)
inorder_traverse() Traverses the AVL Tree in an in-order manner. O(n) O(n)
postorder_traverse() Traverses the AVL Tree in an post-order manner. O(n) O(n)
breadth_first_traverse() Traverses the AVL Tree level by level. O(n) O(n)
depth_first_traverse() Traverses the AVL Tree in an pre-order manner. O(n) O(n)
get_min() Gets the minimum number in the AVL Tree. O(h) O(h)
get_max() Gets the maximum number in the AVL Tree. O(h) O(h)
insert() Inserts a certain value to the AVL Tree. O(h) O(h)
remove() Removes a certain value from the AVL Tree. O(h) O(h)

☕️ API

Here are all of the public methods that can be used with AVL() objects:

class extra.trees.avl.AVL(iterable=None)

AVL is self-balancing (BST), Binary Search Tree which is a non-linear data structure that can be defined recursively using a collection of binary tree nodes, where each node contains a numeric value and it has either zero, one or two references to the children binary tree nodes instances. And the value holding by the node must be greater than all values being hold by the left subtree and smaller that all the values being hold by the right subtree.

__contains__(find_val)

Searches the AVL() for the given value and returns True if the value exists and False if not.

Parameters:find_val (int or float) – The value to be searched for in the AVL() instance.
Returns:Returns True if the value exists in the AVL() instance and False if not.
Return type:bool

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> 5 in avl
True
>> 50 in bst
False
__init__(iterable=None)

Initializes an AVL() instance using an optional iterable object in time-complexity of O(n) where n is the number of elements inside the given iterable.

Parameters:

iterable (iterable (default: None)) – An iterable python object that implements the __iter__ method. For example, list and tuple are both iterables.

Raises:
  • TypeError: – It can be raised in two cases
    1. In case the given object isn’t iterable.
    2. If one of the elements in the iterable is an Extra object.
    3. If one of the elements in the iterable is NOT a number.
  • ValueError: If one of the iterable elements is None.

Examples

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7

Using an iterable object with None as one of its elements will raise ValueError

>>> AVL([2, None])
ValueError: Can't use `None` as an element within `extra.AVL()`!!

Using a non-iterable object will raise TypeError

>>> AVL(2)
TypeError: The given object isn't iterable!!

Using nested AVL() objects will raise TypeError as well

>>> avl_1 = AVL([1])
>>> avl_2 = AVL([1, avl_1])
TypeError: Can't create `extra.AVL()` using `extra.AVL()`!!
__iter__()

Iterates over the AVL() instance and returns a generator of the AVLNode() values in breadth-first manner.

Yields:int or float – The number stored at each node in the instance.

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> for value in avl:
...     print(value, end=',')
4,2,6,1,3,5,7
__len__()

Gets the length of the AVL() instance in constant time.

Returns:The length of the AVL() instance. Length is the number of tree nodes in the instance.
Return type:int

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> len(avl)
7
breadth_first_traverse()

Traverses the AVL() instance in breadth-first manner. Which means that the tree nodes will be visited level by level.

Returns:A list of all values of the pre-order visited nodes.
Return type:list

Example

>>> avl = AVL([[2, 5, 4, 6, 3])
>>> avl
  3__
 /   \
2     5
     / \
    4   6
>>> avl.breadth_first_traverse()
[4, 2, 6, 1, 3, 5, 7]
clear()

Removes all nodes within the AVL() instance in constant time.

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.clear()
>>> avl
/ \
>>> avl.is_empty()
True
count_leaf_nodes()

Counts the number of leaf nodes in the AVL() instance. Leaf nodes are the tree nodes that have no children.

Returns:A positive integer representing the number of leaf nodes in the AVL().
Return type:int

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.count_leaf_nodes()
4
depth_first_traverse()

Traverses the AVL() instance in depth-first manner. Which means that the parent is visited first. Then, the left subtree (if found), then the right subtree (if found).

Note

It’s the same as preorder_traverse() method.

Returns:A list of all values of the pre-order visited nodes.
Return type:list

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.depth_first_traverse()
[4, 2, 1, 3, 6, 5, 7]
get_depth()

Gets the depth of the AVL() instance.

Returns:A positive integer representing the depth of the instance.
Return type:int

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.get_depth()
0
get_height()

Gets the height of the AVL() instance. The AVL’s height is the number of edges between the root and the furthest leaf node.

Returns:A positive integer representing the height of the instance.
Return type:int

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.get_height()
22
get_max()

Gets the maximum value in the AVL() isntance. The maximum value can be found at the right-most tree node in the AVL() instance.

Returns:The maximum numeric value in the AVL() instance.
Return type:int or float
Raises:IndexError: – In case the AVL() instance is empty.

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.get_max()
7
get_min()

Gets the minimum value in the AVL() isntance. The minimum value can be found at the left-most tree node in the AVL() instance.

Returns:The maximum numeric value in the AVL() instance.
Return type:int or float
Raises:IndexError: – In case the AVL() instance is empty.

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.get_min()
1
get_nodes_per_level()

Retrieves all tree nodes within the AVL() instance so that all tree nodes in a certain level will be concatenated into a separate list.

Returns:A nested list where the first inner-list has all the tree nodes in the first level, the second inner-list has all the tree nodes in the second level, … so on.
Return type:list

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.get_nodes_per_level()
[[4], [2, 6], [1, 3, 5, 7]]
inorder_traverse()

Traverses the AVL() instance in in-order manner. Which means that the left subtree (if found) is visited first. Then, the parent then the right subtree (if found).

Returns:A list of all values of the in-order visited nodes.
Return type:list

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.inorder_traverse()
[1, 2, 3, 4, 5, 6, 7]
insert(value)

Inserts a numeric value in the AVL()` instance according to the rules of binary search trees.

Parameters:

value (int or float) – The new numeric value that will be inserted.

Raises:
  • ValueError: – If the given value is None.
  • TypeError: – If the given value is not a numeric value.

Example

>>> avl = AVL()
>>> avl.insert(10)
>>> avl
10
>>> avl.insert(5)
>>> avl
5
 \
  10
>>> avl.insert(15)
  10
 /  \
5    15
>>> avl.insert(8)
>>> avl
  __10
 /    \
5      15
 \
  8
>>> avl.insert("2")
TypeError: `extra.AVL()` accepts only numbers!!
is_balanced()

Checks if the AVL() instance is balanced. A AVL is balanced if the difference between the depth of any two leaf nodes is less than or equal to one.

Returns:True if the AVL() instance is balanced and False if it is not balanced.
Return type:bool
Raises:UserWarning: – If the AVL() is empty.

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> bst.is_balanced()
True
is_empty()

Checks if the AVL() instance is empty or not in constant time.

Returns:A boolean flag showing if the AVL() instance is empty or not. True shows that this instance is empty and False shows it’s not empty.
Return type:bool

Example

>>> avl = AVL()
>>> avl.is_empty()
True
>>> avl.insert(10)
>>> avl.is_empty()
False
is_perfect()

Checks if the AVL() instance is perfect. A AVL is perfect if all its levels are completely filled.

Returns:True if the AVL() instance is perfect and False if it is not perfect.
Return type:bool
Raises:UserWarning: – If the AVL() is empty.

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.is_perfect()
True
is_strict()

Checks if the AVL() instance is strict. A AVL is strict if all its non-leaf nodes have two children (left and right).

Returns:True if the AVL() instance is strict and False if it is not strict.
Return type:bool
Raises:UserWarning: – If the AVL() is empty.

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> bst.is_strict()
True
postorder_traverse()

Traverses the AVL() instance in post-order manner. Which means that the left subtree (if found) is visited first. Then, the right subtree (if found) then the parent.

Returns:A list of all values of the pre-order visited nodes.
Return type:list

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.postorder_traverse()
[1, 3, 2, 5, 7, 6, 4]
preorder_traverse()

Traverses the AVL() instance in pre-order manner. Which means that the parent is visited first. Then, the left subtree (if found), then the right subtree (if found).

Note

It’s the same as depth_first_traverse() method.

Returns:A list of all values of the pre-order visited nodes.
Return type:list

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.preorder_traverse()
[4, 2, 1, 3, 6, 5, 7]
remove(del_value)

Removes the del_value from the AVL() instance.

Parameters:del_value (int or float) – The value to be deleted from the subtree.
Raises:UserWarning: – If the AVL() instance is empty of if the value wasn’t found in the instance.

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.remove(6)
>>> avl
    __4__
   /     \
  2       7
 / \     /
1   3   5
>>> avl.remove(50)
UserWarning: Couldn't find `50` in `extra.AVL()`!!
to_list()

Converts the AVL() instance to a list where values will be inserted in breadth-first manner.

Returns:A list object containing the same elements as the AVL() instance.
Return type:list

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.to_list()
[4, 2, 6, 1, 3, 5, 7]
traverse(method='inorder')

Traversal is the process to visit all nodes of a AVL starting from the root as we cannot randomly access any node in a binary tree. There are four ways which we use to traverse a AVL:

  1. preorder - depth-first
  2. inorder
  3. posteorder
  4. breadth-first
Parameters:

method (str (default="inorder")) – A lower-cased string describing the type of traversal that will be used. It could be one of these values: [“inorder”, “postorder”, “preorder”, “depth-first”, “breadth-first”]

Returns:

A list of all values of the visited nodes according to the specified traversal method.

Return type:

list

Raises:
  • ValueError: If the given method isn’t known.
  • TypeError: If the given method isn’t a string.

Example

>>> avl = AVL([1, 2, 3, 4, 5, 6, 7])
>>> avl
    __4__
   /     \
  2       6
 / \    / \
1   3   5   7
>>> avl.traverse("preorder")
[4, 2, 1, 3, 6, 5, 7]
>>> avl.traverse("inorder")
[1, 2, 3, 4, 5, 6, 7]
>>> avl.traverse("postorder")
[1, 3, 2, 5, 7, 6, 4]
>>> avl.traverse("breadth-first")
[4, 2, 6, 1, 3, 5, 7]
>>> avl.traverse("extra")
ValueError: Given traverse method has to be one of these:
{'breadth-first', 'postorder', 'inorder', 'depth-first', 'preorder'}