Binary Tree¶

1

import "std/data/binary-tree";

Node<T> struct¶

Node of a BinaryTree

Constructors¶

ctor¶

1

public p Node.ctor(const T& value, heap Node<T>* childLeft = nil<heap Node<T>*>, heap Node<T>* childRight = nil<heap Node<T>*>)

Construct a binary tree node holding the given value and optional children

Parameters

BinaryTree<T> struct¶

A binary tree is a data structure to fasten up search speeds. Binary trees (when balanced) can be searched in O(log n). Insert operations, on the other hand, are rather slow, because the tree might get re-balanced.

Time complexity:
Insert: O(n * m); n = inserted elements, m = moved elements
Delete: O(n * m); n = deleted elements, m = moved elements
Search: O(log n)

Constructors¶

ctor¶

1

public p BinaryTree.ctor()

Constructs an empty tree

ctor¶

1

public p BinaryTree.ctor(const BinaryTree<T>& other)

Constructs a new tree as a deep copy of another tree

Parameters

ctor¶

1

public p BinaryTree.ctor(BinaryTree<T>& other)

Move-constructs a new tree, taking ownership of another tree's nodes

Parameters

dtor¶

1

public p BinaryTree.dtor()

Destruct the binary tree, freeing all its nodes

Methods¶

insert¶

1

public p BinaryTree.insert<T>(const T& value)

Insert a new value into the binary tree

Parameters

contains¶

1

public f<bool> BinaryTree.contains<T>(const T& value)

Search for a value in the binary tree

Parameters

Returns: bool — True if the value was found, false otherwise

delete¶

1

public p BinaryTree.delete<T>(const T& value)

Delete a value from the binary tree

Parameters