Perspectives of a Programmer: Red-Black versus AVL: benchmarks

The results of the benchmarks below are thus because of the fact that my computer does not have enough RAM to take advantage of the amortized constant time of the red-black balancing compared to the logarithmic time of the AVL balancing. The red-black balancing functions are longer, and so the height needs to be very large for it to catch up to the AVL and surpass it. See my blog post on the issue here. In short, for small amounts of data, AVL trees may be prefered. For larger amounts of data, red-black trees work better for insertions and deletions in most cases.

    A few months ago, I was on Wikipedia¹ doing research on AVL trees. It stated that red-black trees beat AVL trees when manipulating the data a lot, but AVL trees are better for look-up-intensive operations. Okay, it may have had a "[citation needed]" out to the side, but I assumed that they knew what they were talking about. Then I compared my final AVL tree to std::set (a red-black tree in my case), and my AVL tree beat the socks off of it! I figured it had to do to the fact that I was inserting the data in order. Maybe red-black trees are better when inserting data in random order. I had to test this, so I spent the next month studying red-black trees, and then it came time for coding one and testing a few things.

Hypothesis:

    AVL trees beat red-black trees when searching and when inserting or erasing data in order, but red-black trees beat AVL trees when inserting or erasing data randomly. This is my hypothesis.

Test:

    The code below is used to test the speed of red-black trees compared to speed of AVL trees. It tests the trees on nine different amounts of data. It is in C++11, and I suggest that it be compiled with level two optimization.

    The AVL tree is based off of code I made a few months ago, and the red-black tree is based off of the code in my red-black tree tutorial².

