std::rb_tree_base< TTreeTraits, TAllocator > Template-Klassenreferenz

#include <rb_tree.hpp>

Klassendiagramm für std::rb_tree_base< TTreeTraits, TAllocator >:

Zusammengehörigkeiten von std::rb_tree_base< TTreeTraits, TAllocator >:

Klassen
struct	node

Öffentliche Typen
using	key_type = typename TTreeTraits::key_type
using	value_type = typename TTreeTraits::value_type
using	allocator_type = TAllocator
typedef void(*	TravFunc) (node *n, int left, int depth)
enum	color_e { red, black }
using	size_type = int

Öffentliche Methoden
	rb_tree_base (const allocator_type &allocator=allocator_type())
	~rb_tree_base ()
node *	insert (const value_type &v)
node *	find_node (const key_type &key)
size_type	erase (const key_type &key)
void	erase (node *n)
void	clear ()
void	swap (rb_tree_base &other)
bool	empty () const
size_type	size () const
void	traverse_node (node *n, TravFunc func, int depth)
void	traverse (TravFunc func)
node *	get_begin_node () const
node *	find_next_node (node *n) const
size_type	num_nodes (const node *n) const
void	rebalance (node *new_node)
void	rebalance_after_erase (node *n)
void	validate () const
void	validate_node (node *n) const
void	rotate_left (node *n)
void	rotate_right (node *n)
node *	alloc_node ()
void	free_node (node *n, bool recursive)

Ausführliche Beschreibung

template<class TTreeTraits, class TAllocator = std::allocator>
class std::rb_tree_base< TTreeTraits, TAllocator >

Dokumentation der benutzerdefinierten Datentypen

allocator_type

template<class TTreeTraits, class TAllocator = std::allocator>

using std::rb_tree_base< TTreeTraits, TAllocator >::allocator_type = TAllocator

key_type

template<class TTreeTraits, class TAllocator = std::allocator>

using std::rb_tree_base< TTreeTraits, TAllocator >::key_type = typename TTreeTraits::key_type

size_type

using std::internal::rb_tree_base::size_type = int

inherited

TravFunc

template<class TTreeTraits, class TAllocator = std::allocator>

typedef void(* std::rb_tree_base< TTreeTraits, TAllocator >::TravFunc) (node *n, int left, int depth)

value_type

template<class TTreeTraits, class TAllocator = std::allocator>

using std::rb_tree_base< TTreeTraits, TAllocator >::value_type = typename TTreeTraits::value_type

Dokumentation der Aufzählungstypen

color_e

enum std::internal::rb_tree_base::color_e

inherited

Aufzählungswerte
red
black

                    {
                            red,
                            black
                    };

Beschreibung der Konstruktoren und Destruktoren

rb_tree_base()

template<class TTreeTraits, class TAllocator = std::allocator>

std::rb_tree_base< TTreeTraits, TAllocator >::rb_tree_base ( const allocator_type &  allocator = allocator_type() )

inlineexplicit

            : m_size(0), m_allocator(allocator)
        {
            ms_sentinel.color       = black;
            ms_sentinel.left        = &ms_sentinel;
            ms_sentinel.right       = &ms_sentinel;
            ms_sentinel.parent      = &ms_sentinel;
            m_root                  = &ms_sentinel;
        }

~rb_tree_base()

template<class TTreeTraits, class TAllocator = std::allocator>

std::rb_tree_base< TTreeTraits, TAllocator >::~rb_tree_base ( )

inline

        {
            clear();
        }

Dokumentation der Elementfunktionen

alloc_node()

template<class TTreeTraits, class TAllocator = std::allocator>

node* std::rb_tree_base< TTreeTraits, TAllocator >::alloc_node ( )

inline

        {
            node* mem = (node*)m_allocator.allocate(sizeof(node));
            return new (mem) node();
        }

clear()

template<class TTreeTraits, class TAllocator = std::allocator>

void std::rb_tree_base< TTreeTraits, TAllocator >::clear ( )

inline

        {
            if (!empty())
            {
                free_node(m_root, true);
                m_root = &ms_sentinel;
                m_size = 0;
            }
        }

empty()

template<class TTreeTraits, class TAllocator = std::allocator>

