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
Allocations
/ log
2
(Size)
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
0.03
0.03
0.04
0.04
0.04
0.05
0.05
Allocations
/ log
2
(Size)
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
0.03
0.03
0.04
0.04
0.04
0.05
0.05
Allocations
/ log
2
(Size)
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
0.910
0.920
0.930
0.940
0.950
0.960
0.970
0.980
0.990
1.000
Average Path Length
/ log
2
(Size)
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
0.910
0.920
0.930
0.940
0.950
0.960
0.970
0.980
0.990
1.000
Average Path Length
/ log
2
(Size)
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
0.00
0.50
1.00
1.50
2.00
2.50
3.00
3.50
Total Duration
in seconds
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
2.40
2.60
2.80
3.00
3.20
3.40
3.60
3.80
Duration
in milliseconds
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
2.00
2.50
3.00
3.50
4.00
4.50
5.00
5.50
Duration
in milliseconds
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
-1
0
log
2
(
Average Path Length
/ log
2
(Size))
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
-1
0
log
2
(
Average Path Length
/ log
2
(Size))
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
0
1
log
2
(
Maximum Path Length
/ log
2
(Size))
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
0
1
log
2
(
Maximum Path Length
/ log
2
(Size))
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
1.10
1.20
1.30
1.40
1.50
1.60
1.70
1.80
1.90
2.00
Maximum Path Length
/ log
2
(Size)
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
1.10
1.20
1.30
1.40
1.50
1.60
1.70
1.80
1.90
2.00
Maximum Path Length
/ log
2
(Size)
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
0.00
0.10
0.20
0.30
0.40
0.50
0.60
0.70
0.80
Rotations
/ Operations
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed
1
2
3
4
5
6
7
8
9
10
0.00
0.10
0.20
0.30
0.40
0.50
0.60
0.70
0.80
Rotations
/ Operations
Operations / 10
6
AVLRelaxedBottomUp
RedBlackRelaxedTopDown
LBSTRelaxed
WBSTRelaxed