1    //
2    // AVL versus Red-Black
3    // written by Nathan Belue
4    // April 30, 2012 - May 1, 2012
5    //
6    // This is a comparison of AVL trees to red-black trees. It
7    // tests various scenarios and the speed of each tree in each
8    // scenario.
9    //
10
11
12   /*
13    * Included files
14    */
15
16   #include <chrono>
17   #include <cstdlib>
18   #include <iostream>
19
20   using namespace std;
21
22
23
24   /*
25    * Constants
26    */
27
28
29   namespace {
30
31       //
32       // Set this to how big of intervals to step
33       //
34       const int INTERVAL = 100000;
35
36
37       //
38       // The square root of the maximum random value
39       //
40       const int SQRT_RAND_MAX = 100000;
41
42   }
43
44
45
46   /*
47    * Binary search tree base
48    */
49
50
51       //
52       // Value being stored
53       //
54       typedef int value_type;
55       typedef const value_type & const_reference;
56
57
58       //
59       // More typedefs
60       //
61       typedef size_t size_type;
62
63
64       //
65       // Colors
66       //
67       enum color_type
68       {
69           RED,
70           BLACK
71       };
72
73
74       //
75       // A node of a tree
76       //
77       struct tree_node
78       {
79           value_type data;
80           tree_node * parent;
81           tree_node * left;
82           tree_node * right;
83           union {
84               color_type color;
85               size_type height;
86           };
87       };
88       typedef tree_node * node_ptr;
89       typedef node_ptr * link_type;
90
91
92       //
93       // Binary search tree base class
94       //
95       class binary_search_tree_base
96       {
97       protected:
98           // Data
99           node_ptr _root;
100
101      private:
102          // bst helper functions
103          void _clear( node_ptr );
104
105      protected:
106          // Links
107          typedef node_ptr * node_link;
108          link_type _make_link( node_ptr & );
109          link_type _get_parent_link( node_ptr );
110          node_ptr _link_dest( node_link );
111          void _link_set_dest( node_link, node_ptr );
112          node_ptr _link_origin( node_link );
113
114      protected:
115          // Node functions
116          color_type _node_color( node_ptr );
117          size_type _node_height( node_ptr );
118          node_ptr _node_sibling( node_ptr );
119          node_ptr _node_leftmost( node_ptr );
120
121      protected:
122          // Helper functions
123          void _rotate_clockwise( link_type node );
124          void _rotate_counterclockwise( link_type node );
125          pair<link_type, node_ptr> _get_insert_link(
126              const_reference );
127          node_ptr _replace_and_remove_node( node_ptr );
128
129      public:
130          // Interface
131          binary_search_tree_base();
132          ~binary_search_tree_base();
133          void clear();
134          node_ptr find( const_reference );
135          bool is_empty();
136      };
137
138
139      // Recursively clear the tree
140      void
141      binary_search_tree_base::_clear(
142          node_ptr node )
143      {
144          if( node ) {
145              _clear( node->left );
146              _clear( node->right );
147              delete node;
148          }
149      }
150
151
152      // Convert a node pointer to a link
153      link_type
154      binary_search_tree_base::_make_link(
155          node_ptr & node )
156      {
157          return & node;
158      }
159
160      // Get a node's parent's link to that node
161      link_type
162      binary_search_tree_base::_get_parent_link(
163          node_ptr node )
164      {
165          node_ptr parent = node->parent;
166          if( ! parent )
167              return _make_link( _root );
168          if( parent->left == node )
169              return _make_link( parent->left );
170          return _make_link( parent->right );
171      }
172
173      // Get a link's destination
174      node_ptr
175      binary_search_tree_base::_link_dest(
176          link_type link )
177      {
178          return *link;
179      }
180
181      // Set a link's destination
182      void
183      binary_search_tree_base::_link_set_dest(
184          link_type link, node_ptr dest )
185      {
186          *link = dest;
187      }
188
189      // Get a link's origin
190      node_ptr
191      binary_search_tree_base::_link_origin(
192          node_link link )
193      {
194          return _link_dest(link) -> parent;
195      }
196
197
198      // Get a node's color
199      // Also works for nonexistent imaginary black leaf nodes
200      color_type
201      binary_search_tree_base::_node_color(
202          node_ptr node )
203      {
204          if( node )
205              return node->color;
206          return BLACK;
207      }
208
209      // Get a node's height
210      size_type
211      binary_search_tree_base::_node_height(
212          node_ptr node )
213      {
214          if( node )
215              return node->height;
216          return 0;
217      }
218
219      // Get a node's sibling
220      node_ptr
221      binary_search_tree_base::_node_sibling(
222          node_ptr node )
223      {
224          node_ptr par = node->parent;
225          node_ptr sib = par->left;
226          if( sib == node )
227              sib = par->right;
228          return sib;
229      }
230
231      // Return the leftmost node of a subtree
232      node_ptr
233      binary_search_tree_base::_node_leftmost(
234          node_ptr node )
235      {
236          while( node->left )
237              node = node->left;
238          return node;
239      }
240
241
242      // Rotate about a node clockwise
243      void
244      binary_search_tree_base::_rotate_clockwise(
245          link_type link )
246      {
247          node_ptr node = _link_dest(link);
248          node_ptr left = node->left;
249          node_ptr lright = left->right;
250
251          _link_set_dest( link, left );
252          left->parent = node->parent;
253
254          left->right = node;
255          node->parent = left;
256
257          node->left = lright;
258          if( lright )
259              lright->parent = node;
260      }
261
262      // Rotate about a node counterclockwise
263      void
264      binary_search_tree_base::_rotate_counterclockwise(
265          link_type link )
266      {
267          node_ptr node = _link_dest(link);
268          node_ptr right = node->right;
269          node_ptr rleft = right->left;
270
271          _link_set_dest( link, right );
272          right->parent = node->parent;
273
274          right->left = node;
275          node->parent = right;
276
277          node->right = rleft;
278          if( rleft )
279              rleft->parent = node;
280      }
281
282      // Figure out where to insert a value into the tree
283      // Returns the link and its origin
284      pair<link_type, node_ptr>
285      binary_search_tree_base::_get_insert_link(
286          const_reference value )
287      {
288          link_type where = _make_link(_root);
289          node_ptr origin = nullptr;
290
291          while( _link_dest(where) ) {
292              origin = _link_dest(where);
293              if( value < origin->data )
294                  where = _make_link( origin->left );
295              else if( value > origin->data )
296                  where = _make_link( origin->right );
297              else {
298                  where = nullptr;
299                  break;
300              }
301          }
302
303          return make_pair( where, origin );
304      }
305
306      // Replace and remove node
307      // Returns actual node removed
308      node_ptr
309      binary_search_tree_base::_replace_and_remove_node(
310          node_ptr node )
311      {
312          node_ptr rep = nullptr;
313
314          if( node->left && node->right ) {
315              rep = _node_leftmost( node->right );
316              std::swap( rep->data, node->data );
317              node = rep;
318              rep = nullptr;
319          }
320
321          if( node->left )
322              rep = node->left;
323          else if( node->right )
324              rep = node->right;
325
326          _link_set_dest( _get_parent_link(node), rep );
327          if( rep )
328              rep->parent = node->parent;
329
330          return node;
331      }
332
333
334      // Constructor
335      binary_search_tree_base::binary_search_tree_base() :
336          _root( nullptr )
337      {
338      }
339
340      // Destructor
341      binary_search_tree_base::~binary_search_tree_base()
342      {
343          _clear( _root );
344      }
345
346      // Clear the tree
347      void
348      binary_search_tree_base::clear()
349      {
350          _clear( _root );
351          _root = nullptr;
352      }
353
354      // Find a value in the tree
355      node_ptr
356      binary_search_tree_base::find(
357          const_reference value )
358      {
359          node_ptr node = _root;
360          while( node ) {
361              if( value < node->data )
362                  node = node->left;
363              else if( value > node->data )
364                  node = node->right;
365              else
366                  break;
367          }
368          return node;
369      }
370
371      // Is the tree empty?
372      bool
373      binary_search_tree_base::is_empty()
374      {
375          return _root == nullptr;
376      }
377
378
379
380  /*
381   * AVL tree
382   */
383
384
385      //
386      // AVL tree class
387      //
388      class avl_tree : public binary_search_tree_base
389      {
390      protected:
391          // Node functions
392          int _node_balance( node_ptr );
393      protected:
394          // Helper functions
395          bool _update_height( node_ptr );
396          bool _balance_node( node_ptr );
397          void _balance( node_ptr );
398          int _check( node_ptr );
399      public:
400          // Interface functions
401          void insert( const_reference );
402          void erase( const_reference );
403          void check();
404      };
405
406
407      // Balance of a node
408      int avl_tree::_node_balance( node_ptr node )
409      {
410          return _node_height(node->left)
411              - _node_height(node->right);
412      }
413
414
415      // Update the height of anode
416      // Returns true if height was changed
417      bool avl_tree::_update_height( node_ptr node )
418      {
419          if( ! node )
420              return false;
421          size_type oldH = node->height;
422          size_type leftH = _node_height( node->left );
423          size_type rightH = _node_height( node->right );
424          if( leftH > rightH )
425              node->height = leftH + 1;
426          else
427              node->height = rightH + 1;
428          return ! (oldH == node->height);
429      }
430
431      // Balance at node; return true if balance was done
432      bool avl_tree::_balance_node( node_ptr node )
433      {
434          int bal = _node_balance(node);
435          if( bal == 2 ) {
436              node_link link = _get_parent_link(node);
437              if( _node_balance(node->left) == -1 ) {
438                  _rotate_counterclockwise(
439                      _make_link(node->left) );
440                  _update_height( node->left->left );
441                  _update_height( node->left );
442              }
443              _rotate_clockwise( link );
444              _update_height( node );
445              _update_height( _link_dest(link) );
446              return true;
447          }
448          else if( bal == -2 ) {
449              node_link link = _get_parent_link(node);
450              if( _node_balance(node->right) == 1 ) {
451                  _rotate_clockwise( _make_link(node->right) );
452                  _update_height( node->right->right );
453                  _update_height( node->right );
454              }
455              _rotate_counterclockwise( link );
456              _update_height( node );
457              _update_height( _link_dest(link) );
458              return true;
459          }
460          return false;
461      }
462
463      // Balance the tree
464      void avl_tree::_balance( node_ptr node )
465      {
466          while( node ) {
467              if( _balance_node(node) )
468                  node = node->parent->parent;
469              else if( ! _update_height(node) )
470                  break;
471              else
472                  node = node->parent;
473          }
474      }
475
476      // Check the tree for validity
477      int avl_tree::_check( node_ptr root )
478      {
479
480          if( root == nullptr )
481              return 0;
482
483          node_ptr left = root->left;
484          node_ptr right = root->right;
485
486          // Don't trust nodes' height values
487          int lh = _check(left);
488          int rh = _check(right);
489
490          // Make sure balance factor is not +2 or -2
491          if( lh - rh >= +2 )
492              throw "Right heavy!";
493          else if( lh - rh <= -2 )
494              throw "Left heavy!";
495
496          // Make sure left < right
497          if( left ) {
498              if( left->data > root->data )
499                  throw "Not bst!";
500          }
501          if( right ) {
502              if( right->data < root->data )
503                  throw "Not bst!";
504          }
505
506          // Make sure child->parent points to here
507          if( left )
508              if( left->parent != root )
509                  throw "plink wrong!";
510          if( right )
511              if( right->parent != root )
512                  throw "plink wrong!";
513
514          // Calculate height
515          int height = lh;
516          if( height < rh ) height = rh;
517          ++ height;
518
519          // Return results
520          return height;
521      }
522
523
524      // Insert data into the tree
525      void avl_tree::insert( const_reference value )
526      {
527          pair<link_type, node_ptr> where;
528          where = _get_insert_link( value );
529          if( ! where.first )
530              return;
531
532          node_ptr node = new tree_node;
533          node->data = value;
534          node->height = 1;
535          node->left = node->right = nullptr;
536          node->parent = where.second;
537          _link_set_dest( where.first, node );
538
539          _balance( node->parent );
540      }
541
542      // Erase data from the tree
543      void avl_tree::erase( const_reference value )
544      {
545          node_ptr node = find( value );
546          if( ! node )
547              return;
548          node = _replace_and_remove_node( node );
549          _balance( node->parent );
550          delete node;
551      }
552
553      // Make sure that the tree is valid
554      void avl_tree::check()
555      {
556          _check( _root );
557      }
558
559
560
561  /*
562   * Red-black tree
563   */
564
565      //
566      // Red-black tree class
567      //
568      class rb_tree : public binary_search_tree_base
569      {
570      protected:
571          // Helper functions
572          void _insert_harder_balancing( node_ptr );
573          void _insert_balance( node_ptr );
574          void _erase_harder_balancing_red_parent( node_ptr );
575          void _erase_harder_balancing( node_ptr );
576          void _erase_balance( node_ptr );
577          int _check( node_ptr );
578      public:
579          // Interface functions
580          void insert( const_reference );
581          void erase( const_reference );
582          void check();
583      };
584
585
586      // Balances tree after insertion; handle harder cases
587      void
588      rb_tree::_insert_harder_balancing(
589          node_ptr node )
590      {
591          node_ptr parent = node->parent;
592          node_ptr sibling = _node_sibling( node );
593
594          if( _node_color(sibling) == RED ) {
595              sibling->color = BLACK;
596              parent->color = RED;
597              if( _node_color(parent->parent) == RED ) {
598                  parent->parent->color = BLACK;
599                  _insert_harder_balancing( parent->parent );
600              }
601          }
602
603          else {
604              parent->color = RED;
605              if( node == parent->left ) {
606                  if( _node_color(node->right) == RED ) {
607                      node->color = RED;
608                      node->right->color = BLACK;
609                      _rotate_counterclockwise(
610                          _make_link(parent->left) );
611                  }
612                  _rotate_clockwise(
613                      _get_parent_link(parent) );
614              }
615              else {
616                  if( _node_color(node->left) == RED ) {
617                      node->color = RED;
618                      node->left->color = BLACK;
619                      _rotate_clockwise(
620                          _make_link(parent->right) );
621                  }
622                  _rotate_counterclockwise(
623                      _get_parent_link(parent) );
624              }
625          }
626      }
627
628      // Balance the tree after insertion; easy cases
629      void
630      rb_tree::_insert_balance(
631          node_ptr node )
632      {
633          if( ! node->parent ) {
634              node->color = BLACK;
635          }
636          else if( node->parent->color != BLACK ) {
637              node->parent->color = BLACK;
638              _insert_harder_balancing( node->parent );
639              _root->color = BLACK;
640          }
641      }
642
643      // Balance after erasing; harder; red parent
644      void
645      rb_tree::_erase_harder_balancing_red_parent(
646          node_ptr sibling )
647      {
648          node_ptr parent = sibling->parent;
649          if( sibling == parent->right ) {
650              if( _node_color(sibling->left) == RED ) {
651                  parent->color = BLACK;
652                  _rotate_clockwise( _make_link(parent->right) );
653              }
654              _rotate_counterclockwise( _get_parent_link(parent) );
655          }
656          else {
657              if( _node_color(sibling->right) == RED ) {
658                  parent->color = BLACK;
659                  _rotate_counterclockwise(
660                      _make_link(parent->left) );
661              }
662              _rotate_clockwise( _get_parent_link(parent) );
663          }
664      }
665
666      // Balance after erasing; harder
667      void
668      rb_tree::_erase_harder_balancing(
669          node_ptr sibling )
670      {
671          // Use default rotations and sib->left|right
672          typedef void (rb_tree::*rot_func)( link_type );
673          rot_func rot_clock = & rb_tree::_rotate_clockwise;
674          rot_func rot_counter=& rb_tree::_rotate_counterclockwise;
675          node_ptr sib_left = sibling->left;
676          node_ptr sib_right = sibling->right;
677
678          // One more variable
679          node_ptr parent = sibling->parent;
680
681          // But if sibling is on the left, turn them around.
682          if( sibling == parent->left ) {
683              swap( rot_clock, rot_counter );
684              swap( sib_left, sib_right );
685          }
686
687          if( _node_color(parent) == BLACK ) {
688              if( sibling->color == BLACK ) {
689                  if( _node_color(sib_left) == BLACK
690                      && _node_color(sib_right) == BLACK ) {
691                      sibling->color = RED;
692                      if( parent->parent ) {
693                          _erase_harder_balancing(
694                              _node_sibling(parent) );
695                      }
696                  }
697                  else {
698                      if( _node_color(sib_left) == RED ) {
699                          sib_left->color = BLACK;
700                          (this->*rot_clock)(
701                              _get_parent_link(sibling) );
702                      }
703                      else
704                          sib_right->color = BLACK;
705                      (this->*rot_counter)(
706                          _get_parent_link(parent) );
707                  }
708              }
709              else {
710                  parent->color = RED;
711                  sibling->color = BLACK;
712                  (this->*rot_counter)( _get_parent_link(parent) );
713                  _erase_harder_balancing_red_parent( sib_left );
714              }
715          }
716          else {
717              _erase_harder_balancing_red_parent( sibling );
718          }
719      }
720
721      // Balance the tree after erasing
722      void
723      rb_tree::_erase_balance(
724          node_ptr node )
725      {
726          if( _node_color(node) == BLACK ) {
727              if( node->left )
728                  node->left->color = BLACK;
729              else if( node->right )
730                  node->right->color = BLACK;
731              else if( node->parent ) {
732                  node_ptr sib = node->parent->left;
733                  if( ! sib )
734                      sib = node->parent->right;
735                  _erase_harder_balancing( sib );
736              }
737          }
738      }
739
740      // Check for correctness
741      int
742      rb_tree::_check(
743          node_ptr subtree )
744      {
745          // Imaginary leaf? black height is 1
746          if( ! subtree )
747              return 1;
748
749          node_ptr left = subtree->left;
750          node_ptr right = subtree->right;
751
752          // Black height of both sides must be the same
753          int left_height = _check( left );
754          int right_height = _check( right );
755          if( left_height != right_height )
756              throw "black imbalance!";
757
758          // No two reds in a row
759          if( _node_color(subtree) == RED ) {
760              if( _node_color(left) == RED
761                  || _node_color(right) == RED )
762                  throw "two reds in a row!";
763          }
764
765          // We're black, the height is [left|right]_height + 1
766          else
767              ++ left_height;
768
769          // Make sure that the children's parents are correct
770          if( (left && left->parent != subtree)
771              || (right && right->parent != subtree) )
772              throw "parent pointer wrong!";
773
774          // Return our height
775          return left_height;
776      }
777
778
779      // Insert data into the tree
780      void rb_tree::insert( const_reference value )
781      {
782          pair<link_type, node_ptr> where;
783          where = _get_insert_link( value );
784          if( ! where.first )
785              return;
786
787          node_ptr node = new tree_node;
788          node->data = value;
789          node->color = RED;
790          node->left = node->right = nullptr;
791          node->parent = where.second;
792          _link_set_dest( where.first, node );
793
794          _insert_balance( node );
795      }
796
797      // Erase data from the tree
798      void rb_tree::erase( const_reference value )
799      {
800          node_ptr node = find( value );
801          if( ! node )
802              return;
803          node = _replace_and_remove_node( node );
804          _erase_balance( node );
805          delete node;
806      }
807
808      // Make sure that the tree is valid
809      void rb_tree::check()
810      {
811          if( _node_color(_root) == RED )
812              throw "root is red!";
813          _check( _root );
814      }
815
816
817
818  /*
819   * Random number generation
820   */
821
822
823      //
824      // Random number generator class
825      // It always returns the exact same sequence after being
826      // reset. Also, it never returns a number twice.
827      // Max: SQRT_RAND_MAX
828      // Max Value: SQRT_RAND_MAX*SQRT_RAND_MAX - 1
829      //
830      class random_generator
831      {
832          int * _numbers;
833          int _major_index;
834          int _minor_index;
835      public:
836          // Interface
837          random_generator();
838          ~random_generator();
839          int get();
840          void reset();
841      }
842      random_number;
843
844
845      // Construct a random number generator
846      random_generator::random_generator() :
847          _numbers( new int[SQRT_RAND_MAX] ),
848          _major_index( 0 ),
849          _minor_index( 0 )
850      {
851          for( int i = 0; i != SQRT_RAND_MAX; ++i )
852              _numbers[i] = rand() % SQRT_RAND_MAX;
853      }
854
855      // Destructor
856      random_generator::~random_generator()
857      {
858          delete[] _numbers;
859      }
860
861      // Get a random number
862      int random_generator::get()
863      {
864          int ret = _numbers[_major_index] * SQRT_RAND_MAX
865              + _numbers[_minor_index];
866          ++ _major_index;
867          if( _major_index == SQRT_RAND_MAX ) {
868              _major_index = 0;
869              ++ _minor_index;
870          }
871          return ret;
872      }
873
874      // Reset the generator
875      void random_generator::reset()
876      {
877          _major_index = 0;
878          _minor_index = 0;
879      }
880
881
882
883  /*
884   * Timer
885   */
886
887
888      //
889      // Timer class
890      //
891      class code_timer
892      {
893          // Data
894          chrono::high_resolution_clock::time_point _t;
895      public:
896          void start();
897          void stop();
898      };
899
900
901      // Start the timer
902      void code_timer::start()
903      {
904          _t = chrono::high_resolution_clock::now();
905      }
906
907      // Stop the timer
908      void code_timer::stop()
909      {
910          chrono::microseconds ns
911              = chrono::high_resolution_clock::now() - _t;
912          cout << ns.count() << " microseconds" << endl;
913      }
914
915
916
917  /*
918   * Testing
919   */
920
921      //
922      // Test a tree
923      //
924      template<typename Tree>
925      void test( int count )
926      {
927          Tree tree;
928          code_timer timer;
929          int i;
930
931          cout << "--- Inserting in order ---" << endl;
932          timer.start();
933          for( i = 0; i != count; ++i ) {
934              tree.insert( i );
935  //          tree.check();
936          }
937          timer.stop();
938
939          cout << "--- Searching all afterwards ---" << endl;
940          timer.start();
941          for( i = 0; i != count; ++i ) {
942              tree.find( i );
943          }
944          timer.stop();
945
946          cout << "--- Erasing in order ---" << endl;
947          timer.start();
948          for( i = 0; i != count; ++i ) {
949              tree.erase( i );
950  //          tree.check();
951          }
952          timer.stop();
953
954          cout << "--- Inserting in random ---" << endl;
955          random_number.reset();
956          timer.start();
957          for( i = 0; i != count; ++i ) {
958              tree.insert( random_number.get() );
959  //          tree.check();
960          }
961          timer.stop();
962
963          cout << "--- Searching all afterwards ---" << endl;
964          random_number.reset();
965          timer.start();
966          for( i = 0; i != count; ++i ) {
967              tree.find( random_number.get() );
968          }
969          timer.stop();
970
971          cout << "--- Erasing in random ---" << endl;
972          random_number.reset();
973          timer.start();
974          for( i = 0; i != count; ++i ) {
975              tree.erase( random_number.get() );
976  //          tree.check();
977          }
978          timer.stop();
979      }
980
981
982
983  /*
984   * Main function
985   */
986
987  int main()
988  {
989      try {
990          code_timer timer;
991          timer.start();
992          for( int i = INTERVAL; i < INTERVAL*10; i += INTERVAL ) {
993              cout << endl << "AVL TREE, " << i << endl;
994              test<avl_tree>( i );
995              cout << endl << "RED-BLACK TREE, " << i << endl;
996              test<rb_tree>( i );
997          }
998          cout << endl << "TOTAL PROGRAM RUNNING TIME:" << endl;
999          timer.stop();
1000     }
1001     catch( const char * e ) {
1002         cout << e << endl;
1003     }
1004 };
1005