bool std::rb_tree_base< TTreeTraits, TAllocator >::empty ( ) const

inline

        { 
            return m_size == 0; 
        }

erase() [1/2]

template<class TTreeTraits, class TAllocator = std::allocator>

size_type std::rb_tree_base< TTreeTraits, TAllocator >::erase ( const key_type &  key )

inline

        {
            node* toErase = find_node(key);
            size_type erased(0);
            if (toErase != 0)
            {
                erase(toErase);
                erased = 1;
            }
            return erased;
        }

erase() [2/2]

template<class TTreeTraits, class TAllocator = std::allocator>

void std::rb_tree_base< TTreeTraits, TAllocator >::erase ( node *  n )

inline

        {
            assert(m_size > 0);
            node* toErase;

            if (n->left == &ms_sentinel || n->right == &ms_sentinel)
            {
                toErase = n;
            }
            else
            {
                toErase = n->right;
                while (toErase->left != &ms_sentinel)
                    toErase = toErase->left;
            }

            node* eraseChild = (toErase->left != &ms_sentinel ? toErase->left : toErase->right);
            eraseChild->parent = toErase->parent;
            if (toErase->parent != &ms_sentinel)
            {
                if (toErase == toErase->parent->left)
                    toErase->parent->left = eraseChild;
                else
                    toErase->parent->right = eraseChild;
            }
            else  
            {
                m_root = eraseChild;
            }

            n->value = toErase->value;

            if (toErase->color == black)
                rebalance_after_erase(eraseChild);

            free_node(toErase, false);

            validate();
            --m_size;
        }

find_next_node()

template<class TTreeTraits, class TAllocator = std::allocator>

node* std::rb_tree_base< TTreeTraits, TAllocator >::find_next_node ( node *  n ) const

inline

        {
            node* next(0);
            if (n != 0)
            {
                if (n->right != &ms_sentinel)
                {
                    next = n->right;
                    while (next->left != &ms_sentinel)
                        next = next->left;
                }
                else if (n->parent != &ms_sentinel)
                {
                    if (n == n->parent->left)
                        return n->parent;
                    else
                    {
                        next = n;
                        while (next->parent != &ms_sentinel)
                        {
                            if (next == next->parent->right)
                                next = next->parent;
                            else
                            {
                                return next->parent;
                            }
                        }
                        next = 0;
                    }
                }
                else    // 'n' is root.
                {
                    assert(n == m_root);
                }
            }
            return next;
        }

find_node()

template<class TTreeTraits, class TAllocator = std::allocator>

node* std::rb_tree_base< TTreeTraits, TAllocator >::find_node ( const key_type &  key )

inline

        {
            node* iter(m_root);
            while (iter != &ms_sentinel)
            {
                const key_type& iter_key = iter->value.get_key();
                if (iter_key < key)
                        iter = iter->right;
                else if (key < iter_key)
                        iter = iter->left;
                else // key == iter->key
                        return iter;
            }
            return 0;       // not found
        }

free_node()

template<class TTreeTraits, class TAllocator = std::allocator>

void std::rb_tree_base< TTreeTraits, TAllocator >::free_node ( node *  n, bool  recursive  )

inline

        {
            if (recursive)
            {
                if (n->left != &ms_sentinel)
                        free_node(n->left, true);
                if (n->right != &ms_sentinel)
                        free_node(n->right, true);
            }
            if (n != &ms_sentinel)
            {
                n->~node();
                m_allocator.deallocate(n, sizeof(node));
            }
        }

get_begin_node()

template<class TTreeTraits, class TAllocator = std::allocator>

node* std::rb_tree_base< TTreeTraits, TAllocator >::get_begin_node ( ) const

inline

        {
            node* iter(0);
            if (m_root != &ms_sentinel)
            {
                iter = m_root;
                while (iter->left != &ms_sentinel)
                    iter = iter->left;
            }
            return iter;
        }

insert()

template<class TTreeTraits, class TAllocator = std::allocator>

node* std::rb_tree_base< TTreeTraits, TAllocator >::insert ( const value_type &  v )

