Terminal Settings:
Debug:      xterm -T $TITLE -e
Release:    gnome-terminal -x


Distribution Information (1,000,000 entries)

Uniform;    unique = 1000000; most common = 1
Normalized; unique = 105338; most common = 40
Zipf;       unique = 217201; most common = 69331

Standings (not rebalanced):
Uniform:    RedBlack (10506) < AVL(11148) < ScapeGoat (13278) < Treap_No (13490) < SortedBinaryTree (13840) < ShuffleTree (14673)  < SplayTree_Uniform (18131) < SkipList (22150)
Normalized: Treap_All(9682) < SplayTree_Zipf (10279) < AVL (10825) < ShuffleTree (10865) < RedBlack (11086) < SortedBinaryTree (12954) << ScapeGoat (13667) < SkipList (22488)
Zipf:       Treap_All (6702) < SplayTree_Zipf (7208) << ShuffleTree (7278) < AVL (7449) < RedBlack (7837) < SortedBinaryTree (9188) < ScapeGoat (9666) < SkipList (14839)

Standings (rebalanced allowed)
Uniform:        SortedBinaryTree (9649) < Treap_No (10355) < AVL (10862) < RedBlack (11761) << ScapeGoat (13278) < ShuffleTree (14075) < SplayTree_Uniform (19373) < SkipList (19925)
Normalized:     ShuffleTree (9626) < SortedBinaryTree (9834) < Treap_All(9682) < SplayTree_Zipf (10279) < RedBlack (10403) < AVL (10568) << ScapeGoat (13667) < SkipList (20243)
Zipf:           ShuffleTree (6465) < Treap_All (6702) < SortedBinaryTree (6867) < RedBlack (7191) < SplayTree_Zipf (7208) < AVL (8010) < ScapeGoat (9666) < SkipList (14496)

Note: disallowed ScapeGoat (.5) results, as rebuilds would be prohibitive, and is always balanced



Support Balance: all (not nec. good idea in Treap or SplayTree)
Support Prioritize: all but AVL, RedBlackTree and ScapeGoatTree(weak in SkipList)

Self-Balancing vs Self-Tuning

Interesting test data ideas in shuffle article

To Do:
Iterators?


