---

binary tree sorted and red-black algorithms

A collenction of templated algorithm's in namespace ::binary_tree that manipulate tree's and node's of some binary tree's.

All of the algorithm's work with node_ptr's (and some with tree_ptr's).

  struct node;
  typedef node *node_ptr;

  struct node
  {
    node_ptr prior_left;
    node_ptr next_right;
    node_ptr parent;

    node_ptr swap(node_ptr)
    {
      // typicaly ::binary_tree::basic_swap_node (this, );
      // or       ::binary_tree::rb_swap_node (this, );
      return this;
    }

    #if redblack
      bool red;
    #endif

    #if searchable || redblack
      key_reference key ();
    #endif
  };

  typedef key_type const &key_reference;
  struct less_type
  {
    bool operator () (key_reference low, key_reference high)
    { return low < high;
    }
  };
  // also reqired:
  // typedef std::less<key_type> less_type;

  struct tree;
  typedef tree *tree_node;

  struct tree_t
  {
    node_ptr root;
    node_ptr first_left;
    node_ptr last_right;
  };

---

[Home]