rb_tree.h

A Library of Efficient Data Types and Algorithms,封装了常用的ADT及其相关算法的软件包

/*******************************************************************************
+
+  LEDA 4.5  
+
+
+  rb_tree.h
+
+
+  Copyright (c) 1995-2004
+  by Algorithmic Solutions Software GmbH
+  All rights reserved.
+ 
*******************************************************************************/

// $Revision: 1.3 $  $Date: 2004/02/06 11:19:18 $

#ifndef LEDA_RB_TREE_H
#define LEDA_RB_TREE_H

//------------------------------------------------------------------------------
//
// rb_tree:  red black trees (leaf oriented & doubly linked)
//
//           derived from class "bin_tree"
//
// Stefan N"aher (1993)
//
//------------------------------------------------------------------------------



#include <LEDA/basic.h>
#include <LEDA/impl/bin_tree.h>

LEDA_BEGIN_NAMESPACE

 
typedef bin_tree_node* rb_tree_item;

 
// ----------------------------------------------------------------
// class rb_tree
// ----------------------------------------------------------------

class __exportC rb_tree : public bin_tree
{ 
  enum color  { red = 0, black = 1 };

  int         tree_type() const { return LEDA_RB_TREE; }
  const char* tree_name() const { return "Red/Black Tree"; }

  int root_balance() { return black; }
  int node_balance() { return red; }
  int leaf_balance() { return black; }

  void insert_rebal(rb_tree_item);
  void del_rebal(rb_tree_item, rb_tree_item);

public:

  rb_tree() {}
 ~rb_tree() {}

  rb_tree(const rb_tree& T) : bin_tree(T) {}

  rb_tree& operator=(const rb_tree& T) 
  { bin_tree::operator=(T); return *this; }

};

LEDA_END_NAMESPACE

#endif