Go back
Group:
AVLRedBlack
AVLWeak
AVLRelaxed
RedBlackRelaxed
RankBalanced
WeightBalanced
WeightBalancedRelaxed
Probabilistic
SelfAdjusting
Relaxed
Conclusions
Operation:
Insert
InsertPersistent
InsertDelete
InsertDeletePersistent
Distribution:
Overall
Uniform
Zipf
Maximum
Skewed
Normal
1
2
3
4
5
6
7
8
9
10
0.00
5.00
10.00
15.00
20.00
25.00
30.00
35.00
40.00
45.00
50.00
Allocations
/ log
2
(Size)
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
0.04
0.04
0.05
0.05
0.05
0.05
0.05
0.05
0.05
0.05
0.05
Allocations
/ log
2
(Size)
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
0.04
0.04
0.05
0.05
0.05
0.05
0.05
0.05
0.05
0.05
0.05
Allocations
/ log
2
(Size)
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
0.910
0.915
0.920
0.925
0.930
0.935
0.940
0.945
0.950
0.955
Average Path Length
/ log
2
(Size)
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
0.910
0.915
0.920
0.925
0.930
0.935
0.940
0.945
0.950
0.955
Average Path Length
/ log
2
(Size)
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
0.00
1.00
2.00
3.00
4.00
5.00
6.00
7.00
Total Duration
in seconds
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
2.00
3.00
4.00
5.00
6.00
7.00
8.00
Duration
in milliseconds
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
2.00
3.00
4.00
5.00
6.00
7.00
8.00
Duration
in milliseconds
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
-1
0
log
2
(
Average Path Length
/ log
2
(Size))
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
-1
0
log
2
(
Average Path Length
/ log
2
(Size))
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
0
1
log
2
(
Maximum Path Length
/ log
2
(Size))
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
0
1
log
2
(
Maximum Path Length
/ log
2
(Size))
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
1.10
1.15
1.20
1.25
1.30
1.35
1.40
1.45
1.50
Maximum Path Length
/ log
2
(Size)
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
1.10
1.15
1.20
1.25
1.30
1.35
1.40
1.45
1.50
Maximum Path Length
/ log
2
(Size)
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
0.66
0.68
0.70
0.72
0.74
0.76
0.78
0.80
Rotations
/ Operations
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown
1
2
3
4
5
6
7
8
9
10
0.66
0.68
0.70
0.72
0.74
0.76
0.78
0.80
Rotations
/ Operations
Operations / 10
6
AVLBottomUp
AVLTopDown
RedBlackBottomUp
RedBlackTopDown