This data structure was created in 1972 by Rudolph Bayer. In it, searching, inserting and removing can all be completed in O[lg(n)]
This data structure was created in 1972 by Rudolph Bayer. In it, searching, inserting and removing can all be completed in O[lg(n)] ["big-O of log n"] time and the longest path from root to a leaf can be no more than twice the length of the shortest path.. This is because its balancing algorithm involves checking a namesake property of each of the nodes; a property that can have two possible values. For ten points, identify this type of balanced binary tree, named for the possible colors a node can be.
This data structure was created in 1972 by Rudolph Bayer. In it, searching, inserting and removing can all be completed in O[lg(n)]
{red-black} tree