dsac::search_tree::TreeMap< Key, Value, Compare >::BalanceableBinaryTree Class Reference

#include <tree_map.h>

Inheritance diagram for dsac::search_tree::TreeMap< Key, Value, Compare >::BalanceableBinaryTree:

Collaboration diagram for dsac::search_tree::TreeMap< Key, Value, Compare >::BalanceableBinaryTree:

Public Member Functions
Node *	sentinel () const
void	relink (Node *parent, Node *child, bool make_left_child)
void	rotate (Node *x)
Node *	restructure (Node *x)
Public Member Functions inherited from dsac::tree::LinkedBinaryTree< E >
	LinkedBinaryTree ()
	Constructs a tree storing zero elements.
int	size () const
	Returns the number of elements stored in the tree.
bool	empty () const
	Returns true if the tree does not have any elements.
Position	root () const
	Returns a Position for the root (a null Position, if an empty tree)
std::vector< Position >	positions () const
	Returns an inorder sequence of positions.
void	add_root (const E &e=E())
	Creates a root for an empty tree, storing e as the element; should never be called on non-empty tree.
void	add_left (Position p, const E &e)
void	add_right (Position p, const E &e)
void	erase (Position p)
void	attach (Position p, LinkedBinaryTree &left, LinkedBinaryTree &right)
	~LinkedBinaryTree ()
	LinkedBinaryTree (const LinkedBinaryTree &other)
LinkedBinaryTree &	operator= (const LinkedBinaryTree &other)
	LinkedBinaryTree (LinkedBinaryTree &&other)
LinkedBinaryTree &	operator= (LinkedBinaryTree &&other)

Data Fields
friend	TreeMap
Node *	rt

Additional Inherited Members
Protected Attributes inherited from dsac::tree::LinkedBinaryTree< E >
Node *	rt {nullptr}
int	sz {0}

Member Function Documentation

relink()

template<typename Key , typename Value , typename Compare = std::less<Key>>

void dsac::search_tree::TreeMap< Key, Value, Compare >::BalanceableBinaryTree::relink ( Node *  parent, Node *  child, bool  make_left_child  )

inline

restructure()

template<typename Key , typename Value , typename Compare = std::less<Key>>

Node * dsac::search_tree::TreeMap< Key, Value, Compare >::BalanceableBinaryTree::restructure ( Node *  x )

inline

Performs a trinode restructuring of Node x with its parent/grandparent. Returns the Node that becomes the root of the restructured subtree.

Assumes the nodes are in one of the following configurations:

z=a                 z=c           z=a               z=c

/ \ / \ / \ / \ t0 y=b y=b t3 t0 y=c y=a t3 / \ / \ / \ / \ t1 x=c x=a t2 x=b t3 t0 x=b / \ / \ / \ / \ t2 t3 t0 t1 t1 t2 t1 t2

The subtree will be restructured so that the node with key b becomes its root.

      b
    /   \
  a       c
 / \     / \
t0  t1  t2  t3 

Here is the call graph for this function:

rotate()

template<typename Key , typename Value , typename Compare = std::less<Key>>

void dsac::search_tree::TreeMap< Key, Value, Compare >::BalanceableBinaryTree::rotate ( Node *  x )

inline

Rotates non-root node x above its parent. Switches between these configurations, depending on whether x=a or x=b in the following:

    b                  a
   / \                / \
  a  t2             t0   b
 / \                    / \
t0  t1                 t1  t2 

Here is the call graph for this function:

sentinel()

template<typename Key , typename Value , typename Compare = std::less<Key>>

Node * dsac::search_tree::TreeMap< Key, Value, Compare >::BalanceableBinaryTree::sentinel ( ) const

inline

Field Documentation

rt

template<typename Key , typename Value , typename Compare = std::less<Key>>

Node* dsac::tree::LinkedBinaryTree< E >::rt

TreeMap

template<typename Key , typename Value , typename Compare = std::less<Key>>

friend dsac::search_tree::TreeMap< Key, Value, Compare >::BalanceableBinaryTree::TreeMap

---

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

• dsac/searchtree/tree_map.h