yfast::impl::AVL< Node, Compare > Class Template Reference

#include <avl.h>

Inheritance diagram for yfast::impl::AVL< Node, Compare >:

Classes
struct	SplitResult

Public Member Functions
	AVL (Compare cmp=Compare())
	AVL (const AVL &other)=delete
	AVL (AVL &&other) noexcept
unsigned int	height () const
Node *	insert (Node *node)
Node *	remove (Node *node)
SplitResult	split ()
Public Member Functions inherited from yfast::impl::BST< Node, Compare >
	BST (Compare cmp=Compare())
	BST (const BST &other)=delete
	BST (BST &&other) noexcept
unsigned int	size () const
Node *	root () const
Node *	leftmost () const
Node *	rightmost () const
Node *	find (const Key &key) const
Node *	pred (const Key &key, bool strict=false) const
Node *	succ (const Key &key, bool strict=false) const
Node *	insert (Node *node)
RemoveReport	remove (Node *node)

Static Public Member Functions
static AVL	merge (AVL &&subtree1, AVL &&subtree2)
Static Public Member Functions inherited from yfast::impl::BST< Node, Compare >
static Node *	pred (Node *node)
static Node *	succ (Node *node)

Protected Member Functions
	AVL (Node *root, Compare cmp=Compare())
Protected Member Functions inherited from yfast::impl::BST< Node, Compare >
	BST (Node *root, Compare cmp=Compare())
Node *	seek (const Key &key) const

Additional Inherited Members
Public Types inherited from yfast::impl::BST< Node, Compare >
typedef Node::Key	Key
Static Protected Member Functions inherited from yfast::impl::BST< Node, Compare >
static Node *	_leftmost (Node *node)
static Node *	_rightmost (Node *node)
static void	link_left (Node *parent, Node *child)
static void	link_right (Node *parent, Node *child)
static void	update_size (Node *node)
static void	update_size_path (Node *node)
static void	inc_size_path (Node *node)
static void	dec_size_path (Node *node)
Protected Attributes inherited from yfast::impl::BST< Node, Compare >
Compare	_cmp
Node *	_root

Detailed Description

template<typename Node, typename Compare = std::less<typename Node::Key>>
class yfast::impl::AVL< Node, Compare >

AVL tree implementation

Template Parameters

Node	node type
Compare	key comparator

Member Function Documentation

insert()

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

Node * yfast::impl::AVL< Node, Compare >::insert ( Node * node )

inline

insert a new node, replacing node with the equal key (if any)

Parameters

node	node to insert

Returns

node being replaced or nullptr

---

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

• include/yfast/impl/avl.h