Binäärihakupuun

Binäärihakupuu, often abbreviated as BST, is a data structure used in computer science for storing a collection of keys in a sorted order. It is a type of binary tree, meaning each node has at most two children, referred to as the left child and the right child. The defining characteristic of a BST is its ordering property: for any given node, all keys in its left subtree are less than the node's key, and all keys in its right subtree are greater than the node's key.

This ordering property allows for efficient searching, insertion, and deletion of elements. Searching for a specific key involves comparing the target key with the current node's key. If the target key is smaller, the search continues in the left subtree; if larger, it proceeds to the right subtree. This process is repeated until the key is found or an empty subtree is encountered, indicating the key is not present. On average, searching in a balanced BST takes logarithmic time with respect to the number of nodes, denoted as O(log n).

Insertion involves traversing the tree to find the correct position for the new key, maintaining the BST property. Deletion is more complex, requiring careful handling to preserve the tree's structure and ordering. If a node to be deleted has two children, it is typically replaced by its inorder successor or predecessor.

While BSTs offer good average-case performance, their efficiency can degrade significantly if the tree becomes unbalanced, resembling a linked list. In such cases, operations can degrade to linear time, O(n). To mitigate this, self-balancing BSTs like AVL trees and Red-Black trees are often used, which automatically adjust their structure to maintain logarithmic time complexity for operations.