inline

        {
            node* iter(m_root);
            node* parent(&ms_sentinel);
            while (iter != &ms_sentinel)
            {
                parent = iter;
                if (iter->value.get_key() < v.get_key())
                    iter = iter->right;
                else if (v.get_key() < iter->value.get_key())
                    iter = iter->left;
                else    // v.key == iter->key
                        return iter;
            }

            node* new_node = alloc_node();
            new_node->color = red;
            new_node->value = v;
            new_node->left  = &ms_sentinel;
            new_node->right = &ms_sentinel;
            new_node->parent = parent;
            if (parent != &ms_sentinel)
            {
                if (v.get_key() < parent->value.get_key())
                        parent->left = new_node;
                else
                        parent->right = new_node;
            }
            else    // empty tree
            {
                m_root = new_node;
            }

            rebalance(new_node);
            validate();
            ++m_size;
            return new_node;
        }

num_nodes()

template<class TTreeTraits, class TAllocator = std::allocator>

size_type std::rb_tree_base< TTreeTraits, TAllocator >::num_nodes ( const node *  n ) const

inline

        {
            return n == &ms_sentinel ? 0 : 1 + num_nodes(n->left) + num_nodes(n->right);
        }

rebalance()

template<class TTreeTraits, class TAllocator = std::allocator>

void std::rb_tree_base< TTreeTraits, TAllocator >::rebalance ( node *  new_node )

inline

        {
            assert(new_node->color == red);
            node* iter(new_node);
            while (iter->parent->color == red)
            {
                node* grandparent(iter->parent->parent);
                if (iter->parent == grandparent->left)
                {
                    node* uncle = grandparent->right;

                    if (uncle->color == red)
                    {
                        iter->parent->color = black;
                        uncle->color = black;
                        grandparent->color = red;
                        iter = grandparent;
                    }
                    else 
                    {
                        if (iter == iter->parent->right)
                        {
                            iter = iter->parent;
                            rotate_left(iter);
                        }
                        grandparent = iter->parent->parent;
                        iter->parent->color = black;
                        grandparent->color = red;
                        rotate_right(grandparent);
                    }
                }
                else
                {
                    node* uncle = grandparent->left;
                    if (uncle->color == red)
                    {
                        grandparent->color = red;
                        iter->parent->color = black;
                        uncle->color = black;
                        iter = grandparent;
                    }
                    else
                    {
                        if (iter == iter->parent->left)
                        {
                            iter = iter->parent;
                            rotate_right(iter);
                        }
                        grandparent = iter->parent->parent;
                        iter->parent->color = black;
                        grandparent->color = red;
                        rotate_left(grandparent);
                    }
                }
            }
            m_root->color = black;
        }

rebalance_after_erase()

template<class TTreeTraits, class TAllocator = std::allocator>

void std::rb_tree_base< TTreeTraits, TAllocator >::rebalance_after_erase ( node *  n )

inline

        {
            node* iter(n);
            while (iter != m_root && iter->color == black)
            {
                if (iter == iter->parent->left)
                {
                    node* sibling = iter->parent->right;
                    if (sibling->color == red)
                    {
                        sibling->color = black;
                        iter->parent->color = red;
                        rotate_left(iter->parent);
                        sibling = iter->parent->right;
                    }
                    if (sibling->left->color == black && sibling->right->color == black)
                    {
                        sibling->color = red;
                        iter = iter->parent;
                    }
                    else
                    {
                        if (sibling->right->color == black)
                        {
                            sibling->left->color = black;
                            sibling->color = red;
                            rotate_right(sibling);
                            sibling = iter->parent->right;
                        }
                        sibling->color = iter->parent->color;
                        iter->parent->color = black;
                        sibling->right->color = black;
                        rotate_left(iter->parent);
                        iter = m_root;
                    }
                }
                else    // iter == right child
                {
                    node* sibling = iter->parent->left;
                    if (sibling->color == red)
                    {
                        sibling->color = black;
                        iter->parent->color = red;
                        rotate_right(iter->parent);
                        sibling = iter->parent->left;
                    }
                    if (sibling->left->color == black && sibling->right->color == black)
                    {
                        sibling->color = red;
                        iter = iter->parent;
                    }
                    else
                    {
                        if (sibling->left->color == black)
                        {
                            sibling->right->color = black;
                            sibling->color = red;
                            rotate_left(sibling);
                            sibling = iter->parent->left;
                        }
                        sibling->color = iter->parent->color;
                        iter->parent->color = black;
                        sibling->left->color = black;
                        rotate_right(iter->parent);
                        iter = m_root;
                    }
                }
            }
            iter->color = black;
        }

