#include <avl_tree_map.h>

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

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

Protected Types
typedef TreeMap< Key, Value, Compare >	Base

typedef BalanceableBinaryTree::Node	Node

Protected Types inherited from dsac::search_tree::TreeMap< Key, Value, Compare >
typedef dsac::map::AbstractMap< Key, Value >	Base

typedef std::pair< Entry, int >	BSTEntry

typedef dsac::tree::LinkedBinaryTree< BSTEntry >	TreeBase

typedef BalanceableBinaryTree::Node	Node

typedef BalanceableBinaryTree::Position	Position

Protected Member Functions
int	height (Node *p) const
	Returns the height of the given node (nullptr is considered 0)

void	recompute_height (Node *p)
	Recomputes the height of the given position based on its children's heights.

bool	is_balanced (Node *p) const
	Returns true if position has balance factor between -1 and +1 inclusive.

Node *	taller_child (Node *p)

void	rebalance (Node *p)

void	rebalance_insert (Node *p)

void	rebalance_delete (Node *p)

int	aux (Node *nd) const

void	set_aux (Node *nd, int value)

Protected Member Functions inherited from dsac::search_tree::TreeMap< Key, Value, Compare >
virtual void	rebalance_access (Node *)

virtual void	rebalance_insert (Node *)

virtual void	rebalance_delete (Node *)

Key	key (Node *nd) const

int	aux (Node *nd) const

void	set_aux (Node *nd, int value)

bool	equals (Key a, Key b) const

Node *	search (Key k) const

abstract_iter_rep *	get_rep (const_iterator iter) const

Protected Member Functions inherited from dsac::map::AbstractMap< Key, Value >
abstract_iter_rep *	get_rep (const_iterator iter) const

void	update_value (const Entry &e, const Value &v)

Protected Attributes
BalanceableBinaryTree	tree

Protected Attributes inherited from dsac::search_tree::TreeMap< Key, Value, Compare >
BalanceableBinaryTree	tree

Compare	less_than

Additional Inherited Members
Public Member Functions inherited from dsac::search_tree::TreeMap< Key, Value, Compare >
	TreeMap ()
	Creates an empty map.

int	size () const
	Returns the number of entries in the map.

const_iterator	begin () const
	Returns a const_iterator to first entry.

const_iterator	end () const
	Returns a const_iterator representing the end.

const_iterator	find (const Key &k) const
	Returns a const_iterator to the entry with a given key, or end() if no such entry exists.

const_iterator	put (const Key &k, const Value &v)

const_iterator	erase (const_iterator loc)
	Removes the entry indicated by the given iterator, and returns const_iterator to next entry in iteration order.

const_iterator	lower_bound (const Key &k) const
	Returns a const_iterator to the first entry with key greater than or equal to k, or end() if no such entry exists.

const_iterator	upper_bound (const Key &k) const
	Returns a const_iterator to the first entry with key strictly greater than k, or end() if no such entry exists.

void	_dump () const
	used for debugging only

bool	empty () const
	Returns true if the map is empty, false otherwise.

bool	erase (const Key &k)

virtual const_iterator	erase (const_iterator loc)=0

Public Member Functions inherited from dsac::map::AbstractMap< Key, Value >
bool	empty () const
	Returns true if the map is empty, false otherwise.

bool	contains (const Key &k) const
	Returns true if the map contains an entry with the given key.

const Value &	at (const Key &k) const

bool	erase (const Key &k)

virtual	~AbstractMap ()

virtual int	size () const =0

virtual const_iterator	begin () const =0

virtual const_iterator	end () const =0

virtual const_iterator	find (const Key &k) const =0

virtual const_iterator	put (const Key &k, const Value &v)=0

virtual const_iterator	erase (const_iterator loc)=0

Static Public Member Functions inherited from dsac::search_tree::TreeMap< Key, Value, Compare >
static void	_dumpNode (Node *p)

static void	_dump (Node *p, int depth)

Static Protected Member Functions inherited from dsac::search_tree::TreeMap< Key, Value, Compare >
static Node *	successor (Node *p)

Member Typedef Documentation

◆ Base

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

typedef TreeMap<Key,Value,Compare> dsac::search_tree::AVLTreeMap< Key, Value, Compare >::Base

protected

◆ Node

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

typedef BalanceableBinaryTree::Node dsac::search_tree::TreeMap< Key, Value, Compare >::Node

protected

Member Function Documentation

◆ aux()

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

int dsac::search_tree::TreeMap< Key, Value, Compare >::aux ( Node * nd ) const

inlineprotected

◆ height()

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

int dsac::search_tree::AVLTreeMap< Key, Value, Compare >::height ( Node * p ) const

inlineprotected

Returns the height of the given node (nullptr is considered 0)

Here is the call graph for this function:

◆ is_balanced()

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

bool dsac::search_tree::AVLTreeMap< Key, Value, Compare >::is_balanced ( Node * p ) const

inlineprotected

Returns true if position has balance factor between -1 and +1 inclusive.

Here is the call graph for this function:

◆ rebalance()

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

void dsac::search_tree::AVLTreeMap< Key, Value, Compare >::rebalance ( Node * p )

inlineprotected

Utility used to rebalance after an insertion or deletion. This traverses the path upward from p, performing a trinode restructuring when imbalance is found, continuing until balance is restored.

Here is the call graph for this function:

◆ rebalance_delete()

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

void dsac::search_tree::AVLTreeMap< Key, Value, Compare >::rebalance_delete ( Node * p )

inlineprotected

Here is the call graph for this function:

◆ rebalance_insert()

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

void dsac::search_tree::AVLTreeMap< Key, Value, Compare >::rebalance_insert ( Node * p )

inlineprotected

Here is the call graph for this function:

◆ recompute_height()

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

void dsac::search_tree::AVLTreeMap< Key, Value, Compare >::recompute_height ( Node * p )

inlineprotected

Recomputes the height of the given position based on its children's heights.

Here is the call graph for this function:

◆ set_aux()

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

void dsac::search_tree::TreeMap< Key, Value, Compare >::set_aux	(	Node *	nd,
		int	value
	)

inlineprotected

◆ taller_child()

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

Node * dsac::search_tree::AVLTreeMap< Key, Value, Compare >::taller_child ( Node * p )

inlineprotected

Returns a child of p with height no smaller than that of the other child In case of tie, chooses the "aligned" child

Here is the call graph for this function:

Field Documentation

◆ tree

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

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

protected

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

dsac/searchtree/avl_tree_map.h

Protected Types

Protected Member Functions

Protected Attributes

Additional Inherited Members

Member Typedef Documentation

◆ Base

◆ Node

Member Function Documentation

◆ aux()

◆ height()

◆ is_balanced()

◆ rebalance()

◆ rebalance_delete()

◆ rebalance_insert()

◆ recompute_height()

◆ set_aux()

◆ taller_child()

Field Documentation

◆ tree