红黑树的删除压力测试和完整性检查

 1 import ‘dart:math‘;
 2 import ‘package:data_struct/tree/tree.dart‘;
 3 
 4 void run() {
 5   var size = 100000, loops = 1024;
 6   check(size, loops);
 7   stress(size);
 8 }
 9 
10 void check(int size, int loops) {
11   var rd = Random();
12   for (var i = 0; i < loops; i++) {
13     print(‘the $i times check...‘);
14 
15     var arr = List.generate(size, (_) => rd.nextDouble() * size);
16     var tree = RBTree.from(arr);
17     var bh = _checkIsRBTree(tree);
18     print(‘black height: $bh\n\r‘);
19 
20     for (var d in arr) {
21       tree.delete(d);
22       _checkIsRBTree(tree);
23     }
24 
25     tree = RBTree.from(arr);
26     for (var d in arr) {
27       tree.quickDelete(d);
28       _checkIsRBTree(tree);
29     }
30   }
31 }
32 
33 void stress(int size) {
34   var rd = Random();
35   var arr = List.generate(size, (_) => rd.nextDouble() * size);
36 
37   var tree = RBTree.from(arr);
38   var st = DateTime.now();
39   for (var d in arr) tree.delete(d);
40   var ft = DateTime.now();
41   print(‘my delete implement cost:\t${ft.difference(st)}‘);
42 
43   tree = RBTree.from(arr);
44   st = DateTime.now();
45   for (var d in arr) tree.quickDelete(d);
46   ft = DateTime.now();
47   print(‘    linux implement cost:\t${ft.difference(st)}‘);
48 }
49 
50 void traverse(RBTNode r, void func(RBTNode r)) {
51   if (r != null) {
52     traverse(r.left, func);
53     func(r);
54     traverse(r.right, func);
55   }
56 }
57 
58 int _checkIsRBTree(RBTree t) {
59   assert(t.isEmpty || (!t.isEmpty && t.root.isBlack));
60   return _goThrough(t.root);
61 }
62 
63 int _goThrough(RBTNode r) {
64   if (r == null) return 0;
65   assert(r.isBlack || (r.isRed && r.parent.isBlack));
66   var lbh = _goThrough(r.left);
67   var rbh = _goThrough(r.right);
68   assert(lbh == rbh);
69   return lbh + (r.isRed ? 0 : 1);
70 }