之前的文章写了红黑树的实现，因为自己实现了插入和删除的算法。为了测试算法的性能，以及算法的正确性，又写了几个函数，用来检查一棵树是否是红黑树，并进行压力测试，代码如下：

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 }