Data Structure & Algorithm Takeaway: Binary Search Tree

TipWhat is binary search tree?

A binary search tree (BST), or binary sort tree, is a type of binary tree storing ordered elements that satisfies the property:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.

TipWhat are the main operations of a binary search tree?

The basic operations of a binary search tree include all the operations of a binary tree. The difference is that the binary search tree allows for efficient searching, insertion, and deletion of elements due to its ordered structure.

TipWhy is it called a binary search tree?

A binary search tree is called so because it is a binary tree that allows for efficient searching of elements, which is its main purpose. The regular binary tree does not have any specific ordering of elements, so searching for an element may require traversing the entire tree. In contrast, a binary search tree stores elements that are ordered, which can be taken advantage of to quickly search for an element.

TipHow to search for an element in a binary search tree?

To search for an element in a binary search tree, we start at the root node and compare the target value with the key of the current node. If the target value is equal to the current node’s key, we have found the element. If the target value is less than the current node’s key, we move to the left subtree and repeat the process. If the target value is greater than the current node’s key, we move to the right subtree and repeat the process. This process continues until we either find the element or reach a leaf node (a node with no children), indicating that the element is not present in the tree.

ImportantWhat is the time complexity of search in a binary search tree?

The time complexity of the search operation in a binary search tree is $O(h)$, where $h$ is the height of the tree. In the best case, when the tree is balanced, the height is $O(\log n)$, where $n$ is the number of nodes in the tree. In the worst case, when the tree is extremely skewed and resembles a linked list, the height can be $O(n)$. Therefore, the average time complexity for search operation in a balanced binary search tree is $O(\log n)$.

TipHow to insert an element in a binary search tree?

Insert operation in a binary search tree first need to find the correct position for the new element, which follows the same logic as the search operation. However, insert will modify the binary tree structure, which is more tedious.

ImportantWhat is the time complexity of insert in a binary search tree?

TipHow to delete an element in a binary search tree?

Similar to insert, delete operation in a binary search tree first need to find the element to be deleted, which follows the same logic as the search operation. However, delete will modify the binary tree structure, which is more tedious.

ImportantWhat is the time complexity of delete in a binary search tree?

TipHow is a binary search tree constructed in the first place?

A binary search tree is constructed by inserting elements one by one.

ImportantWhat is the time complexity of constructing a binary search tree?

The time complexity of constructing a binary search tree by inserting elements one by one. A insert operation takes $O(h)$ time, where $h$ is the height of the tree. This can be $O(\log n)$ on average for a balanced tree, but can degrade to $O(n)$ in the worst case for an unbalanced tree. Constructing a binary search tree involves inserting $n$ elements, therefore the overall time complexity is $O(n\log n)$ on average, but can degrade to $O(n^2)$ in the worst case.

TipConstructing a balanced binary search tree takes $O(n\log n)$ at minimum, which is the same as sorting algorithms like merge sort and quick sort. So why bother constructing a binary search tree for search?

This is true, but binary search tree is more of saved for multiple times of searches. If you only need to search once, binary search tree is not necessary.

TipAs balanced binary search tree is preferred, how to construct a balanced binary search tree?

There are mainly two algorithms to construct a balanced binary search tree:

• AVL tree
• Red-Black tree