Inherits ReferenceCountedObject.

Public Member Functions
	BinaryTreeImpl () noexcept

	BinaryTreeImpl (Node *node) noexcept

	BinaryTreeImpl (const BinaryTreeImpl &copy)

bool	isEmpty () const noexcept

Node *	getRoot () noexcept

const Node *	getRoot () const noexcept

void	setRoot (Node *node) noexcept

void	balanceTree ()

	~BinaryTreeImpl ()

Public Member Functions inherited from ReferenceCountedObject
	ReferenceCountedObject () noexcept

	ReferenceCountedObject (const ReferenceCountedObject &copy) noexcept

	ReferenceCountedObject (ReferenceCountedObject &&move) noexcept

ReferenceCountedObject &	operator= (const ReferenceCountedObject &copy) noexcept

ReferenceCountedObject &	operator= (ReferenceCountedObject &&move) noexcept

MemorySize	getNumberOfReferences_INTERNAL () const noexcept

virtual bool	useGarbageCollector () const noexcept

Public Member Functions inherited from DynamicObject
	DynamicObject () noexcept

bool	isValidObject () const noexcept

virtual	~DynamicObject () noexcept(false)

	_COM_AZURE_DEV__BASE__OVERRIDE_ALLOC ()

Static Public Member Functions
static Node *	makeLeft (Node *node, const TYPE &value)

static Node *	makeLeft (Node *node, TYPE &&value)

static Node *	makeRight (Node *node, const TYPE &value)

static Node *	makeRight (Node *node, TYPE &&value)

static Node *	rotateLeft (Node *node)

static Node *	rotateRight (Node *node)

static MemorySize	getSize (const Node *node) noexcept

static void	getNodes (Allocator< Node * > &buffer, Node *node)

static Node *	buildBalancedTree (Span< Node * > span)

static Node *	buildBalancedTree (Allocator< Node * > &buffer)

static Pair< bool, MemorySize >	isBalancedImpl (const Node *node) noexcept

static bool	isBalanced (const Node *node) noexcept

static Pair< MemorySize, MemorySize >	getHowBalancedImpl (const Node *node)

static Pair< MemorySize, MemorySize >	getHowBalanced (const Node *node)

template<class PREDICATE >
static bool	validate (const Node *node, PREDICATE predicate)

Protected Member Functions
Node *	copySubtree (const Node *node)

void	destroySubtree (Node *node)

Constructor & Destructor Documentation

◆ BinaryTreeImpl() [1/3]

template<class TYPE >

BinaryTree< TYPE >::BinaryTreeImpl::BinaryTreeImpl ( )

inlineexplicitnoexcept

Initialize an empty binary tree.

◆ BinaryTreeImpl() [2/3]

template<class TYPE >

BinaryTree< TYPE >::BinaryTreeImpl::BinaryTreeImpl ( Node * node )

inlineexplicitnoexcept

Initialize a binary tree with the specified root node.

Parameters

node	The root node of the tree.

◆ BinaryTreeImpl() [3/3]

template<class TYPE >

BinaryTree< TYPE >::BinaryTreeImpl::BinaryTreeImpl ( const BinaryTreeImpl & copy )

inline

Initialize binary tree from other binary tree.

◆ ~BinaryTreeImpl()

template<class TYPE >

BinaryTree< TYPE >::BinaryTreeImpl::~BinaryTreeImpl ( )

inline

Destroys the binary tree.

Member Function Documentation

◆ balanceTree()

template<class TYPE >

void BinaryTree< TYPE >::BinaryTreeImpl::balanceTree ( )

inline

Builds a balanced tree. But uses buffer and rebuilds entire tree.

◆ buildBalancedTree()

template<class TYPE >

static Node* BinaryTree< TYPE >::BinaryTreeImpl::buildBalancedTree ( Allocator< Node * > & buffer )

inlinestatic

Builds a balanced tree.

◆ copySubtree()

template<class TYPE >

Node* BinaryTree< TYPE >::BinaryTreeImpl::copySubtree ( const Node * node )

inlineprotected

Makes a copy of a subtree specified by the top node.

Parameters

node	The top node of the subtree to be copied.

Returns: The top node of the new subtree.

◆ destroySubtree()

template<class TYPE >

void BinaryTree< TYPE >::BinaryTreeImpl::destroySubtree ( Node * node )

inlineprotected

Destroys the subtree specified by the node. Helper function only used by the destouctor.

Parameters

node	The root node of the subtree to be destroyed.

◆ getHowBalanced()

template<class TYPE >

static Pair<MemorySize, MemorySize> BinaryTree< TYPE >::BinaryTreeImpl::getHowBalanced ( const Node * node )

inlinestatic

Returns how balanced the given tree is.

