red-black-tree

B-tree when you’re managing more than thousands of items and you’re paging them from a disk or some slow storage medium. RB tree when you’re doing fairly frequent inserts, deletes and retrievals on the tree. AVL tree when your inserts and deletes are infrequent relative to your retrievals. think B+ trees are a good general-purpose ordered container data structure, even in main memory. Even when virtual memory isn’t an issue, cache-friendliness often is, and B+ trees are particularly good for sequential access - the same asymptotic performance as a linked list, but with cache-friendliness close to a simple array. [Read More]

Introduction: Please refer the introduction of RBT here. So, we now know the invariants or properties of RBT which make it rbt :) Insertion of element in RBT or red black tree breaks one of the 4 invariants or properties. So we have to fix it in minimal possible way. To assist us with we have 2 solutions : Flipping the color Right and left rotation Insertion: Insertion begins by adding the node much as binary search tree insertion does and by coloring it red. [Read More]

Deletion of a node from a red black tree is very difficult. During insertion we selected the color of a new node as red to make it easier. We forced a red violation and fixed it. Red violations are easy to fix, and we took full advantage of that to produce a truly elegant recursive algorithm. When you want to delete a node, you don’t have the option of choosing its color. [Read More]

A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer who called them “symmetric binary B-trees”, but acquired its modern name in a paper in 1978 by Leo J. Guibas and Robert Sedgewick, due to printing press technology of that time. Unfortunately, they were not able to print the paper in red black ink as was supposed, but the name stayed. [Read More]

Definition A balanced search tree is a tree which can provide operations like insert, delete and search in O(lg n) where n is the height of tree and lg n is height. Motivation behind Balanced Search tree Properties of sorted array Consider the sorted array. If we have a sorted array, what kinds of operations can we perform on it? Binary search in O(logn) time. (We use binary search) Select element given ith order statistic in O(1) Computing min/max of array - O(1) Predecessor/Successor - O(1), just find that element and return one before/after it Rank - how many keys stored are less than or equal to the key - O(logn) Output in sorted order - O(n) Simply using a sorted array would be unacceptable for insertion/deletion because it could use O(n) time. [Read More]