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

#include <bst.h>

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

Classes
struct	RemoveReport

Public Types
typedef Node::Key	Key

Public Member Functions
	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 Node *	pred (Node *node)
static Node *	succ (Node *node)

Protected Member Functions
	BST (Node *root, Compare cmp=Compare())
Node *	seek (const Key &key) const

Static Protected Member Functions
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
Compare	_cmp
Node *	_root

Detailed Description

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

Binary search 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::BST< 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/bst.h