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

佚名 6年前 (2019-03-30) 算法 2033人围观抢沙发百度已收录

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

 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 }