TTKRedBlackTree< _Key, _Value > Struct Template Reference

The class of the tree modules. More...

#include <ttktree.h>

Classes
struct	iterator
struct	Node

Public Types
using	key_type = _Key
using	value_type = _Value
using	reference = _Value &
using	const_reference = const _Value &

Public Member Functions
reference	operator[] (const key_type &key)
iterator	begin () noexcept
iterator	end () const noexcept
	TTKRedBlackTree ()
	~TTKRedBlackTree ()
void	insert (const key_type &key, const value_type &value) noexcept
void	remove (const key_type &key) noexcept
Node *	find (const key_type &key) const noexcept
bool	empty () const noexcept
void	clear () noexcept
Node *	minimum (Node *x) const noexcept

Private Member Functions
void	rotateLeft (Node *x) noexcept
void	rotateRight (Node *x) noexcept
void	fixInsert (Node *z) noexcept
void	transplant (Node *u, Node *v) noexcept
void	fixDelete (Node *x) noexcept
void	deleteNode (Node *z) noexcept
void	destroy (Node *node) noexcept

Private Attributes
Node *	m_root
Node *	m_nil

Detailed Description

template<typename _Key, typename _Value>
struct TTKRedBlackTree< _Key, _Value >

The class of the tree modules.

Author

Greedysky greed.nosp@m.ysky.nosp@m.@163..nosp@m.com

Definition at line 29 of file ttktree.h.

Member Typedef Documentation

template<typename _Key , typename _Value >

using TTKRedBlackTree< _Key, _Value >::const_reference = const _Value&

Definition at line 35 of file ttktree.h.

template<typename _Key , typename _Value >

using TTKRedBlackTree< _Key, _Value >::key_type = _Key

Definition at line 32 of file ttktree.h.

template<typename _Key , typename _Value >

using TTKRedBlackTree< _Key, _Value >::reference = _Value&

Definition at line 34 of file ttktree.h.

template<typename _Key , typename _Value >

using TTKRedBlackTree< _Key, _Value >::value_type = _Value

Definition at line 33 of file ttktree.h.

Constructor & Destructor Documentation

template<typename _Key , typename _Value >

TTKRedBlackTree< _Key, _Value >::TTKRedBlackTree ( )

inline

Definition at line 442 of file ttktree.h.

References TTKRedBlackTree< _Key, _Value >::Node::m_b, TTKRedBlackTree< _Key, _Value >::Node::m_left, TTKRedBlackTree< _Key, _Value >::Node::m_parent, and TTKRedBlackTree< _Key, _Value >::Node::m_right.

template<typename _Key , typename _Value >

TTKRedBlackTree< _Key, _Value >::~TTKRedBlackTree ( )

inline

Definition at line 450 of file ttktree.h.

Member Function Documentation

template<typename _Key , typename _Value >

iterator TTKRedBlackTree< _Key, _Value >::begin ( )

inlinenoexcept

Definition at line 427 of file ttktree.h.

References TTKRedBlackTree< _Key, _Value >::Node::m_left.

template<typename _Key , typename _Value >

void TTKRedBlackTree< _Key, _Value >::clear ( )

inlinenoexcept

Definition at line 519 of file ttktree.h.

template<typename _Key , typename _Value >

void TTKRedBlackTree< _Key, _Value >::deleteNode ( Node *  z )

inlineprivatenoexcept

Definition at line 276 of file ttktree.h.

References TTKRedBlackTree< _Key, _Value >::Node::m_b, TTKRedBlackTree< _Key, _Value >::Node::m_left, TTKRedBlackTree< _Key, _Value >::Node::m_parent, and TTKRedBlackTree< _Key, _Value >::Node::m_right.

template<typename _Key , typename _Value >

void TTKRedBlackTree< _Key, _Value >::destroy ( Node *  node )

inlineprivatenoexcept

Definition at line 322 of file ttktree.h.

template<typename _Key , typename _Value >

bool TTKRedBlackTree< _Key, _Value >::empty ( ) const

inlinenoexcept

Definition at line 518 of file ttktree.h.

template<typename _Key , typename _Value >

iterator TTKRedBlackTree< _Key, _Value >::end ( ) const

inlinenoexcept

Definition at line 437 of file ttktree.h.

template<typename _Key , typename _Value >

Node* TTKRedBlackTree< _Key, _Value >::find ( const key_type &  key ) const

inlinenoexcept

