mstl_red_black_tree_base.hpp

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
The young Library
Copyright (c) 2005 by 杨桓

Permission to use, copy, modify, distribute and sell this software for any
purpose is hereby granted without fee, provided that the above copyright
notice appear in all copies and that both that copyright notice and this
permission notice appear in supporting documentation.
The author make no representations about the suitability of this software
for any purpose. It is provided "as is" without express or implied warranty.
*/

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_MINI_STL_RED_BLACK_TREE_BASE_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_RED_BLACK_TREE_BASE_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "mstl_binary_search_tree_base.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

typedef  bool  rb_tree_color;
static const rb_tree_color red = false;
static const rb_tree_color black = true;

struct rb_tree_node_base : public bs_tree_node_base
{
    rb_tree_color color;
};

typedef  rb_tree_node_base*  rb_node_base_ptr;

template< typename Value >
struct rb_tree_node : public rb_tree_node_base
{
    Value data;
};

//-----------------------------------------------------------------------------

def_size_t black_count( const rb_tree_node_base* node,
                        const rb_tree_node_base* root )
{
    if( !node )
        return 0;
    def_size_t count = ( node->color == black ) ? 1 : 0;
    if( node == root )
        return count;
    else
        return ( black_count( static_cast<rb_tree_node_base*>( node->parent ),
                              root ) + count );
}

//-----------------------------------------------------------------------------

inline rb_tree_color& color( bs_tree_node_base* x )
{
    return static_cast<rb_tree_node_base*>(x)->color;
}

//-----------------------------------------------------------------------------

void rb_tree_insert_rebalance( bs_tree_node_base* position,
                               bs_tree_node_base& header )
{
    bs_tree_node_base*& root = header.parent;
    color( position ) = red;

    while( position != root && color( position->parent ) == red )
    {
        //position->parent is left child
        if( position->parent == position->parent->parent->left )
        {
            bs_tree_node_base* runcle = position->parent->parent->right;
            //处理第1种情况:只用更改颜色
            if( runcle && color( runcle ) == red )
            {
                color( runcle ) = black;
                color( position->parent ) = black;
                color( position->parent->parent ) = red;
                position = position->parent->parent;
            }
            else  //right uncle == 0  or  right uncle->color == black
            {
                if( position == position->parent->right )  //处理第2种情况:
                {
                    position = position->parent;
                    root = bs_tree_rotate_left( position, root );
                }
            	color( position->parent ) = black;  //处理第3种情况:将终止循环
            	color( position->parent->parent ) = red;
            	root = bs_tree_rotate_right( position->parent->parent, root );
            }
        }
        else  //position->parent is right child
        {
            bs_tree_node_base* luncle = position->parent->parent->left;
            //处理第1种情况:只用更改颜色
            if( luncle && color( luncle ) == red )
            {
                color( luncle ) = black;
                color( position->parent ) = black;
                color( position->parent->parent ) = red;
                position = position->parent->parent;
            }
            else  //left uncle == 0  or  left uncle->color == black
            {
                if( position == position->parent->left )  //处理第2种情况:
                {
                    position = position->parent;
                    root = bs_tree_rotate_right( position, root );
                }
                color( position->parent ) = black;  //处理第3种情况:将终止循环
                color( position->parent->parent ) = red;
                root = bs_tree_rotate_left( position->parent->parent, root );
            }
        }
    } //end while

    color( root ) = black;
}

//-----------------------------------------------------------------------------

void rb_tree_erase_rebalance( bs_tree_node_base* erase_node,
                              bs_tree_node_base& header )
{
    bs_tree_node_base *successor, *succ_parent, *position;
    bs_tree_node_base*& root = header.parent;
    bs_tree_node_base*& leftmost = header.left;
    bs_tree_node_base*& rightmost = header.right;

    //调整节点
    position = bs_tree_erase_adjust( erase_node,
                                     successor,
                                     succ_parent,
                                     root,
                                     leftmost,
                                     rightmost );

    //调整颜色
    if( position != erase_node )
    {
        data_swap( color( position ), color( erase_node ) );
        position = erase_node;
    }

    if( color( erase_node ) != red )
    {
        while( ( successor != root )
               && ( !successor || color( successor ) == black ) )
        {
            //successor is left child
            if( successor == succ_parent->left )
            {
                bs_tree_node_base* succ_rbrother = succ_parent->right;

                //第1种情况:succ_rbrother->color is red
                if( color( succ_rbrother ) == red )
                {
                    color( succ_rbrother ) = black;
                    color( succ_parent ) = red;
                    root = bs_tree_rotate_left( succ_parent, root );
                    succ_rbrother = succ_parent->right;
                }

                //第2种情况: succ_rbrother->children->color are black
                if( ( !( succ_rbrother->left )
                      || color( succ_rbrother->left ) == black )
                    && ( !( succ_rbrother->right )
                         || color( succ_rbrother->right ) == black ) )
                {
                    color( succ_rbrother ) = red;
                    successor = succ_parent;
                    succ_parent = succ_parent->parent;
                }
                else
                {
                    //第3种情况:succ_rbrother->right->color is black
                    if( !( succ_rbrother->right )
                        || color( succ_rbrother->right ) == black )
                    {
                        if( succ_rbrother->left )
                            color( succ_rbrother->left ) = black;
                        color( succ_rbrother ) = red;
                        root = bs_tree_rotate_right( succ_rbrother, root );
                        succ_rbrother = succ_parent->right;
                    }

                    //第4种情况:succ_rbrother->right->color is red
                    color( succ_rbrother ) = color( succ_parent );
                    color( succ_parent ) = black;
                    if( succ_rbrother->right )
                        color( succ_rbrother->right ) = black;
                    root = bs_tree_rotate_left( succ_parent, root );
                    break;
                }
            } //end if : successor is left child
            else    //successor is right child
            {
                bs_tree_node_base* succ_lbrother = succ_parent->left;
                //第1种情况:succ_lbrother->color is red
                if( color( succ_lbrother ) == red )
                {
                    color( succ_lbrother ) = black;
                    color( succ_parent ) = red;
                    root = bs_tree_rotate_right( succ_parent, root );
                    succ_lbrother = succ_parent->left;
            	}

                //第2种情况:succ_lbrother->children->color are black
                if( ( !( succ_lbrother->right )
                      || color( succ_lbrother->right ) == black )
                    && ( !( succ_lbrother->left )
                         || color( succ_lbrother->left ) == black ) )
                {
                    color( succ_lbrother ) = red;
                    successor = succ_parent;
                    succ_parent = succ_parent->parent;
                }
                else
                {
                    //第3种情况:succ_lbrother->left->color is black
                    if( !( succ_lbrother->left )
                        || color( succ_lbrother->left ) == black )
                    {
                        if( succ_lbrother->right )
                            color( succ_lbrother->right ) = black;
                        color( succ_lbrother ) = red;
                        root = bs_tree_rotate_left( succ_lbrother, root );
                        succ_lbrother = succ_parent->left;
                    }

                    //第4种情况:succ_lbrother->left->color is red
                    color( succ_lbrother ) = color( succ_parent );
                    color( succ_parent ) = black;
                    if( succ_lbrother->left )
                        color( succ_lbrother->left ) = black;
                    root = bs_tree_rotate_right( succ_parent, root );
                    break;
                }
            } //end else : successor is right child
        } //end while

        if( successor )
            color( successor ) = black;
    } //end if
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_END_NAMESPACE__
#endif
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------