Metrics
The Metrics project inspires the Metrics library we are going to build, and it has two major components: MetricRegistry and supported types of metrics, including Counter and Histogram.
MetricRegistry
MetricRegistry is the starting point for using the Metrics library, and it is a collection of all the metrics used to track the application. So, for example, if we need to track one operation, says the number of rotations, we can define a Counter type metric for monitoring the rotations and register the Counter metric to the MetricRegistry with a readable name avlt.rotations. With this approach, we can manage the metrics easily, and a client code can retrieve any metric through the MetricRegistry via the metric’s name.
The implementation is straightforward. We use a Python dictionary to keep the registered metrics. The key is the metric’s name, and the value is the metric instance. We also define MetricType for the supported types for type safety.
MetricType = Union[Counter, Histogram]
"""Alias for the supported metric types."""
class MetricRegistry
def __init__(self) -> None:
self._registry: Dict[str, MetricType] = dict()
def register(self, name: str, metric: MetricType) -> None
self._registry[name] = metric
def get_metric(self, name: str) -> MetricType
return self._registry[name]
Counter
A Counter is a simple metric that counts something, i.e., increments and decrements the counter. Anything that needs to count can use a Counter -for example, the number of rotations.
class Counter
def __init__(self) -> None:
self._count = 0
def increase(self, n: int = 1) -> None
self._count += n
def decrease(self, n: int = 1) -> None
self._count -= n
@property
def count(self) -> int
return self._count
Histogram
By definition, a histogram is a graphical representation of the distribution of numerical data. It is an estimate of the probability distribution of a continuous variable (quantitative variable). The Histogram in the Metrics library measures the distribution of a data set, including the min, mean, max, standard deviation, and percentile.
Since we assume that the software we measure can be fit in RAM, we can use Python List to hold all the values and use Numpy to compute the data set’s distribution.
import numpy as np
class Histogram
def __init__(self) -> None:
self._values: List[int] = list()
def update(self, value: int) -> None
self._values.append(value)
def report(self) -> Dict
array = np.array(self._values)
return {
"min": array.min(),
"max": array.max(),
"medium": np.median(array),
"mean": array.mean(),
"stdDev": array.std(),
"percentile": {
"75": np.percentile(array, 75),
"95": np.percentile(array, 95),
"99": np.percentile(array, 99),
},
}
(The complete implementation is available at metrics.py)
Test
As always, we should have unit tests for our code as much as possible. Check test_metrics.py for the complete unit test.
Place Metrics in the trees
Red-Black Tree
After we implemented the Metrics library, we can place metrics in the red-black tree class. Since we want to measure the number of rotations, we use a Counter for it. To calculate the change of tree height, we can use a Histogram. Besides, we need a MetricRegistry for the Counter and Histogram to register. MetricRegistry supports managing the metrics in the entire program, so the higher level should pass the MetricRegistry instance to the RBTree class. With that, we modify the RBTree’s __init__ function like the following.
class RBTree:
def __init__(self, registry: Optional[metrics.MetricRegistry] = None) -> None:
self._NIL: Leaf = Leaf()
self.root: Union[Node, Leaf] = self._NIL
self._metrics_enabled = True if registry else False
if self._metrics_enabled and registry:
self._rotate_counter = metrics.Counter()
self._height_histogram = metrics.Histogram()
registry.register(name="rbt.rotate", metric=self._rotate_counter)
registry.register(name="rbt.height", metric=self._height_histogram)
(See red_black_tree.py for the complete implementation)
One thing to be aware of is that although it is essential to get insight into software behavior via a method such as the Metrics library, it does come with the cost. It adds complexity to the code and may slow down its performance because it needs to do more things. Therefore, we set the registry parameter optional. When we do not measure the code, we can disable the metrics to avoid potential side-effect.
Counter for Rotation
As the name counter imply, we need to increment the counter when rotation occurs. Therefore, we call increase() function at the end of the rotation functions like the following.
def _left_rotate(self, node_x: Node) -> None:
node_y = node_x.right
if isinstance(node_y, Leaf):
raise RuntimeError("Invalid left rotate")
node_x.right = node_y.left
if isinstance(node_y.left, Node):
node_y.left.parent = node_x
node_y.parent = node_x.parent
if isinstance(node_x.parent, Leaf):
self.root = node_y
elif node_x == node_x.parent.left:
node_x.parent.left = node_y
else:
node_x.parent.right = node_y
node_y.left = node_x
node_x.parent = node_y
if self._metrics_enabled:
self._rotate_counter.increase()
def _right_rotate(self, node_x: Node) -> None:
node_y = node_x.left
if isinstance(node_y, Leaf):
raise RuntimeError("Invalid right rotate")
node_x.left = node_y.right
if isinstance(node_y.right, Node):
node_y.right.parent = node_x
node_y.parent = node_x.parent
if isinstance(node_x.parent, Leaf):
self.root = node_y
elif node_x == node_x.parent.right:
node_x.parent.right = node_y
else:
node_x.parent.left = node_y
node_y.right = node_x
node_x.parent = node_y
if self._metrics_enabled:
self._rotate_counter.increase()
(See red_black_tree.py for the complete implementation)
Histogram for Height
The height may change after we perform insertion and deletion, and what we want to track is the trend of tree height. Therefore, we can update the Histogram at the end of insertion and deletion like below.
def insert(self, key: Any, data: Any) -> None:
new_node = Node(key=key, data=data, color=Color.RED)
parent: Union[Node, Leaf] = self._NIL
current: Union[Node, Leaf] = self.root
while isinstance(current, Node):
parent = current
if new_node.key < current.key:
current = current.left
elif new_node.key > current.key:
current = current.right
else:
raise tree_exceptions.DuplicateKeyError(key=new_node.key)
new_node.parent = parent
if isinstance(parent, Leaf):
new_node.color = Color.BLACK
self.root = new_node
else:
if new_node.key < parent.key:
parent.left = new_node
else:
parent.right = new_node
self._insert_fixup(new_node)
if self._metrics_enabled:
self._height_histogram.update(value=self.get_height(self.root))
def delete(self, key: Any) -> None:
if (deleting_node := self.search(key=key)) and (
isinstance(deleting_node, Node)
):
original_color = deleting_node.color
if isinstance(deleting_node.left, Leaf):
replacing_node = deleting_node.right
self._transplant(
deleting_node=deleting_node, replacing_node=replacing_node
)
if original_color == Color.BLACK:
if isinstance(replacing_node, Node):
self._delete_fixup(fixing_node=replacing_node)
elif isinstance(deleting_node.right, Leaf):
replacing_node = deleting_node.left
self._transplant(
deleting_node=deleting_node, replacing_node=replacing_node
)
if original_color == Color.BLACK:
if isinstance(replacing_node, Node):
self._delete_fixup(fixing_node=replacing_node)
else:
replacing_node = self.get_leftmost(deleting_node.right)
original_color = replacing_node.color
replacing_replacement = replacing_node.right
if replacing_node.parent == deleting_node:
if isinstance(replacing_replacement, Node):
replacing_replacement.parent = replacing_node
else:
self._transplant(replacing_node, replacing_node.right)
replacing_node.right = deleting_node.right
replacing_node.right.parent = replacing_node
self._transplant(deleting_node, replacing_node)
replacing_node.left = deleting_node.left
replacing_node.left.parent = replacing_node
replacing_node.color = deleting_node.color
if original_color == Color.BLACK:
if isinstance(replacing_replacement, Node):
self._delete_fixup(fixing_node=replacing_replacement)
if self._metrics_enabled:
self._height_histogram.update(value=self.get_height(self.root))
(See red_black_tree.py for the complete implementation)
With the Histogram in place, after some insertions and deletions, we can get the report like the maximum, the average, and the medium tree height. By combining these numbers with standard deviation and percentile also provided by the Histogram, we can clearly picture how the height change. For example, if we have a 99% percentile close to the median with a relatively low standard deviation, we can say the tree height is pretty consistent. In other words, the tree is fairly balanced.
AVL Tree
Similar to the red-black tree, we use a Counter to track rotation and a Histogram to monitor the tree height.
class AVLTree:
def __init__(self, registry: Optional[metrics.MetricRegistry] = None) -> None:
self.root: Optional[Node] = None
self._metrics_enabled = True if registry else False
if self._metrics_enabled and registry:
self._rotate_counter = metrics.Counter()
self._height_histogram = metrics.Histogram()
registry.register(name="avlt.rotate", metric=self._rotate_counter)
registry.register(name="avlt.height", metric=self._height_histogram)
(See avl_tree.py for the complete implementation)
We also increase the Counter at the end of the rotation functions and update the Histogram after insertion and deletion.
def insert(self, key: Any, data: Any) -> None:
new_node = Node(key=key, data=data)
parent: Optional[Node] = None
current: Optional[Node] = self.root
while current:
parent = current
if new_node.key < current.key:
current = current.left
elif new_node.key > current.key:
current = current.right
else:
raise tree_exceptions.DuplicateKeyError(key=new_node.key)
new_node.parent = parent
if parent is None:
self.root = new_node
else:
if new_node.key < parent.key:
parent.left = new_node
else:
parent.right = new_node
if not (parent.left and parent.right):
self._insert_fixup(new_node)
if self._metrics_enabled:
self._height_histogram.update(value=self.get_height(self.root))
def delete(self, key: Any) -> None:
if self.root and (deleting_node := self.search(key=key)):
if (deleting_node.left is None) and (deleting_node.right is None):
self._delete_no_child(deleting_node=deleting_node)
elif deleting_node.left and deleting_node.right:
replacing_node = self.get_leftmost(node=deleting_node.right)
deleting_node.key = replacing_node.key
deleting_node.data = replacing_node.data
if replacing_node.right:
self._delete_one_child(deleting_node=replacing_node)
else:
self._delete_no_child(deleting_node=replacing_node)
else:
self._delete_one_child(deleting_node=deleting_node)
if self._metrics_enabled:
self._height_histogram.update(value=self.get_height(self.root))
def _left_rotate(self, node_x: Node) -> None:
node_y = node_x.right
if node_y:
node_x.right = node_y.left
if node_y.left:
node_y.left.parent = node_x
node_y.parent = node_x.parent
if node_x.parent is None:
self.root = node_y
elif node_x == node_x.parent.left:
node_x.parent.left = node_y
else:
node_x.parent.right = node_y
node_y.left = node_x
node_x.parent = node_y
node_x.height = 1 + max(
self.get_height(node_x.left), self.get_height(node_x.right)
)
node_y.height = 1 + max(
self.get_height(node_y.left), self.get_height(node_y.right)
)
if self._metrics_enabled:
self._rotate_counter.increase()
def _right_rotate(self, node_x: Node) -> None:
node_y = node_x.left
if node_y:
node_x.left = node_y.right
if node_y.right:
node_y.right.parent = node_x
node_y.parent = node_x.parent
if node_x.parent is None:
self.root = node_y
elif node_x == node_x.parent.right:
node_x.parent.right = node_y
else:
node_x.parent.left = node_y
node_y.right = node_x
node_x.parent = node_y
node_x.height = 1 + max(
self.get_height(node_x.left), self.get_height(node_x.right)
)
node_y.height = 1 + max(
self.get_height(node_y.left), self.get_height(node_y.right)
)
if self._metrics_enabled:
self._rotate_counter.increase()
(See avl_tree.py for the complete implementation)
Binary Search Tree
Although this article focuses on the AVL tree and the red-black tree, it is easy to apply the same method to the binary search tree. Since the binary search tree does not have a rotation operation, we only need a Histogram to measure the tree height. In the next section, we can add the binary search tree into the comparison to better understand how self-balanced trees perform better than the binary search tree.
(See binary_search_tree.py for the implementation by adding metrics to the binary search tree)
Compare Red-Black Tree and the AVL Tree with Metrics
Experiment 1
In the first experiment, we use the Python built-in random sampling function ( random.sample) to generate a list ( insert_data) with 1000 unique random integers chosen from range 1 to 2000. And use the same random.sample function to randomize the insert_data as the delete_data. So the order to delete nodes from the trees will be random.
import random
insert_data = random.sample(range(1, 2000), 1000)
delete_data = random.sample(insert_data, 1000)
Then, we define a MetricRegistry for metrics and pass it when we define the trees. Here we also define a binary search tree so we can see the different performance between a binary search tree and self-balancing trees.
from forest import metrics
from forest.binary_trees import avl_tree
from forest.binary_trees import binary_search_tree
from forest.binary_trees import red_black_tree
registry = metrics.MetricRegistry()
bstree = binary_search_tree.BinarySearchTree(registry=registry)
avltree = avl_tree.AVLTree(registry=registry)
rbtree = red_black_tree.RBTree(registry=registry)
Once the trees and metrics are ready, we first insert the insert_data to the trees, and then delete nodes from the trees in the order of delete_data.
for key in insert_data:
bstree.insert(key=key, data=str(key))
avltree.insert(key=key, data=str(key))
rbtree.insert(key=key, data=str(key))
for key in delete_data:
bstree.delete(key=key)
avltree.delete(key=key)
rbtree.delete(key=key)
Finally, we can retrieve the metrics by their names and print out the number of rotations and the height’s histogram.
print("Binary Search Tree:")
bst_report = registry.get_metric(name="bst.height").report()
print(f" Height: {bst_report}")
print("AVL Tree:")
avlt_rotation_count = registry.get_metric(name="avlt.rotate").count
print(f" Rotation: {avlt_rotation_count}")
avlt_report = registry.get_metric(name="avlt.height").report()
print(f" Height: {avlt_report}")
print("Red-Black Tree")
rbt_rotation_count = registry.get_metric(name="rbt.rotate").count
print(f" Rotation: {rbt_rotation_count}")
rbt_repot = registry.get_metric(name="rbt.height").report()
print(f" Height: {rbt_repot}")
(The complete code is available at avlt_vs_rbt.py)
Since the input data is randomly generated, the result may be slightly different every time, but the result should be very close. The output may look like the following:
Binary Search Tree:
Height: {'min': 0, 'max': 21, 'medium': 17.0, 'mean': 16.52976488244122, 'stdDev': 3.621953722665703, 'percentile': {'75': 20.0, '95': 20.0, '99': 21.0}}
AVL Tree:
Rotation: 1053
Height: {'min': -1, 'max': 11, 'medium': 10.0, 'mean': 9.1765, 'stdDev': 1.7370514528936674, 'percentile': {'75': 10.0, '95': 11.0, '99': 11.0}}
Red-Black Tree
Rotation: 647
Height: {'min': 0, 'max': 12, 'medium': 11.0, 'mean': 9.9605, 'stdDev': 1.78295814589126, 'percentile': {'75': 11.0, '95': 12.0, '99': 12.0}}
From the output, we can see both the AVL tree and red-black tree are pretty balanced — the max height is 11 for the AVL tree and 12 for the red-black tree, and the medium and mean are also very close to their max heights. Also, their percentile is relative to the medium, and the standard deviation is relatively low. Therefore, we can say both trees have consistent heights.
On the contrary, the binary search tree has a worse tree height — 21 max and 17 medium. We know that based on the theorem we mentioned in the Binary Search Tree — Analysis: The expected height of a randomly build binary search tree on n distinct keys is O(lg n). Even if we generate the binary search tree randomly, its tree height is still worse than the AVL tree and the red-black tree. Moreover, the standard deviation of the binary search tree is more significant than the AVL tree and the red-black tree. Here, we show that the AVL tree and the red-black tree are more balanced than the binary search tree even if we randomly generate the binary search tree.
Regarding the number of rotations, the result shows that the AVL tree needs more rotations to keep balanced than the red-black tree, matching our expectations.
Experiment 2
We will be more aggressive in the second experiment than in the first experiment. We generate the insertion and deletion data randomly and perform insertion and deletion in random order. Again, we use the random.sample function to generate a list ( insert_data) with 2000 unique random integers chosen from range 1 to 3000. But this time, we generate the delete_data with 1000 unique random integers from range 1 to 3000. In this case, the insertion and deletion data are not identical. That means when we try to delete a node, the node may not exist, but that is not a problem. As long as we use the same insert_data and delete_data to test our trees in the same order, the experiment is valid. The following code shows how do we generate the test data.
import random
sample_data = random.sample(range(1, 3000), 2000)
insert_data = [("insert", item) for item in sample_data]
sample_data = random.sample(range(1, 3000), 1000)
delete_data = [("delete", item) for item in sample_data]
test_data = random.sample(
(insert_data + delete_data), len(insert_data) + len(delete_data)
)
We combine the insert_data and the delete_data to a single test_data via random.sample function, so the order will be random. Besides, each item of the insert_data and the delete_data is a pair that contains the operation type (insert or delete) and the data to be inserted or deleted. So, we know which operations, insert or delete, we need to perform when we go through the test_data with the operation type. That is how we make sure we use the same data set and same order to all three trees. The following code demonstrates the experiment.
from forest import metrics
from forest.binary_trees import avl_tree
from forest.binary_trees import binary_search_tree
from forest.binary_trees import red_black_tree
registry = metrics.MetricRegistry()
bstree = binary_search_tree.BinarySearchTree(registry=registry)
avltree = avl_tree.AVLTree(registry=registry)
rbtree = red_black_tree.RBTree(registry=registry)
for operation, key in test_data:
if operation == "insert":
bstree.insert(key=key, data=str(key))
avltree.insert(key=key, data=str(key))
rbtree.insert(key=key, data=str(key))
if operation == "delete":
bstree.delete(key=key)
avltree.delete(key=key)
rbtree.delete(key=key)
print("Binary Search Tree:")
bst_report = registry.get_metric(name="bst.height").report()
print(f" Height: {bst_report}")
print("AVL Tree:")
avlt_rotation_count = registry.get_metric(name="avlt.rotate").count
print(f" Rotation: {avlt_rotation_count}")
avlt_report = registry.get_metric(name="avlt.height").report()
print(f" Height: {avlt_report}")
print("Red-Black Tree")
rbt_rotation_count = registry.get_metric(name="rbt.rotate").count
print(f" Rotation: {rbt_rotation_count}")
rbt_repot = registry.get_metric(name="rbt.height").report()
print(f" Height: {rbt_repot}")
(The complete code is available at avlt_vs_rbt_2.py)
The test data is also randomly generated so that the result may be slightly different every time. Example output may look like the following:
Binary Search Tree:
Height: {'min': 0, 'max': 23, 'medium': 22.0, 'mean': 20.394120153387302, 'stdDev': 3.249885374276778, 'percentile': {'75': 22.0, '95': 23.0, '99': 23.0}}
AVL Tree:
Rotation: 1455
Height: {'min': 0, 'max': 12, 'medium': 11.0, 'mean': 10.175117170856412, 'stdDev': 1.6120322559944114, 'percentile': {'75': 11.0, '95': 12.0, '99': 12.0}}
Red-Black Tree
Rotation: 1136
Height: {'min': 0, 'max': 13, 'medium': 11.0, 'mean': 10.826161056668086, 'stdDev': 1.8772598891928807, 'percentile': {'75': 12.0, '95': 13.0, '99': 13.0}}
We got a similar result as experiment 1 — the red-black tree needs fewer rotations than the AVL tree, the AVL tree is slightly balanced than the red-black tree, and both the AVL tree and the red-black tree are much more balanced than the binary search tree.
Summary
Both AVL Tree and Red-Black Tree are wildly used in computer software. Each of them has strengths and weaknesses. Choosing the right one to fit our use cases best is critical for software development. Furthermore, knowing how to measure our choice and implementation is also essential for the software to be successful. This article introduces a method to measure software behavior using the AVL tree and the red-black tree we implemented in the previous articles as an example. Although the scope of the example in this article is small, the concept used here can be applied to any software. Hopefully, this article provides valuable knowledge so people can benefit from it.
