red_black_tree的一个实现(c/c++)

本文主要是介绍red_black_tree的一个实现(c/c++)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考《STL源码剖析》, 博客:http://blog.csdn.net/spch2008/article/details/9338923

#ifndef MY_RB_TREE_H
#define MY_RB_TREE_H
#include<iostream>
#include<cstddef>
using namespace std;
#define t_classes <typename Key,typename Value,typename KeyOfValue,typename Compare> 
#define classes <Key,Value,KeyOfValue,Compare> typedef bool rb_tree_color_type;
const rb_tree_color_type rb_tree_red = false;
const rb_tree_color_type rb_tree_black = true;struct rb_tree_node_base{typedef rb_tree_color_type color_type;typedef rb_tree_node_base *base_ptr; color_type color; base_ptr parent; base_ptr left; base_ptr right; static base_ptr minimum(base_ptr x){while(x -> left != NULL) x = x -> left;return x;}static base_ptr maximum(base_ptr x){while(x -> right != NULL) x = x -> right;return x;}base_ptr increment(){base_ptr x = this;if(x->right != NULL){x = x->right;while(x->left != NULL) x = x->left;}else{base_ptr y = x ->parent;while(x == y->right){x = y;y = y->parent;}if(x->right != y) //y != header else return headerx = y;}return x;}base_ptr decrement(){base_ptr x = this;if(x->color == rb_tree_red && x->parent->parent == x){ //x == headerx = x->right;}else if(x ->left != NULL){base_ptr y = x->left;while(y->right != NULL) y = y->right;x = y;}else{base_ptr y = x->parent;while(x == y->left){x = y;y = y->parent;}x = y;}return x;}};template <class Value>
struct __rb_tree_node: public rb_tree_node_base{typedef  __rb_tree_node<Value>* link_type;Value value_field;
};
//KeyOfValue is a function object (functor). In this rb_tree, the value_field contains key and value actrually. We can define the structure of the value_field but we should provide this function object to extract the key from the value_field
//Compare is a function object. if a < b return true else false
template t_classes
class rb_tree{
protected:typedef  void* void_pointer;typedef rb_tree_node_base* base_ptr;typedef __rb_tree_node<Value> rb_tree_node;typedef rb_tree_color_type color_type;public:typedef Key key_type;typedef Value value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type& reference;typedef const value_type& const_reference;typedef rb_tree_node * link_type;typedef size_t size_type;typedef ptrdiff_t difference_type;protected:link_type get_node(){return new rb_tree_node();      }   void put_node(link_type p){delete p;}link_type create_node (const value_type x){link_type node = get_node();//construct(&node->value_field,x);node->value_field = value_type(x);}link_type clone_node(link_type x){link_type  tmp = creat_node(x->value_field);tmp->color = x->color;tmp->left = NULL;tmp->right = NULL;return tmp;}
//if you used alloc and free in c, it should destroy the object first then release the memoryvoid destroy_node(link_type p){put_node(p);}protected:size_type node_count; //number of nodeslink_type header; //this is an extra node for convinience, its parent is the head,left is the left most and right child is the right most nodeCompare key_compare; //a compare function object (functor)link_type& root() const {

这篇关于red_black_tree的一个实现(c/c++)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---