Why red-black tree based implementation for java TreeMap?

java algorithm binary-search-tree avl-tree red-black-tree
Nikunj Banka picture Nikunj Banka · Feb 17, 2013 · Viewed 8.9k times · Source

The third paragraph of wikipedia's article on AVL trees says: "Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications."

So, shouldn't TreeMap be implemented using AVL trees instead of red-black trees(as there will be more look up intensive applictions for a hashing based data structure ) ?

Answer

Justin picture Justin · Feb 17, 2013

Red-Black trees are more general purpose. They do relatively well on add, remove, and look-up but AVL trees have faster look-ups at the cost of slower add/remove. Java's general policy is to provide the best general purpose data structures. It's also the same reason Java's default Array.sort(Object[] a) implementation is stable,adaptive ,iterative merge sort instead of quicksort.

Related questions

Iterate through binary search tree to find all leaves

I am pretty new to trees, and I am trying to create kind of a "leaf iterator". I'm thinking it should put all nodes that does not have a .left and .right value onto a stack, but I'm not sure …

Read More
Finding the max/min value in an array of primitives using Java

It's trivial to write a function to determine the min/max value in an array, such as: /** * * @param chars * @return the max value in the array of chars */ private static int maxValue(char[] chars) { int max = chars[0]; for (int ktr = 0; …

Read More
Generating all permutations of a given string

What is an elegant way to find all the permutations of a string. E.g. permutation for ba, would be ba and ab, but what about longer string such as abcdefgh? Is there any Java implementation example?

Read More