rotate_left()

template<class TTreeTraits, class TAllocator = std::allocator>

void std::rb_tree_base< TTreeTraits, TAllocator >::rotate_left ( node *  n )

inline

        {
            // Right child's left child becomes n's right child.
            node* rightChild = n->right;
            n->right = rightChild->left;
            if (n->right != &ms_sentinel)
                    n->right->parent = n;

            // n's right child replaces n
            rightChild->parent = n->parent;
            if (n->parent == &ms_sentinel)
            {
                    m_root = rightChild;
            }
            else
            {
                    if (n == n->parent->left)
                            n->parent->left = rightChild;
                    else
                            n->parent->right = rightChild;
            }
            rightChild->left = n;
            n->parent = rightChild;
        }

rotate_right()

template<class TTreeTraits, class TAllocator = std::allocator>

void std::rb_tree_base< TTreeTraits, TAllocator >::rotate_right ( node *  n )

inline

        {
            node* leftChild(n->left);
            n->left = leftChild->right;
            
            if (n->left != &ms_sentinel)
                n->left->parent = n;

            leftChild->parent = n->parent;
            if (n->parent == &ms_sentinel)
            {
                m_root = leftChild;
            }
            else
            {
                // Substitute us in the parent list with left child.
                if (n == n->parent->left)
                        n->parent->left = leftChild;
                else
                        n->parent->right = leftChild;
            }
            leftChild->right = n;
            n->parent = leftChild;
        }

size()

template<class TTreeTraits, class TAllocator = std::allocator>

size_type std::rb_tree_base< TTreeTraits, TAllocator >::size ( ) const

inline

        {
            return m_size;
        }

swap()

template<class TTreeTraits, class TAllocator = std::allocator>

void std::rb_tree_base< TTreeTraits, TAllocator >::swap ( rb_tree_base< TTreeTraits, TAllocator > &  other )

inline

        {
            if (&other != this)
            {
                validate();
                assert(m_allocator == other.m_allocator);
                std::swap(m_root, other.m_root);
                std::swap(m_size, other.m_size);
                validate();
            }
        }

traverse()

template<class TTreeTraits, class TAllocator = std::allocator>

void std::rb_tree_base< TTreeTraits, TAllocator >::traverse ( TravFunc  func )

inline

        {
            int depth(0);
            traverse_node(m_root, func, depth);
        }

traverse_node()

template<class TTreeTraits, class TAllocator = std::allocator>

void std::rb_tree_base< TTreeTraits, TAllocator >::traverse_node ( node *  n, TravFunc  func, int  depth  )

inline

        {
            int left(-1);
            if (n->parent != &ms_sentinel)
            {
                left = n->parent->left == n;
            }
            func(n, left, depth);
            if (n->left != &ms_sentinel)
                traverse_node(n->left, func, depth + 1);
            if (n->right != &ms_sentinel)
                traverse_node(n->right, func, depth + 1);
        }

validate()

template<class TTreeTraits, class TAllocator = std::allocator>

void std::rb_tree_base< TTreeTraits, TAllocator >::validate ( ) const

inline

        {
            assert(m_root->color == black);
            validate_node(m_root);
        }

validate_node()

template<class TTreeTraits, class TAllocator = std::allocator>

void std::rb_tree_base< TTreeTraits, TAllocator >::validate_node ( node *  n ) const

inline

        {
            // - we're child of our parent.
            assert(n->parent == &ms_sentinel ||
                    n->parent->left == n || n->parent->right == n);
            // - both children of red node are black
            if (n->color == red)
            {
                    assert(n->left->color == black);
                    assert(n->right->color == black);
            }
            if (n->left != &ms_sentinel)
                    validate_node(n->left);
            if (n->right != &ms_sentinel)
                    validate_node(n->right);
        }

---

Die Dokumentation für diese Klasse wurde erzeugt aufgrund der Datei:

• include/rb_tree.hpp