vs::_vs_tree_node< _Key, _Comp > Struct Template Reference

Manages all balancing logic and correlating allocations;. More...

#include <vs_tree.h>

Collaboration diagram for vs::_vs_tree_node< _Key, _Comp >:

Public Types
typedef _vs_tree_node< _Key, _Comp > *	_Ptr_type
typedef int	size_type

Public Member Functions
	_vs_tree_node (const _Key &_value)
	_vs_tree_node (const _vs_tree_node &_node)
void	refresh_node_height ()
size_type	node_delta_height ()
_Ptr_type	rebalance ()
_Ptr_type	turnleft ()
_Ptr_type	turnright ()
_Ptr_type	node_insert (const _Key &_value, _Comp comp=_Comp{})
	Fall down recursively, insert and rebalance on the way up. More...

Public Attributes
_Key	value
size_type	height = 0
_Ptr_type	left = nullptr
_Ptr_type	right = nullptr

Detailed Description

template<typename _Key, typename _Comp = std::less<_Key>>
struct vs::_vs_tree_node< _Key, _Comp >

Manages all balancing logic and correlating allocations;.

Definition at line 26 of file vs_tree.h.

Member Typedef Documentation

_Ptr_type

template<typename _Key , typename _Comp = std::less<_Key>>

typedef _vs_tree_node<_Key, _Comp>* vs::_vs_tree_node< _Key, _Comp >::_Ptr_type

Definition at line 30 of file vs_tree.h.

size_type

template<typename _Key , typename _Comp = std::less<_Key>>

typedef int vs::_vs_tree_node< _Key, _Comp >::size_type

Definition at line 31 of file vs_tree.h.

Constructor & Destructor Documentation

_vs_tree_node() [1/2]

template<typename _Key , typename _Comp = std::less<_Key>>

vs::_vs_tree_node< _Key, _Comp >::_vs_tree_node ( const _Key &  _value )

inline

Definition at line 40 of file vs_tree.h.

        : value(_value){ }

_vs_tree_node() [2/2]

template<typename _Key , typename _Comp = std::less<_Key>>

vs::_vs_tree_node< _Key, _Comp >::_vs_tree_node ( const _vs_tree_node< _Key, _Comp > &  _node )

inline

Definition at line 43 of file vs_tree.h.

        : value(_node.value), height(_node.height) { }

Member Function Documentation

node_delta_height()

template<typename _Key , typename _Comp = std::less<_Key>>

size_type vs::_vs_tree_node< _Key, _Comp >::node_delta_height ( )

inline

Definition at line 57 of file vs_tree.h.

        {
            size_type lh = (left ? left->height + 1 : 0);
            size_type rh = (right ? right->height + 1 : 0);
            
            return lh - rh;
        }

node_insert()

template<typename _Key , typename _Comp = std::less<_Key>>

_Ptr_type vs::_vs_tree_node< _Key, _Comp >::node_insert ( const _Key &  _value, _Comp  comp = _Comp{}  )

inline

Fall down recursively, insert and rebalance on the way up.

Definition at line 112 of file vs_tree.h.

                                                          {})
        {
            if (comp(_value, this->value))
            {
                if (left)
                {
                    left = left->node_insert(_value);
                }
                else
                {
                    left = new _vs_tree_node(_value);
                }
            }
            else
            {
                if (right)
                {
                    right = right->node_insert(_value);
                }
                else
                {
                    right = new _vs_tree_node(_value);
                }
            }
 
            return rebalance();
        }

rebalance()

template<typename _Key , typename _Comp = std::less<_Key>>

_Ptr_type vs::_vs_tree_node< _Key, _Comp >::rebalance ( )

inline

Definition at line 66 of file vs_tree.h.

        {
            refresh_node_height();
 
            switch (node_delta_height())
            {
                case 2:
                    if (left->node_delta_height() < 0)
                        left = left->turnleft();
 
                    return turnright();
 
                case -2:
                    if (right->node_delta_height() > 0)
                        right = right->turnright();
                    return turnleft();
                
                default:
                    return this;
            }
        }

refresh_node_height()

template<typename _Key , typename _Comp = std::less<_Key>>

void vs::_vs_tree_node< _Key, _Comp >::refresh_node_height ( )

inline

Definition at line 48 of file vs_tree.h.

        {
            size_type lh = (left ? left->height + 1 : 0);
            size_type rh = (right ? right->height + 1 : 0);
 
            height = (lh > rh ? lh : rh);
        }

turnleft()

template<typename _Key , typename _Comp = std::less<_Key>>

_Ptr_type vs::_vs_tree_node< _Key, _Comp >::turnleft ( )

inline

Definition at line 89 of file vs_tree.h.

                  {
            _Ptr_type child = right;
            right = child->left;
            child->left = this;
            refresh_node_height();
            child->refresh_node_height();
            return child;
        }

turnright()

template<typename _Key , typename _Comp = std::less<_Key>>

_Ptr_type vs::_vs_tree_node< _Key, _Comp >::turnright ( )

inline

Definition at line 99 of file vs_tree.h.

                   {
            _Ptr_type child = left;
            left = child->right;
            child->right = this;
            refresh_node_height();
            child->refresh_node_height();
            return child;
        }

Member Data Documentation

height

template<typename _Key , typename _Comp = std::less<_Key>>

size_type vs::_vs_tree_node< _Key, _Comp >::height = 0

Definition at line 34 of file vs_tree.h.

left

template<typename _Key , typename _Comp = std::less<_Key>>

_Ptr_type vs::_vs_tree_node< _Key, _Comp >::left = nullptr

Definition at line 35 of file vs_tree.h.

right

template<typename _Key , typename _Comp = std::less<_Key>>

_Ptr_type vs::_vs_tree_node< _Key, _Comp >::right = nullptr

Definition at line 36 of file vs_tree.h.

value

template<typename _Key , typename _Comp = std::less<_Key>>

_Key vs::_vs_tree_node< _Key, _Comp >::value

Definition at line 33 of file vs_tree.h.

---

The documentation for this struct was generated from the following file:

• lib/include/vs_tree.h