This project was made in order to help me in the rebuild of some containers (map, set) on my ft_containers project.
A red-black tree is a data structure. It respects some well defined rules so that all branches are balanced.
A red-black tree must respect the following rules:
- Each node is either red or black.
- All NULL nodes are considered black.
- A red node does not have a red child.
- Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.
Methods | Complexity | Notes |
---|---|---|
insertNode | O(log n) | Add a new node. The first parameter is the key and the second is the value to stock. |
deleteNode | O(log n) | Delete a node. The parameter is the key to find to delete. |
printTree | O(n) | Print all node (key, color, parent, left, right, value). |