Easy Tutorial
Union Find Quick Union Find Compress Heap Index Shell Sort Merge Sort Binary Search Remove Heap Shift Down Heap Sort Union Find Quick Merge Graph Theory Short Path Graph Theory Deep Union Find Basic Binary Search Feature Insertion Sort Binary Search Tree Search Sorting Algorithm Derivative Problem Heap Storage Binary Search Tree Insert Heap Shift Up Binary Search Traverse Data Structures Tutorial Graph Theory Iter 2Way Quick Sort Binary Search Tree Random Quick Sort Graph Theory Union Find Rank Graph Theory Path 3Way Qiuck Sort Union Find Size Heap Sort Optimization Binary Search Level Traverse
❮ Union Find Basic Insertion Sort ❯

Properties of Binary Search Trees

1. Order Properties

A binary search tree can be implemented as a lookup table.

The purpose of using a binary search tree is to immediately obtain the value associated with a key. Operations such as finding the minimum, maximum, successor, predecessor, floor, ceil, rank, and select are all manifestations of the order properties of a binary search tree.

2. Limitations

Binary search trees have limitations in terms of time performance.

As illustrated below, with the same set of elements, two different binary search trees can be constructed, both of which satisfy the definition:

A binary search tree can degenerate into a linked list. Consequently, the search operation in a binary search tree is related to the height of the tree, which in this case is equal to the number of nodes n. Additionally, all corresponding algorithms for binary search trees degrade to O(n) complexity.

❮ Union Find Basic Insertion Sort ❯