Binary Search Tree

Binary search trees (BSTs) are a type of data structure that maintains a sorted order of elements. Each node in a BST has at most two children, referred to as the left and right child. The left child’s value is less than its parent’s value, while the right child’s value is greater than its parent’s value. This property allows for efficient searching, insertion, and deletion operations.

class trees.binary_trees.binary_search_tree.BinarySearchTree

Binary Search Tree class that supports insertion, deletion, and searching.

Examples

>>> from trees.binary_trees import binary_search_tree
>>> tree = binary_search_tree.BinarySearchTree()
>>> tree.insert(key=23, data="23")
>>> tree.insert(key=4, data="4")
>>> tree.insert(key=30, data="30")
>>> tree.insert(key=11, data="11")
>>> tree.insert(key=7, data="7")
>>> tree.insert(key=34, data="34")
>>> tree.insert(key=20, data="20")
>>> tree.insert(key=24, data="24")
>>> tree.insert(key=22, data="22")
>>> tree.insert(key=15, data="15")
>>> tree.insert(key=1, data="1")
>>> tree.get_leftmost().key
1
>>> tree.get_leftmost().data
'1'
>>> tree.get_height(tree.root)
4
>>> tree.search(24).data
`24`
>>> tree.delete(15)

delete(key: Any) → None

Delete the node by the given key.

Parameters:: key (Any) – The key of the node to be deleted.
Raises:: KeyNotFoundError – Raised if the key does not exist.

property empty: bool

True if the tree is empty; False otherwise.

Notes

The property, empty, is read-only.

Type:: bool

get_height(node: Node | None) → int

Return the height of the given node.

Parameters:: node (Node) – The node to get its height.
Returns:: The height of the given node.
Return type:: int

get_leftmost(node: Node) → Node

Return the leftmost node from a given subtree.

The key of the leftmost node is the smallest key in the given subtree.

Parameters:: node (Node) – The root of the subtree.
Returns:: The node whose key is the smallest from the subtree of the given node.
Return type:: Node

insert(key: Any, data: Any) → None

Insert a (key, data) pair into the binary search tree.

Parameters:

key (Any) – The key associated with the data.
data (Any) – The data to be inserted.

Raises:

DuplicateKeyError – Raised if the key to be inserted has existed in the tree.

search(key: Any) → Node

Look for a node by a given key.

Parameters:: key (Any) – The key associated with the data.
Returns:: The node found by the given key.
Return type:: Node
Raises:: KeyNotFoundError – Raised if the key does not exist.

class trees.binary_trees.binary_search_tree.Node(key: Any, data: Any, left: Node | None = None, right: Node | None = None, parent: Node | None = None): Definition of Binary Search Tree Node.