RED BLACK Tree

Introduction

https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/

Insertion

The below link covers theory.

https://www.geeksforgeeks.org/c-program-red-black-tree-insertion/

For implementation:

https://www.geeksforgeeks.org/c-program-red-black-tree-insertion/

Time Complexity: O(logn)
Space Complexity: O(1)

Deletion

The below link only covers theory.

https://www.geeksforgeeks.org/red-black-tree-set-3-delete-2/

Time Complexity: O(logn)

Space Complexity: O(1)

References

• geeksforgeeks.org
• Introduction to algorithms by CLRS