lal::detail::AVL< T >::tree_node Struct Reference

Node of the tree. More...

Public Member Functions
std::size_t	left_size () const noexcept
	Returns the size of the left subtree.
std::size_t	right_size () const noexcept
	Returns the size of the right subtree.
std::size_t	left_counter () const noexcept
	Returns the total occurrences of the left subtree.
std::size_t	right_counter () const noexcept
	Returns the size of the right subtree.
void	update_height_and_balance_factor () noexcept
	Calculate the height and balance factor of this node.
void	update_size () noexcept
	Computes the size of the subtree rooted at this node.
void	update_count () noexcept
	Computes the size of the subtree rooted at this node.
void	update () noexcept
	Updates information of this node.
void	replace_with (tree_node *const n) noexcept
	Replace this node with either its left or right child.

Public Attributes
T	key
	contents of the node
std::size_t	node_counter = 0
	Amount of occurrences of key.
std::size_t	tree_size = 0
	Amount of nodes in the subtree rooted at this node.
std::size_t	tree_counter = 0
	Total number of occurrences in the nodes in the subtree rooted at this node.
std::size_t	height = 0
	Maximum height of the left and right subtrees' height.
int64_t	balance_factor = 0
	Balance factor of a node:
tree_node *	parent = nullptr
	Pointer to the parent of this node.
tree_node *	left = nullptr
	Pointer to the left subtree.
tree_node *	right = nullptr
	Pointer to the right subtree.
char	side = '0'
	Side of this node with respect to its parent.

Detailed Description

template<typename T>
struct lal::detail::AVL< T >::tree_node

Node of the tree.

Member Function Documentation

replace_with()

template<typename T >

void lal::detail::AVL< T >::tree_node::replace_with ( tree_node *const n )

inlinenoexcept

Replace this node with either its left or right child.

Let p := this->parent be the parent of "this" node. That is, the grandparent of parameter n.

If this node is a left child of 'p', make 'n' be the left child of 'p'. If it is a right child of 'p', make 'n' be the right child of 'p'.

Parameters

n	Left or right child of this node.

Postcondition

Reference parent still points to the parent.

If node 'n' is 'this->left', then reference left still points to its left child.

If node 'n' is 'this->right', then reference right still points to its right child.

update()

template<typename T >

void lal::detail::AVL< T >::tree_node::update ( )

inlinenoexcept

Updates information of this node.

• size (see update_size),
• count values (see update_count),
• the height (see update_height_and_balance_factor).

update_count()

template<typename T >

void lal::detail::AVL< T >::tree_node::update_count ( )

inlinenoexcept

Computes the size of the subtree rooted at this node.

Postcondition

Updates the tree_counter member.

update_height_and_balance_factor()

template<typename T >

void lal::detail::AVL< T >::tree_node::update_height_and_balance_factor ( )

inlinenoexcept

Calculate the height and balance factor of this node.

Postcondition

Updates the height and balance_factor members.

update_size()

template<typename T >

void lal::detail::AVL< T >::tree_node::update_size ( )

inlinenoexcept

Computes the size of the subtree rooted at this node.

Postcondition

Updates the tree_size member.

Member Data Documentation

balance_factor

template<typename T >

int64_t lal::detail::AVL< T >::tree_node::balance_factor = 0

Balance factor of a node:

Right subtree's height minus left subtree's height. This value is either -2, -1, 0, 1, 2.

side

template<typename T >

char lal::detail::AVL< T >::tree_node::side = '0'

Side of this node with respect to its parent.

l: this node is a left subtree of its parent, r: this node is a right subtree of its parent, 0: this node is the root. Eq. parent = nullptr

tree_counter

template<typename T >

std::size_t lal::detail::AVL< T >::tree_node::tree_counter = 0

Total number of occurrences in the nodes in the subtree rooted at this node.

Sum of the occurrences at this node plus the sum of the occurrences across all nodes of the left subtree plus the sum of the occurrences across all nodes of the right subtree.

This is not necessarily the same as tree_size.

tree_size

template<typename T >

std::size_t lal::detail::AVL< T >::tree_node::tree_size = 0

Amount of nodes in the subtree rooted at this node.

Number of nodes in the left and right subtrees plus this node.

---

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

• lal/detail/avl.hpp