Results:

The output is as follows.

AVL TREE, 100000
--- Inserting in order ---
17114 microseconds
--- Searching all afterwards ---
6844 microseconds
--- Erasing in order ---
12577 microseconds
--- Inserting in random ---
46528 microseconds
--- Searching all afterwards ---
36651 microseconds
--- Erasing in random ---
36527 microseconds

RED-BLACK TREE, 100000
--- Inserting in order ---
17711 microseconds
--- Searching all afterwards ---
11772 microseconds
--- Erasing in order ---
14304 microseconds
--- Inserting in random ---
31337 microseconds
--- Searching all afterwards ---
27948 microseconds
--- Erasing in random ---
27852 microseconds

AVL TREE, 200000
--- Inserting in order ---
36405 microseconds
--- Searching all afterwards ---
17925 microseconds
--- Erasing in order ---
28306 microseconds
--- Inserting in random ---
70557 microseconds
--- Searching all afterwards ---
55740 microseconds
--- Erasing in random ---
70785 microseconds

RED-BLACK TREE, 200000
--- Inserting in order ---
37151 microseconds
--- Searching all afterwards ---
23832 microseconds
--- Erasing in order ---
30406 microseconds
--- Inserting in random ---
73643 microseconds
--- Searching all afterwards ---
80067 microseconds
--- Erasing in random ---
90427 microseconds

