bintree

Basic data

• Class name: bintree
• Short description: bintree implements a binary tree.
• Has iterator: yes, eight of them. These are: (const_)preorder_iterator, (const_)postorder_iterator, (const_)inorder_iterator, (const_)level_iterator. Iterators have a method getNode() which returns the node in the current position, and can be constructed either by begin() or end(), or via a constructor that receives a node (except (const_)level_iterator).

Template information

This template receives two data types.

• T is the data type of the tags.
• _node (aliased to node) is the node implementation. It's set by default to _regular_bintree_node<T>, which is what's commonly used. Some uses, such as AVL or Red-Black, requires their own node type, so bintree gives the option to manage them accordingly.

_regular_bintree_node methods

All methods are O(1).

Name	Returns	Const	Description
node()	N/A	NO	Constructs a null node.
node(const T& tag)	N/A	NO	Constructs a null node with the tag tag.
node(const node& other)	N/A	NO	Shallow copy constructor.
null()	bool	YES	Whether the node is null or not.
parent()	node	YES	Returns the parent node.
parent(node n)	NO	NO	Sets the parent to n.
left()	node	YES	Returns the left child.
left(node n)	NO	NO	Sets the left child to n.
right()	node	YES	Returns the right child.
right(node n)	NO	NO	Sets the right child to n.
destroy()	NO	NO	Destroys the node, leaving it null.
operator*()	T&	NO	Returns the tag.
operator*()	const T&	YES	Returns the tag.
operator=(const node& other)	node&	NO	Shallow copies the node.
operator==(const node& other)	bool	YES	Whether two nodes are the same.
operator!=(const node& other)	bool	YES	Whether two nodes are different.

bintree methods

Name	Returns	Const	Description	Efficiency (worst case)	Efficiency (mid case)	Efficiency (best case)
bintree()	N/A	NO	Creates a bintree with no root.	O(1)	O(1)	O(1)
bintree(const T& root_tag)	N/A	NO	Creates a bintree with its root's tag set to root_tag.	O(1)	O(1)	O(1)
bintree(const bintree<T, node>& other)	N/A	NO	Creates a deep copy of another tree.	O(n)	O(n)	O(n)
bintree(bintree<T, node>&& other)	N/A	NO	Movement constructor.	O(1)	O(1)	O(1)
root()	node	YES	Returns the root.	O(1)	O(1)	O(1)
root(node n)	NO	NO	Sets the root to n.	O(1)	O(1)	O(1)
size()	size_t	YES	Returns the number of nodes.	O(n)	O(n)	O(n)
empty()	bool	YES	Whether the tree is empty (has no root).	O(1)	O(1)	O(1)
clear()	NO	NO	Destroys all the nodes and leaves it empty.	O(n)	O(n)	O(n)
graft_left(node n, bintree<T, node>& branch)	NO	NO	Grafts branch at the left of n, a node of the current tree, leaving branch empty.	O(n)	O(1)	O(1)
insert_left(node n, const T& tag)	NO	NO	Inserts a new node with tag tag at the left of n.	O(n)	O(1)	O(1)
graft_right(node n, bintree<T, node>& branch)	NO	NO	Grafts branch at the right of n. Leaves branch empty.	O(n)	O(1)	O(1)
insert_right(node n, const T& tag)	NO	NO	Inserts a new node with tag tag at the right of n.	O(n)	O(1)	O(1)
prune_left(node n, bintree<T, node>& dest)	NO	NO	Prunes the left branch of n, which becomes a null tree, and moves it to dest.	O(n)	O(1)	O(1)
prune_right(node n, bintree<T, node>& dest)	NO	NO	Prunes the right branch of n, which becomes a null tree, and moves it to dest.	O(n)	O(1)	O(1)
assign_subtree(const bintree<T, node>& tree, node n)	NO	NO	Replaces the tree with a deep copy of another tree starting with n as the root.	O(n)	O(n)	O(n)
operator=(const bintree<T, node>& other)	bintree<T, node>&	NO	Deep copy.	O(n)	O(n)	O(n)
operator==(const bintree<T, node>& other)	bool	YES	Whether two trees are equivalent.	O(n)	O(n)	O(n)
operator!=(const bintree<T, node>& other)	bool	YES	Whether two trees are different.	O(n)	O(n)	O(n)

NOTE: Methods which in worst case are O(n) and in mid case are O(1) are always O(1) if the destination is null. For instance, insert_right is always O(1) if n.right().null(). In case it's not, it destroys the whole subtree so it's O(n).