mstl_binary_search_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_BINARY_SEARCH_TREE_BASE_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_BINARY_SEARCH_TREE_BASE_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "../mstl_define.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

struct bs_tree_node_base
{
    bs_tree_node_base* parent;
    bs_tree_node_base* left;
    bs_tree_node_base* right;
};

typedef  bs_tree_node_base*  bs_node_base_ptr;

inline bs_tree_node_base* min_element( bs_tree_node_base* p )
{
    if( p )
    {
        while( p->left )
            p = p->left;
    }
    return p;
}

inline bs_tree_node_base* max_element( bs_tree_node_base* p )
{
    if( p )
    {
        while( p->right )
            p = p->right;
    }
    return p;
}

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

inline
bs_tree_node_base* bs_tree_iterator_increase( bs_tree_node_base* node )
{
    if( node->right )
    {
        node = node->right;
        while( node->left )
            node = node->left;
    }
    else
    {
        bs_tree_node_base* temp = node->parent;
        while( node == temp->right )
        {
            node = temp;
            temp = temp->parent;
        }
        if( node->right != temp )
            node = temp;
    }
    return node;
}



inline
bs_tree_node_base* bs_tree_iterator_decrease( bs_tree_node_base* node )
{
    bs_tree_node_base* temp;
    if( node->left )
    {
        temp = node->left;
        while( temp->right )
            temp = temp->right;
        node = temp;
    }
    else
    {
        temp = node->parent;
        while( node == temp->left )
    	{
            node = temp;
            temp = temp->parent;
        }
        node = temp;
    }
    return node;
}

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

inline
def_size_t bs_tree_node_height( const bs_tree_node_base* node,
                                const bs_tree_node_base* root )
{
    if( !node || !root )
        return 0;

    def_size_t height = 0;

    while( node != root )
    {
        node = node->parent;
        ++height;
    }
    return height;
}



inline bs_tree_node_base* bs_tree_rotate_left( bs_tree_node_base* position,
                                               bs_tree_node_base* root )
{
    bs_tree_node_base* rchild = position->right;
    position->right = rchild->left;
    if( rchild->left )
        rchild->left->parent = position;
    rchild->parent = position->parent;

    if( position == root )
        root = rchild;
    else if( position == position->parent->left )
        position->parent->left = rchild;
    else
        position->parent->right = rchild;

    rchild->left = position;
    position->parent = rchild;

    return root;
}



inline bs_tree_node_base* bs_tree_rotate_right( bs_tree_node_base* position,
                                                bs_tree_node_base* root )
{
    bs_tree_node_base* lchild = position->left;
    position->left = lchild->right;
    if( lchild->right )
        lchild->right->parent = position;
    lchild->parent = position->parent;

    if( position == root )
        root = lchild;
    else if( position == position->parent->right )
        position->parent->right = lchild;
    else
        position->parent->left = lchild;

    lchild->right = position;
    position->parent = lchild;

    return root;
}

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

inline bs_node_base_ptr bs_tree_erase_adjust( bs_node_base_ptr erase_node,
                                              bs_node_base_ptr& successor,
                                              bs_node_base_ptr& succ_parent,
                                              bs_node_base_ptr& root,
                                              bs_node_base_ptr& leftmost,
                                              bs_node_base_ptr& rightmost )
{
    bs_node_base_ptr position = erase_node;  //position将指向新节点
    successor = NULL_POINTER;
    succ_parent = NULL_POINTER;

    //查找
    if( !(position->left) )  //position有右子树或者没有子树
        successor = position->right;  //successor可能为空
    else
    {
        if( !(position->right) )  //只有左子树
            successor = position->left;
        else  //有左、右子树
        {
            position = position->right;
            while( position->left )
                position = position->left;
            successor = position->right;
        }
    }

    //替换
    if( position != erase_node )
    {
        erase_node->left->parent = position;
        position->left = erase_node->left;
        if( position != erase_node->right )
        {
            succ_parent = position->parent;
            if( successor )
                successor->parent = position->parent;
            position->parent->left = successor;
            position->right = erase_node->right;
            erase_node->right->parent = position;
        }
        else
            succ_parent = position;

        if( root == erase_node )
            root = position;
        else if( erase_node->parent->left == erase_node )
            erase_node->parent->left = position;
        else
            erase_node->parent->right = position;

        position->parent = erase_node->parent;
    }
    else  //position == erase_node
    {
        succ_parent = position->parent;
        if( successor )
            successor->parent = succ_parent;

        if( root == erase_node )
            root = successor;
        else if( erase_node->parent->left == erase_node )
            erase_node->parent->left = successor;
        else
            erase_node->parent->right = successor;

        if( leftmost == erase_node )
        {
            if( !(erase_node->right) )  //leftmost左子树必为空
                leftmost = erase_node->parent;
            else
                leftmost = min_element( successor );
        }

        if( rightmost == erase_node )
        {
            if( !(erase_node->left) )  //rightmost右子树必为空
                rightmost = erase_node->parent;
            else
                rightmost = max_element( successor );
        }
    } //end else

    return position;
}

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