◆ getHowBalancedImpl()

template<class TYPE >

static Pair<MemorySize, MemorySize> BinaryTree< TYPE >::BinaryTreeImpl::getHowBalancedImpl ( const Node * node )

inlinestatic

Returns how balanced the given tree is.

◆ getNodes()

template<class TYPE >

static void BinaryTree< TYPE >::BinaryTreeImpl::getNodes	(	Allocator< Node * > &	buffer,
		Node *	node
	)

inlinestatic

Gets all the nodes for the given node.

◆ getRoot() [1/2]

template<class TYPE >

const Node* BinaryTree< TYPE >::BinaryTreeImpl::getRoot ( ) const

inlinenoexcept

Returns the root node of the binary tree.

◆ getRoot() [2/2]

template<class TYPE >

Node* BinaryTree< TYPE >::BinaryTreeImpl::getRoot ( )

inlinenoexcept

Returns the root node of the binary tree.

◆ getSize()

template<class TYPE >

static MemorySize BinaryTree< TYPE >::BinaryTreeImpl::getSize ( const Node * node )

inlinestaticnoexcept

Returns the size of the given subtree.

◆ isBalanced()

template<class TYPE >

static bool BinaryTree< TYPE >::BinaryTreeImpl::isBalanced ( const Node * node )

inlinestaticnoexcept

Returns true if the tree is balanced.

◆ isEmpty()

template<class TYPE >

bool BinaryTree< TYPE >::BinaryTreeImpl::isEmpty ( ) const

inlinenoexcept

Returns true if the binary tree is empty.

◆ makeLeft() [1/2]

template<class TYPE >

static Node* BinaryTree< TYPE >::BinaryTreeImpl::makeLeft	(	Node *	node,
		const TYPE &	value
	)

inlinestatic

Makes a left child node.

Returns: The new left child node.

◆ makeLeft() [2/2]

template<class TYPE >

static Node* BinaryTree< TYPE >::BinaryTreeImpl::makeLeft	(	Node *	node,
		TYPE &&	value
	)

inlinestatic

Makes a left child node.

Returns: The new left child node.

◆ makeRight() [1/2]

template<class TYPE >

static Node* BinaryTree< TYPE >::BinaryTreeImpl::makeRight	(	Node *	node,
		const TYPE &	value
	)

inlinestatic

Makes a right child node.

Returns: The new right child node.

◆ makeRight() [2/2]

template<class TYPE >

static Node* BinaryTree< TYPE >::BinaryTreeImpl::makeRight	(	Node *	node,
		TYPE &&	value
	)

inlinestatic

Makes a right child node.

Returns: The new right child node.

◆ rotateLeft()

template<class TYPE >

static Node* BinaryTree< TYPE >::BinaryTreeImpl::rotateLeft ( Node * node )

inlinestatic

Rotates the specified subtree to the left. Raises InvalidNode if the specified node cannot be rotated (i.e. the specified node does not have a right child node).

Parameters

node	The subtree to be rotated.

Returns: The new parent of the subtree.

◆ rotateRight()

template<class TYPE >

static Node* BinaryTree< TYPE >::BinaryTreeImpl::rotateRight ( Node * node )

inlinestatic

Rotates the specified subtree to the right. Raises InvalidNode if the specified node cannot be rotated (i.e. the specified node does not have a left child node).

Parameters

node	The subtree to be rotated.

Returns: The new parent of the subtree.

◆ setRoot()

template<class TYPE >

void BinaryTree< TYPE >::BinaryTreeImpl::setRoot ( Node * node )

inlinenoexcept

Sets the root of the binary tree.

◆ validate()

template<class TYPE >

template<class PREDICATE >

static bool BinaryTree< TYPE >::BinaryTreeImpl::validate	(	const Node *	node,
		PREDICATE	predicate
	)

inlinestatic

Validates the tree for the given predicate.

Public Member Functions

Static Public Member Functions

Protected Member Functions

Constructor & Destructor Documentation

◆ BinaryTreeImpl() [1/3]

◆ BinaryTreeImpl() [2/3]

◆ BinaryTreeImpl() [3/3]

◆ ~BinaryTreeImpl()

Member Function Documentation

◆ balanceTree()

◆ buildBalancedTree()

◆ copySubtree()

◆ destroySubtree()

◆ getHowBalanced()

◆ getHowBalancedImpl()

◆ getNodes()

◆ getRoot() [1/2]

◆ getRoot() [2/2]

◆ getSize()

◆ isBalanced()

◆ isEmpty()

◆ makeLeft() [1/2]

◆ makeLeft() [2/2]

◆ makeRight() [1/2]

◆ makeRight() [2/2]

◆ rotateLeft()

◆ rotateRight()

◆ setRoot()

◆ validate()