Definition at line 497 of file ttktree.h.

References key, TTKRedBlackTree< _Key, _Value >::Node::m_key, TTKRedBlackTree< _Key, _Value >::Node::m_left, and TTKRedBlackTree< _Key, _Value >::Node::m_right.

template<typename _Key , typename _Value >

void TTKRedBlackTree< _Key, _Value >::fixDelete ( Node *  x )

inlineprivatenoexcept

Definition at line 201 of file ttktree.h.

References TTKRedBlackTree< _Key, _Value >::Node::m_b, TTKRedBlackTree< _Key, _Value >::Node::m_left, TTKRedBlackTree< _Key, _Value >::Node::m_parent, and TTKRedBlackTree< _Key, _Value >::Node::m_right.

template<typename _Key , typename _Value >

void TTKRedBlackTree< _Key, _Value >::fixInsert ( Node *  z )

inlineprivatenoexcept

Definition at line 129 of file ttktree.h.

References TTKRedBlackTree< _Key, _Value >::Node::m_b, TTKRedBlackTree< _Key, _Value >::Node::m_left, TTKRedBlackTree< _Key, _Value >::Node::m_parent, and TTKRedBlackTree< _Key, _Value >::Node::m_right.

template<typename _Key , typename _Value >

void TTKRedBlackTree< _Key, _Value >::insert ( const key_type &  key, const value_type &  value  )

inlinenoexcept

Definition at line 456 of file ttktree.h.

References key, TTKRedBlackTree< _Key, _Value >::Node::m_key, TTKRedBlackTree< _Key, _Value >::Node::m_left, TTKRedBlackTree< _Key, _Value >::Node::m_parent, and TTKRedBlackTree< _Key, _Value >::Node::m_right.

template<typename _Key , typename _Value >

Node* TTKRedBlackTree< _Key, _Value >::minimum ( Node *  x ) const

inlinenoexcept

Definition at line 525 of file ttktree.h.

References TTKRedBlackTree< _Key, _Value >::Node::m_left.

template<typename _Key , typename _Value >

reference TTKRedBlackTree< _Key, _Value >::operator[] ( const key_type &  key )

inline

Definition at line 333 of file ttktree.h.

References TTKRedBlackTree< _Key, _Value >::Node::m_key, TTKRedBlackTree< _Key, _Value >::Node::m_left, TTKRedBlackTree< _Key, _Value >::Node::m_parent, TTKRedBlackTree< _Key, _Value >::Node::m_right, and TTKRedBlackTree< _Key, _Value >::Node::m_value.

template<typename _Key , typename _Value >

void TTKRedBlackTree< _Key, _Value >::remove ( const key_type &  key )

inlinenoexcept

Definition at line 488 of file ttktree.h.

References key.

template<typename _Key , typename _Value >

void TTKRedBlackTree< _Key, _Value >::rotateLeft ( Node *  x )

inlineprivatenoexcept

Definition at line 73 of file ttktree.h.

References TTKRedBlackTree< _Key, _Value >::Node::m_left, TTKRedBlackTree< _Key, _Value >::Node::m_parent, and TTKRedBlackTree< _Key, _Value >::Node::m_right.

template<typename _Key , typename _Value >

void TTKRedBlackTree< _Key, _Value >::rotateRight ( Node *  x )

inlineprivatenoexcept

Definition at line 101 of file ttktree.h.

References TTKRedBlackTree< _Key, _Value >::Node::m_left, TTKRedBlackTree< _Key, _Value >::Node::m_parent, and TTKRedBlackTree< _Key, _Value >::Node::m_right.

template<typename _Key , typename _Value >

void TTKRedBlackTree< _Key, _Value >::transplant ( Node *  u, Node *  v  )

inlineprivatenoexcept

Definition at line 184 of file ttktree.h.

References TTKRedBlackTree< _Key, _Value >::Node::m_left, TTKRedBlackTree< _Key, _Value >::Node::m_parent, and TTKRedBlackTree< _Key, _Value >::Node::m_right.

Member Data Documentation

template<typename _Key , typename _Value >

Node* TTKRedBlackTree< _Key, _Value >::m_nil

private

Definition at line 71 of file ttktree.h.

template<typename _Key , typename _Value >

Node* TTKRedBlackTree< _Key, _Value >::m_root

private

Definition at line 70 of file ttktree.h.

---

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

• TTKCommon/TTKLibrary/ttktree.h