AVL TREE, 300000
--- Inserting in order ---
64436 microseconds
--- Searching all afterwards ---
37097 microseconds
--- Erasing in order ---
53168 microseconds
--- Inserting in random ---
153341 microseconds
--- Searching all afterwards ---
134494 microseconds
--- Erasing in random ---
156761 microseconds

RED-BLACK TREE, 300000
--- Inserting in order ---
69095 microseconds
--- Searching all afterwards ---
46417 microseconds
--- Erasing in order ---
53712 microseconds
--- Inserting in random ---
183088 microseconds
--- Searching all afterwards ---
145537 microseconds
--- Erasing in random ---
141416 microseconds

AVL TREE, 400000
--- Inserting in order ---
87766 microseconds
--- Searching all afterwards ---
50195 microseconds
--- Erasing in order ---
68301 microseconds
--- Inserting in random ---
226314 microseconds
--- Searching all afterwards ---
198646 microseconds
--- Erasing in random ---
241950 microseconds

RED-BLACK TREE, 400000
--- Inserting in order ---
96927 microseconds
--- Searching all afterwards ---
63858 microseconds
--- Erasing in order ---
79998 microseconds
--- Inserting in random ---
282133 microseconds
--- Searching all afterwards ---
206998 microseconds
--- Erasing in random ---
227705 microseconds

AVL TREE, 500000
--- Inserting in order ---
116793 microseconds
--- Searching all afterwards ---
72019 microseconds
--- Erasing in order ---
92173 microseconds
--- Inserting in random ---
343159 microseconds
--- Searching all afterwards ---
279647 microseconds
--- Erasing in random ---
356676 microseconds

RED-BLACK TREE, 500000
--- Inserting in order ---
122283 microseconds
--- Searching all afterwards ---
79625 microseconds
--- Erasing in order ---
93864 microseconds
--- Inserting in random ---
370758 microseconds
--- Searching all afterwards ---
381809 microseconds
--- Erasing in random ---
399800 microseconds

AVL TREE, 600000
--- Inserting in order ---
152210 microseconds
--- Searching all afterwards ---
90795 microseconds
--- Erasing in order ---
114050 microseconds
--- Inserting in random ---
389289 microseconds
--- Searching all afterwards ---
365971 microseconds
--- Erasing in random ---
482464 microseconds

RED-BLACK TREE, 600000
--- Inserting in order ---
155385 microseconds
--- Searching all afterwards ---
101590 microseconds
--- Erasing in order ---
116332 microseconds
--- Inserting in random ---
449050 microseconds
--- Searching all afterwards ---
483760 microseconds
--- Erasing in random ---
530612 microseconds

AVL TREE, 700000
--- Inserting in order ---
181521 microseconds
--- Searching all afterwards ---
108327 microseconds
--- Erasing in order ---
131930 microseconds
--- Inserting in random ---
531229 microseconds
--- Searching all afterwards ---
475930 microseconds
--- Erasing in random ---
524804 microseconds

RED-BLACK TREE, 700000
--- Inserting in order ---
189916 microseconds
--- Searching all afterwards ---
121527 microseconds
--- Erasing in order ---
147624 microseconds
--- Inserting in random ---
662187 microseconds
--- Searching all afterwards ---
545392 microseconds
--- Erasing in random ---
634577 microseconds

AVL TREE, 800000
--- Inserting in order ---
212977 microseconds
--- Searching all afterwards ---
133794 microseconds
--- Erasing in order ---
161690 microseconds
--- Inserting in random ---
617316 microseconds
--- Searching all afterwards ---
543345 microseconds
--- Erasing in random ---
663574 microseconds

RED-BLACK TREE, 800000
--- Inserting in order ---
209157 microseconds
--- Searching all afterwards ---
137076 microseconds
--- Erasing in order ---
164212 microseconds
--- Inserting in random ---
777456 microseconds
--- Searching all afterwards ---
662227 microseconds
--- Erasing in random ---
761854 microseconds

AVL TREE, 900000
--- Inserting in order ---
244121 microseconds
--- Searching all afterwards ---
151686 microseconds
--- Erasing in order ---
178633 microseconds
--- Inserting in random ---
750362 microseconds
--- Searching all afterwards ---
661424 microseconds
--- Erasing in random ---
722931 microseconds

