red-black trees figure partially unbalanced tree with realistic amount of random datait' not likely tree would become seriously unbalanced howeverthere may be runs of sorted data that will partially unbalance tree searching partially unbalanced trees will take time somewhere between (nand (logn)depending on how badly the tree is unbalanced balance to the rescue to guarantee the quick (log nsearch times tree is capable ofwe need to ensure that our tree is always balanced (or at least almost balancedthis means that each node in tree needs to have roughly the same number of descendents on its left side as it has on its right in red-black treebalance is achieved during insertion (and also deletionbut we'll ignore that for the momentas an item is being insertedthe insertion routine checks that certain characteristics of the tree are not violated if they areit takes corrective actionrestructuring the tree as necessary by maintaining these characteristicsthe tree is kept balanced red-black tree characteristics what are these mysterious tree characteristicsthere are twoone simple and one more complicatedthe nodes are colored during insertion and deletionrules are followed that preserve various arrangements of these colors