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 and/or structures:
“The difference between human vision and the image perceived by the faceted eye of an insect may be compared with the difference between a half-tone block made with the very finest screen and the corresponding picture as represented by the very coarse screening used in common newspaper pictorial reproduction. The same comparison holds good between the way Gogol saw things and the way average readers and average writers see things.”
—Vladimir Nabokov (1899–1977)
“If there are people who feel that God wants them to change the structures of society, that is something between them and their God. We must serve him in whatever way we are called. I am called to help the individual; to love each poor person. Not to deal with institutions. I am in no position to judge.”
—Mother Teresa (b. 1910)