RED-BLACK TREE, 900000
--- Inserting in order ---
256723 microseconds
--- Searching all afterwards ---
162953 microseconds
--- Erasing in order ---
190804 microseconds
--- Inserting in random ---
875096 microseconds
--- Searching all afterwards ---
825393 microseconds
--- Erasing in random ---
852197 microseconds

TOTAL PROGRAM RUNNING TIME:
25471323 microseconds

The above is kind of messy, so I have put the data into a graph to make it easier to see what happens.

Analysis:

    Okay, the results are not even close to what I expected! Why does the AVL tree beat the red-black tree when manipulating random data? And for ordered data, though it is not immediately apparent by the graph, analyzing the data shows the the AVL tree again wins.

    Because the results obtained may be due to the fact that I am much better at coding AVL trees than at coding red-black trees, I ran another test to confirm the accuracy of the results. I have an AVL tree that I coded a few months ago (I do not provide the source), and I tested that against std::set using the same method. The AVL tree again won.

    The results of the operations on ordered data are too close together for comfort, so that needs tested again with larger numbers.

Re-test ordered data:

    In the code, I have commented out the tests on random data, and I have changed the INTERVAL and SQRT_MAX_RAND constants.

1    //
2    // AVL versus Red-Black
3    // written by Nathan Belue
4    // April 30, 2012 - May 1, 2012
5    //
6    // This is a comparison of AVL trees to red-black trees. It
7    // tests various scenarios and the speed of each tree in each
8    // scenario.
9    //
10
11
12   /*
13    * Included files
14    */
15
16   #include <chrono>
17   #include <cstdlib>
18   #include <iostream>
19
20   using namespace std;
21
22
23
24   /*
25    * Constants
26    */
27
28
29   namespace {
30
31       //
32       // Set this to how big of intervals to step
33       //
34       const int INTERVAL = 1000000;
35
36
37       //
38       // The square root of the maximum random value
39       //
40       const int SQRT_RAND_MAX = 1000000;
41
42   }
43
44
45
46   /*
47    * Binary search tree base
48    */
49
50
51       //
52       // Value being stored
53       //
54       typedef int value_type;
55       typedef const value_type & const_reference;
56
57
58       //
59       // More typedefs
60       //
61       typedef size_t size_type;
62
63
64       //
65       // Colors
66       //
67       enum color_type
68       {
69           RED,
70           BLACK
71       };
72
73
74       //
75       // A node of a tree
76       //
77       struct tree_node
78       {
79           value_type data;
80           tree_node * parent;
81           tree_node * left;
82           tree_node * right;
83           union {
84               color_type color;
85               size_type height;
86           };
87       };
88       typedef tree_node * node_ptr;
89       typedef node_ptr * link_type;
90
91
92       //
93       // Binary search tree base class
94       //
95       class binary_search_tree_base
96       {
97       protected:
98           // Data
99           node_ptr _root;
100
101      private:
102          // bst helper functions
103          void _clear( node_ptr );
104
105      protected:
106          // Links
107          typedef node_ptr * node_link;
108          link_type _make_link( node_ptr & );
109          link_type _get_parent_link( node_ptr );
110          node_ptr _link_dest( node_link );
111          void _link_set_dest( node_link, node_ptr );
112          node_ptr _link_origin( node_link );
113
114      protected:
115          // Node functions
116          color_type _node_color( node_ptr );
117          size_type _node_height( node_ptr );
118          node_ptr _node_sibling( node_ptr );
119          node_ptr _node_leftmost( node_ptr );
120
121      protected:
122          // Helper functions
123          void _rotate_clockwise( link_type node );
124          void _rotate_counterclockwise( link_type node );
125          pair<link_type, node_ptr> _get_insert_link(
126              const_reference );
127          node_ptr _replace_and_remove_node( node_ptr );
128
129      public:
130          // Interface
131          binary_search_tree_base();
132          ~binary_search_tree_base();
133          void clear();
134          node_ptr find( const_reference );
135          bool is_empty();
136      };
137
138
139      // Recursively clear the tree
140      void
141      binary_search_tree_base::_clear(
142          node_ptr node )
143      {
144          if( node ) {
145              _clear( node->left );
146              _clear( node->right );
147              delete node;
148          }
149      }
150
151
152      // Convert a node pointer to a link
153      link_type
154      binary_search_tree_base::_make_link(
155          node_ptr & node )
156      {
157          return & node;
158      }
159
160      // Get a node's parent's link to that node
161      link_type
162      binary_search_tree_base::_get_parent_link(
163          node_ptr node )
164      {
165          node_ptr parent = node->parent;
166          if( ! parent )
167              return _make_link( _root );
168          if( parent->left == node )
169              return _make_link( parent->left );
170          return _make_link( parent->right );
171      }
172
173      // Get a link's destination
174      node_ptr
175      binary_search_tree_base::_link_dest(
176          link_type link )
177      {
178          return *link;
179      }
180
181      // Set a link's destination
182      void
183      binary_search_tree_base::_link_set_dest(
184          link_type link, node_ptr dest )
185      {
186          *link = dest;
187      }
188
189      // Get a link's origin
190      node_ptr
191      binary_search_tree_base::_link_origin(
192          node_link link )
193      {
194          return _link_dest(link) -> parent;
195      }
196
197
198      // Get a node's color
199      // Also works for nonexistent imaginary black leaf nodes
200      color_type
201      binary_search_tree_base::_node_color(
202          node_ptr node )
203      {
204          if( node )
205              return node->color;
206          return BLACK;
207      }
208
209      // Get a node's height
210      size_type
211      binary_search_tree_base::_node_height(
212          node_ptr node )
213      {
214          if( node )
215              return node->height;
216          return 0;
217      }
218
219      // Get a node's sibling
220      node_ptr
221      binary_search_tree_base::_node_sibling(
222          node_ptr node )
223      {
224          node_ptr par = node->parent;
225          node_ptr sib = par->left;
226          if( sib == node )
227              sib = par->right;
228          return sib;
229      }
230
231      // Return the leftmost node of a subtree
232      node_ptr
233      binary_search_tree_base::_node_leftmost(
234          node_ptr node )
235      {
236          while( node->left )
237              node = node->left;
238          return node;
239      }
240
241
242      // Rotate about a node clockwise
243      void
244      binary_search_tree_base::_rotate_clockwise(
245          link_type link )
246      {
247          node_ptr node = _link_dest(link);
248          node_ptr left = node->left;
249          node_ptr lright = left->right;
250
251          _link_set_dest( link, left );
252          left->parent = node->parent;
253
254          left->right = node;
255          node->parent = left;
256
257          node->left = lright;
258          if( lright )
259              lright->parent = node;
260      }
261
262      // Rotate about a node counterclockwise
263      void
264      binary_search_tree_base::_rotate_counterclockwise(
265          link_type link )
266      {
267          node_ptr node = _link_dest(link);
268          node_ptr right = node->right;
269          node_ptr rleft = right->left;
270
271          _link_set_dest( link, right );
272          right->parent = node->parent;
273
274          right->left = node;
275          node->parent = right;
276
277          node->right = rleft;
278          if( rleft )
279              rleft->parent = node;
280      }
281
282      // Figure out where to insert a value into the tree
283      // Returns the link and its origin
284      pair<link_type, node_ptr>
285      binary_search_tree_base::_get_insert_link(
286          const_reference value )
287      {
288          link_type where = _make_link(_root);
289          node_ptr origin = nullptr;
290
291          while( _link_dest(where) ) {
292              origin = _link_dest(where);
293              if( value < origin->data )
294                  where = _make_link( origin->left );
295              else if( value > origin->data )
296                  where = _make_link( origin->right );
297              else {
298                  where = nullptr;
299                  break;
300              }
301          }
302
303          return make_pair( where, origin );
304      }
305
306      // Replace and remove node
307      // Returns actual node removed
308      node_ptr
309      binary_search_tree_base::_replace_and_remove_node(
310          node_ptr node )
311      {
312          node_ptr rep = nullptr;
313
314          if( node->left && node->right ) {
315              rep = _node_leftmost( node->right );
316              std::swap( rep->data, node->data );
317              node = rep;
318              rep = nullptr;
319          }
320
321          if( node->left )
322              rep = node->left;
323          else if( node->right )
324              rep = node->right;
325
326          _link_set_dest( _get_parent_link(node), rep );
327          if( rep )
328              rep->parent = node->parent;
329
330          return node;
331      }
332
333
334      // Constructor
335      binary_search_tree_base::binary_search_tree_base() :
336          _root( nullptr )
337      {
338      }
339
340      // Destructor
341      binary_search_tree_base::~binary_search_tree_base()
342      {
343          _clear( _root );
344      }
345
346      // Clear the tree
347      void
348      binary_search_tree_base::clear()
349      {
350          _clear( _root );
351          _root = nullptr;
352      }
353
354      // Find a value in the tree
355      node_ptr
356      binary_search_tree_base::find(
357          const_reference value )
358      {
359          node_ptr node = _root;
360          while( node ) {
361              if( value < node->data )
362                  node = node->left;
363              else if( value > node->data )
364                  node = node->right;
365              else
366                  break;
367          }
368          return node;
369      }
370
371      // Is the tree empty?
372      bool
373      binary_search_tree_base::is_empty()
374      {
375          return _root == nullptr;
376      }
377
378
379
380  /*
381   * AVL tree
382   */
383
384
385      //
386      // AVL tree class
387      //
388      class avl_tree : public binary_search_tree_base
389      {
390      protected:
391          // Node functions
392          int _node_balance( node_ptr );
393      protected:
394          // Helper functions
395          bool _update_height( node_ptr );
396          bool _balance_node( node_ptr );
397          void _balance( node_ptr );
398          int _check( node_ptr );
399      public:
400          // Interface functions
401          void insert( const_reference );
402          void erase( const_reference );
403          void check();
404      };
405
406
407      // Balance of a node
408      int avl_tree::_node_balance( node_ptr node )
409      {
410          return _node_height(node->left)
411              - _node_height(node->right);
412      }
413
414
415      // Update the height of anode
416      // Returns true if height was changed
417      bool avl_tree::_update_height( node_ptr node )
418      {
419          if( ! node )
420              return false;
421          size_type oldH = node->height;
422          size_type leftH = _node_height( node->left );
423          size_type rightH = _node_height( node->right );
424          if( leftH > rightH )
425              node->height = leftH + 1;
426          else
427              node->height = rightH + 1;
428          return ! (oldH == node->height);
429      }
430
431      // Balance at node; return true if balance was done
432      bool avl_tree::_balance_node( node_ptr node )
433      {
434          int bal = _node_balance(node);
435          if( bal == 2 ) {
436              node_link link = _get_parent_link(node);
437              if( _node_balance(node->left) == -1 ) {
438                  _rotate_counterclockwise(
439                      _make_link(node->left) );
440                  _update_height( node->left->left );
441                  _update_height( node->left );
442              }
443              _rotate_clockwise( link );
444              _update_height( node );
445              _update_height( _link_dest(link) );
446              return true;
447          }
448          else if( bal == -2 ) {
449              node_link link = _get_parent_link(node);
450              if( _node_balance(node->right) == 1 ) {
451                  _rotate_clockwise( _make_link(node->right) );
452                  _update_height( node->right->right );
453                  _update_height( node->right );
454              }
455              _rotate_counterclockwise( link );
456              _update_height( node );
457              _update_height( _link_dest(link) );
458              return true;
459          }
460          return false;
461      }
462
463      // Balance the tree
464      void avl_tree::_balance( node_ptr node )
465      {
466          while( node ) {
467              if( _balance_node(node) )
468                  node = node->parent->parent;
469              else if( ! _update_height(node) )
470                  break;
471              else
472                  node = node->parent;
473          }
474      }
475
476      // Check the tree for validity
477      int avl_tree::_check( node_ptr root )
478      {
479
480          if( root == nullptr )
481              return 0;
482
483          node_ptr left = root->left;
484          node_ptr right = root->right;
485
486          // Don't trust nodes' height values
487          int lh = _check(left);
488          int rh = _check(right);
489
490          // Make sure balance factor is not +2 or -2
491          if( lh - rh >= +2 )
492              throw "Right heavy!";
493          else if( lh - rh <= -2 )
494              throw "Left heavy!";
495
496          // Make sure left < right
497          if( left ) {
498              if( left->data > root->data )
499                  throw "Not bst!";
500          }
501          if( right ) {
502              if( right->data < root->data )
503                  throw "Not bst!";
504          }
505
506          // Make sure child->parent points to here
507          if( left )
508              if( left->parent != root )
509                  throw "plink wrong!";
510          if( right )
511              if( right->parent != root )
512                  throw "plink wrong!";
513
514          // Calculate height
515          int height = lh;
516          if( height < rh ) height = rh;
517          ++ height;
518
519          // Return results
520          return height;
521      }
522
523
524      // Insert data into the tree
525      void avl_tree::insert( const_reference value )
526      {
527          pair<link_type, node_ptr> where;
528          where = _get_insert_link( value );
529          if( ! where.first )
530              return;
531
532          node_ptr node = new tree_node;
533          node->data = value;
534          node->height = 1;
535          node->left = node->right = nullptr;
536          node->parent = where.second;
537          _link_set_dest( where.first, node );
538
539          _balance( node->parent );
540      }
541
542      // Erase data from the tree
543      void avl_tree::erase( const_reference value )
544      {
545          node_ptr node = find( value );
546          if( ! node )
547              return;
548          node = _replace_and_remove_node( node );
549          _balance( node->parent );
550          delete node;
551      }
552
553      // Make sure that the tree is valid
554      void avl_tree::check()
555      {
556          _check( _root );
557      }
558
559
560
561  /*
562   * Red-black tree
563   */
564
565      //
566      // Red-black tree class
567      //
568      class rb_tree : public binary_search_tree_base
569      {
570      protected:
571          // Helper functions
572          void _insert_harder_balancing( node_ptr );
573          void _insert_balance( node_ptr );
574          void _erase_harder_balancing_red_parent( node_ptr );
575          void _erase_harder_balancing( node_ptr );
576          void _erase_balance( node_ptr );
577          int _check( node_ptr );
578      public:
579          // Interface functions
580          void insert( const_reference );
581          void erase( const_reference );
582          void check();
583      };
584
585
586      // Balances tree after insertion; handle harder cases
587      void
588      rb_tree::_insert_harder_balancing(
589          node_ptr node )
590      {
591          node_ptr parent = node->parent;
592          node_ptr sibling = _node_sibling( node );
593
594          if( _node_color(sibling) == RED ) {
595              sibling->color = BLACK;
596              parent->color = RED;
597              if( _node_color(parent->parent) == RED ) {
598                  parent->parent->color = BLACK;
599                  _insert_harder_balancing( parent->parent );
600              }
601          }
602
603          else {
604              parent->color = RED;
605              if( node == parent->left ) {
606                  if( _node_color(node->right) == RED ) {
607                      node->color = RED;
608                      node->right->color = BLACK;
609                      _rotate_counterclockwise(
610                          _make_link(parent->left) );
611                  }
612                  _rotate_clockwise(
613                      _get_parent_link(parent) );
614              }
615              else {
616                  if( _node_color(node->left) == RED ) {
617                      node->color = RED;
618                      node->left->color = BLACK;
619                      _rotate_clockwise(
620                          _make_link(parent->right) );
621                  }
622                  _rotate_counterclockwise(
623                      _get_parent_link(parent) );
624              }
625          }
626      }
627
628      // Balance the tree after insertion; easy cases
629      void
630      rb_tree::_insert_balance(
631          node_ptr node )
632      {
633          if( ! node->parent ) {
634              node->color = BLACK;
635          }
636          else if( node->parent->color != BLACK ) {
637              node->parent->color = BLACK;
638              _insert_harder_balancing( node->parent );
639              _root->color = BLACK;
640          }
641      }
642
643      // Balance after erasing; harder; red parent
644      void
645      rb_tree::_erase_harder_balancing_red_parent(
646          node_ptr sibling )
647      {
648          node_ptr parent = sibling->parent;
649          if( sibling == parent->right ) {
650              if( _node_color(sibling->left) == RED ) {
651                  parent->color = BLACK;
652                  _rotate_clockwise( _make_link(parent->right) );
653              }
654              _rotate_counterclockwise( _get_parent_link(parent) );
655          }
656          else {
657              if( _node_color(sibling->right) == RED ) {
658                  parent->color = BLACK;
659                  _rotate_counterclockwise(
660                      _make_link(parent->left) );
661              }
662              _rotate_clockwise( _get_parent_link(parent) );
663          }
664      }
665
666      // Balance after erasing; harder
667      void
668      rb_tree::_erase_harder_balancing(
669          node_ptr sibling )
670      {
671          // Use default rotations and sib->left|right
672          typedef void (rb_tree::*rot_func)( link_type );
673          rot_func rot_clock = & rb_tree::_rotate_clockwise;
674          rot_func rot_counter=& rb_tree::_rotate_counterclockwise;
675          node_ptr sib_left = sibling->left;
676          node_ptr sib_right = sibling->right;
677
678          // One more variable
679          node_ptr parent = sibling->parent;
680
681          // But if sibling is on the left, turn them around.
682          if( sibling == parent->left ) {
683              swap( rot_clock, rot_counter );
684              swap( sib_left, sib_right );
685          }
686
687          if( _node_color(parent) == BLACK ) {
688              if( sibling->color == BLACK ) {
689                  if( _node_color(sib_left) == BLACK
690                      && _node_color(sib_right) == BLACK ) {
691                      sibling->color = RED;
692                      if( parent->parent ) {
693                          _erase_harder_balancing(
694                              _node_sibling(parent) );
695                      }
696                  }
697                  else {
698                      if( _node_color(sib_left) == RED ) {
699                          sib_left->color = BLACK;
700                          (this->*rot_clock)(
701                              _get_parent_link(sibling) );
702                      }
703                      else
704                          sib_right->color = BLACK;
705                      (this->*rot_counter)(
706                          _get_parent_link(parent) );
707                  }
708              }
709              else {
710                  parent->color = RED;
711                  sibling->color = BLACK;
712                  (this->*rot_counter)( _get_parent_link(parent) );
713                  _erase_harder_balancing_red_parent( sib_left );
714              }
715          }
716          else {
717              _erase_harder_balancing_red_parent( sibling );
718          }
719      }
720
721      // Balance the tree after erasing
722      void
723      rb_tree::_erase_balance(
724          node_ptr node )
725      {
726          if( _node_color(node) == BLACK ) {
727              if( node->left )
728                  node->left->color = BLACK;
729              else if( node->right )
730                  node->right->color = BLACK;
731              else if( node->parent ) {
732                  node_ptr sib = node->parent->left;
733                  if( ! sib )
734                      sib = node->parent->right;
735                  _erase_harder_balancing( sib );
736              }
737          }
738      }
739
740      // Check for correctness
741      int
742      rb_tree::_check(
743          node_ptr subtree )
744      {
745          // Imaginary leaf? black height is 1
746          if( ! subtree )
747              return 1;
748
749          node_ptr left = subtree->left;
750          node_ptr right = subtree->right;
751
752          // Black height of both sides must be the same
753          int left_height = _check( left );
754          int right_height = _check( right );
755          if( left_height != right_height )
756              throw "black imbalance!";
757
758          // No two reds in a row
759          if( _node_color(subtree) == RED ) {
760              if( _node_color(left) == RED
761                  || _node_color(right) == RED )
762                  throw "two reds in a row!";
763          }
764
765          // We're black, the height is [left|right]_height + 1
766          else
767              ++ left_height;
768
769          // Make sure that the children's parents are correct
770          if( (left && left->parent != subtree)
771              || (right && right->parent != subtree) )
772              throw "parent pointer wrong!";
773
774          // Return our height
775          return left_height;
776      }
777
778
779      // Insert data into the tree
780      void rb_tree::insert( const_reference value )
781      {
782          pair<link_type, node_ptr> where;
783          where = _get_insert_link( value );
784          if( ! where.first )
785              return;
786
787          node_ptr node = new tree_node;
788          node->data = value;
789          node->color = RED;
790          node->left = node->right = nullptr;
791          node->parent = where.second;
792          _link_set_dest( where.first, node );
793
794          _insert_balance( node );
795      }
796
797      // Erase data from the tree
798      void rb_tree::erase( const_reference value )
799      {
800          node_ptr node = find( value );
801          if( ! node )
802              return;
803          node = _replace_and_remove_node( node );
804          _erase_balance( node );
805          delete node;
806      }
807
808      // Make sure that the tree is valid
809      void rb_tree::check()
810      {
811          if( _node_color(_root) == RED )
812              throw "root is red!";
813          _check( _root );
814      }
815
816
817
818  /*
819   * Random number generation
820   */
821
822
823      //
824      // Random number generator class
825      // It always returns the exact same sequence after being
826      // reset. Also, it never returns a number twice.
827      // Max: SQRT_RAND_MAX
828      // Max Value: SQRT_RAND_MAX*SQRT_RAND_MAX - 1
829      //
830      class random_generator
831      {
832          int * _numbers;
833          int _major_index;
834          int _minor_index;
835      public:
836          // Interface
837          random_generator();
838          ~random_generator();
839          int get();
840          void reset();
841      }
842      random_number;
843
844
845      // Construct a random number generator
846      random_generator::random_generator() :
847          _numbers( new int[SQRT_RAND_MAX] ),
848          _major_index( 0 ),
849          _minor_index( 0 )
850      {
851          for( int i = 0; i != SQRT_RAND_MAX; ++i )
852              _numbers[i] = rand() % SQRT_RAND_MAX;
853      }
854
855      // Destructor
856      random_generator::~random_generator()
857      {
858          delete[] _numbers;
859      }
860
861      // Get a random number
862      int random_generator::get()
863      {
864          int ret = _numbers[_major_index] * SQRT_RAND_MAX
865              + _numbers[_minor_index];
866          ++ _major_index;
867          if( _major_index == SQRT_RAND_MAX ) {
868              _major_index = 0;
869              ++ _minor_index;
870          }
871          return ret;
872      }
873
874      // Reset the generator
875      void random_generator::reset()
876      {
877          _major_index = 0;
878          _minor_index = 0;
879      }
880
881
882
883  /*
884   * Timer
885   */
886
887
888      //
889      // Timer class
890      //
891      class code_timer
892      {
893          // Data
894          chrono::high_resolution_clock::time_point _t;
895      public:
896          void start();
897          void stop();
898      };
899
900
901      // Start the timer
902      void code_timer::start()
903      {
904          _t = chrono::high_resolution_clock::now();
905      }
906
907      // Stop the timer
908      void code_timer::stop()
909      {
910          chrono::microseconds ns
911              = chrono::high_resolution_clock::now() - _t;
912          cout << ns.count() << " microseconds" << endl;
913      }
914
915
916
917  /*
918   * Testing
919   */
920
921      //
922      // Test a tree
923      //
924      template<typename Tree>
925      void test( int count )
926      {
927          Tree tree;
928          code_timer timer;
929          int i;
930
931          cout << "--- Inserting in order ---" << endl;
932          timer.start();
933          for( i = 0; i != count; ++i ) {
934              tree.insert( i );
935  //          tree.check();
936          }
937          timer.stop();
938
939          cout << "--- Searching all afterwards ---" << endl;
940          timer.start();
941          for( i = 0; i != count; ++i ) {
942              tree.find( i );
943          }
944          timer.stop();
945
946          cout << "--- Erasing in order ---" << endl;
947          timer.start();
948          for( i = 0; i != count; ++i ) {
949              tree.erase( i );
950  //          tree.check();
951          }
952          timer.stop();
953  /*
954          cout << "--- Inserting in random ---" << endl;
955          random_number.reset();
956          timer.start();
957          for( i = 0; i != count; ++i ) {
958              tree.insert( random_number.get() );
959  //          tree.check();
960          }
961          timer.stop();
962
963          cout << "--- Searching all afterwards ---" << endl;
964          random_number.reset();
965          timer.start();
966          for( i = 0; i != count; ++i ) {
967              tree.find( random_number.get() );
968          }
969          timer.stop();
970
971          cout << "--- Erasing in random ---" << endl;
972          random_number.reset();
973          timer.start();
974          for( i = 0; i != count; ++i ) {
975              tree.erase( random_number.get() );
976  //          tree.check();
977          }
978          timer.stop();*/
979      }
980
981
982
983  /*
984   * Main function
985   */
986
987  int main()
988  {
989      try {
990          code_timer timer;
991          timer.start();
992          for( int i = INTERVAL; i < INTERVAL*10; i += INTERVAL ) {
993              cout << endl << "AVL TREE, " << i << endl;
994              test<avl_tree>( i );
995              cout << endl << "RED-BLACK TREE, " << i << endl;
996              test<rb_tree>( i );
997          }
998          cout << endl << "TOTAL PROGRAM RUNNING TIME:" << endl;
999          timer.stop();
1000     }
1001     catch( const char * e ) {
1002         cout << e << endl;
1003     }
1004 };
1005

