Docs Red-Black Tree on GitHub

Red-Black Tree¶

Red-Black Tree is a self-balancing BST (Binary Search Tree) which means that it has a guaranteed height of O(log(n)) where n is the number of nodes within the tree. Each node in the Red-Black Tree has a color, this color is either “Red” or “Black”. Hence, the name “Red-Black Tree”. The color of the node is used only to re-balance the tree and has nothing to do with anything else.

So, the following is a simple Red-Black Tree:

           ______13|B______
          /                \
   _____8|R_             __17|R______
  /         \          /             \
1|B_        11|B      15|B         __25|B
    \                            /
    6|R                         22|R

As we can see, the previous Red-Black Tree is a Bineary Search Tree with an additional color denoted by either R for “red” or B for “black”. In addition to the BST characteristics, Red-black trees have these additional characteristics:

A node is either ‘red’ or ‘black’.
Root is always ‘black’.
A node is ‘red’ if it has two ‘black’ children.
Any child of a red-node is always ‘black’.
Black depth: is the depth of all black nodes.All nodes with zero or one children have the same black depth.
Shortest path: It is the path from the root to the nearest leaf-node and it is equal to the black depth.
Longest path: It is the path from the root to the furthest leaf-node with alternating red and black nodes. And it can’t be bigger than (2*shortest-path).

⏱ 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 nodes currently in the red-black tree.
h is the height of the red-black tree which equals to log(n).

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

☕️ API¶

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

class extra.trees.red_black_tree.RedBlackTree(iterable=None)¶

__contains__(find_val)¶

Searches the RedBlackTree() 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 RedBlackTree() instance.
Returns:	Returns True if the value exists in the RedBlackTree() instance and False` if not.
Return type:	bool

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> 17 in rbtree
True
>> 50 in rbtree
False

__init__(iterable=None)¶

A class method which creates a RedBlackTree() instance using an iterable 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 three cases In case the given object isn’t iterable. If one of the elements in the iterable is an Extra object. If one of the elements in the iterable is NOT a number. ValueError: – If one of the iterable elements is None.

Examples

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R

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

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

Using a non-iterable object will raise TypeError

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

Using nested RedBlackTree() objects will raise TypeError as well

>>> rbtree_1 = RedBlackTree([1])
>>> rbtree_2 = RedBlackTree([1, rbtree_1])
TypeError: Can't create `extra.RedBlackTree()` using `extra.RedBlackTree()`!!

__iter__()¶

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

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

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> for value in rbtree:
...     print(value, end=',')
13,8,17,1,11,15,25,6,

__len__()¶

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

Returns:	The length of the RedBlackTree() instance. Length is the number of red-black nodes in the instance.
Return type:	int

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> len(rbtree)
7

breadth_first_traverse()¶

Traverses the RedBlackTree() 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

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.breadth_first_traverse()
[13, 8, 17, 1, 11, 15, 25, 6]

clear()¶

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

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.clear()
>>> rbtree
/ \
>>> rbtree.is_empty()
True

count_leaf_nodes()¶

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

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

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.count_leaf_nodes()
4

depth_first_traverse()¶

Traverses the RedBlackTree() 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

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.depth_first_traverse()
[13, 8, 1, 6, 11, 17, 15, 25]

get_black_height()¶

Gets the black height of the RedBlackTree() instance. The black height is the number of black nodes; starting from the root till any leaf node knowing that the root node (which is always black) is not counted.

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

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.get_black_height()
2

get_depth()¶

Gets the depth of the RedBlackTree() instance.

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

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.get_depth()
0

get_height()¶

Gets the height of the RedBlackTree() instance. The RedBlackTree’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

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.get_height()
3

get_max()¶

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

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

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.get_max()
25

get_min()¶

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

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

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.get_min()
1

get_nodes_per_level()¶

Retrieves all tree nodes within the RedBlackTree() 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

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.get_nodes_per_level()
[[13], [8, 17], [1, 11, 15, 25], [6]]

inorder_traverse()¶

Traverses the RedBlackTree() 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

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.inrder_traverse()
[1, 6, 8, 11, 13, 15, 17, 25]

insert(value)¶

Inserts a numeric value in the RedBlackTree() instance according to the rules of binary search trees and the rules red-black trees as well.

Parameters:	value (int or float) – The new numeric value that will be inserted.
Raises:	ValueError: – If the given value is None. TypeError: – If either the given value is not a numeric value.

Example

>>> rbtree = RedBlackTree()
>>> rbtree.insert(10)
>>> rbtree.insert(5)
>>> rbtree.insert(15)
>>> rbtree
   _10|B_
  /      \
5|R      15|R
>>> rbtree.insert("2")
TypeError: `extra.RedBlackTree()` accepts only numbers!!

is_balanced()¶

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

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

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.is_balanced()
True

is_empty()¶

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

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

Example

>>> rbtree = RedBlackTree()
>>> rbtree.is_empty()
True
>>> rbtree.insert(10)
>>> rbtree.is_empty()
False

is_perfect()¶

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

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

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.is_perfect()
False

is_strict()¶

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

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

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.is_strict()
False

postorder_traverse()¶

Traverses the RedBlackTree() 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

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.postorder_traverse()
[6, 1, 11, 8, 15, 25, 17, 13]

preorder_traverse()¶

Traverses the RedBlackTree() 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

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.preorder_traverse()
[13, 8, 1, 6, 11, 17, 15, 25]

remove(del_value)¶

Removes the del_value from the RedBlackTree() instance which is one of the following cases:

Case I : The removed node is ‘red’, and its replacement is either ‘red’ or None.
Case II : The removed node is ‘red’, and its replacement is ‘black’.
Case III: The removed node is ‘black’, and its replacement is either ‘black’ or None.
Case IV : The removed node is ‘black’, and its replacement is ‘red’.

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

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.remove(13)
>>> rbtree
           ______15|B_
          /           \
   _____8|R_          17|B_
  /         \             \
1|B_        11|B           25|R
    \
    6|R
>>> rbtree.remove(50)
UserWarning: Couldn't find `50` in `extra.RedBlackTree()`!!

to_list()¶

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

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

Example

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.to_list()
[13, 8, 17, 1, 11, 15, 25, 6]

traverse(method='inorder')¶

Traversal is the process to visit all nodes of a RedBlackTree 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 RedBlackTree:

preorder - depth-first
inorder
posteorder
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

>>> rbtree = RedBlackTree([13, 8, 17, 1, 11, 15, 25, 6])
>>> rbtree
           ______13|B______
          /                \
   _____8|R_             __17|B_
  /         \          /       \
1|B_        11|B      15|R      25|R
    \
    6|R
>>> rbtree.traverse("preorder")
[13, 8, 1, 6, 11, 17, 15, 25]
>>> rbtree.traverse("inorder")
[1, 6, 8, 11, 13, 15, 17, 25]
>>> rbtree.traverse("postorder")
[6, 1, 11, 8, 15, 25, 17, 13]
>>> rbtree.traverse("breadth-first")
[13, 8, 17, 1, 11, 15, 25, 6]
>>> rbtree.traverse("extra")
ValueError: Given traverse method has to be one of these:
{'breadth-first', 'postorder', 'inorder', 'depth-first', 'preorder'}

Previous Next

2020, anwarvic

Created using Sphinx (1.8.6) with Minoo (Beta 0.9.7) theme.