Comparison To Other Structures
Both AVL trees and red-black trees are self-balancing binary search trees, so they are very similar mathematically. The operations to balance the trees are different, but both occur in O(log n) time. The real difference between the two is the limiting height. For a tree of size :
- An AVL tree's height is strictly less than:
where is the golden ratio.
- A red-black tree's height is at most
AVL trees are more rigidly balanced than red-black trees, leading to slower insertion and removal but faster retrieval.
Read more about this topic: AVL Tree
Famous quotes containing the words comparison to, comparison and/or structures:
“It is very important not to become hard. The artist must always have one skin too few in comparison to other people, so you feel the slightest wind.”
—Shusha Guppy (b. 1938)
“We teach boys to be such men as we are. We do not teach them to aspire to be all they can. We do not give them a training as if we believed in their noble nature. We scarce educate their bodies. We do not train the eye and the hand. We exercise their understandings to the apprehension and comparison of some facts, to a skill in numbers, in words; we aim to make accountants, attorneys, engineers; but not to make able, earnest, great- hearted men.”
—Ralph Waldo Emerson (1803–1882)
“The philosopher believes that the value of his philosophy lies in its totality, in its structure: posterity discovers it in the stones with which he built and with which other structures are subsequently built that are frequently better—and so, in the fact that that structure can be demolished and yet still possess value as material.”
—Friedrich Nietzsche (1844–1900)