Results:

The output:

AVL TREE, 1000000
--- Inserting in order ---
212706 microseconds
--- Searching all afterwards ---
118500 microseconds
--- Erasing in order ---
144221 microseconds

RED-BLACK TREE, 1000000
--- Inserting in order ---
253050 microseconds
--- Searching all afterwards ---
128795 microseconds
--- Erasing in order ---
177536 microseconds

AVL TREE, 2000000
--- Inserting in order ---
444879 microseconds
--- Searching all afterwards ---
297211 microseconds
--- Erasing in order ---
324151 microseconds

RED-BLACK TREE, 2000000
--- Inserting in order ---
578794 microseconds
--- Searching all afterwards ---
308073 microseconds
--- Erasing in order ---
394074 microseconds

AVL TREE, 3000000
--- Inserting in order ---
697510 microseconds
--- Searching all afterwards ---
466717 microseconds
--- Erasing in order ---
510471 microseconds

RED-BLACK TREE, 3000000
--- Inserting in order ---
901346 microseconds
--- Searching all afterwards ---
502883 microseconds
--- Erasing in order ---
643791 microseconds

AVL TREE, 4000000
--- Inserting in order ---
936047 microseconds
--- Searching all afterwards ---
632872 microseconds
--- Erasing in order ---
722934 microseconds

RED-BLACK TREE, 4000000
--- Inserting in order ---
1226726 microseconds
--- Searching all afterwards ---
667614 microseconds
--- Erasing in order ---
875269 microseconds

AVL TREE, 5000000
--- Inserting in order ---
1178134 microseconds
--- Searching all afterwards ---
823000 microseconds
--- Erasing in order ---
921291 microseconds

RED-BLACK TREE, 5000000
--- Inserting in order ---
1575743 microseconds
--- Searching all afterwards ---
861085 microseconds
--- Erasing in order ---
1171663 microseconds

AVL TREE, 6000000
--- Inserting in order ---
1441767 microseconds
--- Searching all afterwards ---
1003871 microseconds
--- Erasing in order ---
1143342 microseconds

RED-BLACK TREE, 6000000
--- Inserting in order ---
1918461 microseconds
--- Searching all afterwards ---
1055850 microseconds
--- Erasing in order ---
1437743 microseconds

AVL TREE, 7000000
--- Inserting in order ---
1710106 microseconds
--- Searching all afterwards ---
1205899 microseconds
--- Erasing in order ---
1391172 microseconds

RED-BLACK TREE, 7000000
--- Inserting in order ---
2292231 microseconds
--- Searching all afterwards ---
1235369 microseconds
--- Erasing in order ---
1623608 microseconds

AVL TREE, 8000000
--- Inserting in order ---
1978473 microseconds
--- Searching all afterwards ---
1379757 microseconds
--- Erasing in order ---
1592189 microseconds

RED-BLACK TREE, 8000000
--- Inserting in order ---
2691522 microseconds
--- Searching all afterwards ---
1446219 microseconds
--- Erasing in order ---
1907239 microseconds

AVL TREE, 9000000
--- Inserting in order ---
2284785 microseconds
--- Searching all afterwards ---
1588427 microseconds
--- Erasing in order ---
1818956 microseconds

RED-BLACK TREE, 9000000
--- Inserting in order ---
2987662 microseconds
--- Searching all afterwards ---
1648480 microseconds
--- Erasing in order ---
2160594 microseconds

TOTAL PROGRAM RUNNING TIME:
59642916 microseconds

The graph:

Analysis:

    As you can see, the AVL tree even beats the red-black tree for ordered data in all cases (though only slightly for searching). Again, I reran this test for my old AVL tree and std::set, and I got similar results.

Conclusions:

    Per all of the above data, the AVL tree beats the red-black tree in every area tested. I fear, however, that my results may be incorrect. First, no sources (including my hypothesis) have stated that AVL trees always beat red-black trees. Second, my compiler³ uses a red-black tree for its std::set implementation; why would it do that if AVL trees are superior?

    While my tests have shown that AVL trees are better than red-black trees in inserting, deleting, and finding data either in order or randomly, I believe that more tests and studies need to be done to conclusively state one way or another where AVL trees are superior to red-black trees and vice-versa.

Footnotes and references:

1 - AVL tree. Wikipedia. Spring 2012. <http://en.wikipedia.org/wiki/AVL_tree>.
2 - My tutorial on red-black trees. <http://nathanbelue.blogspot.com/2012/04/red-black-trees.html>.
3 - g++ version 4.6.1

Update May 3, 2012

    I spent the day running tests. I tested the trees above along with my personal AVL and red-black trees, std::set from g++ 4.6.1, and a third-party's tree. I tested inserting in ascending order, inserting in descending order, inserting using rand(), inserting using the random number generator above, and inserting using a random number generator that guarantees every number to be unique. I tested with data sets in the tens of thousands, hundreds of thousands, and millions. I inserted elements, deleted 90% of the elements, then inserted them back a few times. I tried different compiler optimizations. Heck, I even tried allocating memory for the trees beforehand so that memory allocation wouldn't be in the equation! Oh, and I made darn certain there was no noise, and I ran the tests several times.

    In every single case, the AVL trees outperformed the red-black trees. The closest that the red-black trees ever came to beating the AVL trees was after inserting hundreds of thousands of unique random numbers (the results for this were too close to comfortably call the winner definitely). At least we know now that for up to five million nodes, the AVL tree is faster than the red-black tree.

    I would like to thank #algorithms on freenode (especially wefawa) for taking the time (quite a bit of time) to consider this problem and help think up tests to run. There is one test that was not run because it was not figured out how to do it (try to maintain a Fibonacci tree), but I do not believe that it is likely to be found in any applications. The next step is to go beyond the 1 GB limit of my computer, and that requires some math. I will post again soon with the final verdict.

Perspectives of a Programmer

Tuesday, May 1, 2012

Red-Black versus AVL: benchmarks

1 comment: