Binary Search Tree
I. Concept and Introduction
Binary Search Tree (English: Binary Search Tree), also known as binary search tree, binary search tree, ordered binary tree, or sorted binary tree. It satisfies the following conditions:
- If its left subtree is not empty, all node values in the left subtree are less than its root node.
- If its right subtree is not empty, all node values in the right subtree are greater than its root node.
Its left and right subtrees are also binary search trees.
As shown in the figure below:
II. Applicability Notes
Binary search trees have efficient insertion, deletion, and query operations.
The average time complexity isO(log n), the worst-case scenario isO(n). Binary search trees are different from heaps; they are not necessarily complete binary trees, and the underlying layer is not easily represented directly by arrays, so linked lists are used to implement binary search trees.
| Find element | Insert element | Delete element | |
|---|---|---|---|
| Normal array | O(n) | O(n) | O(n) |
| Ordered array | O(logn) | O(n) | O(n) |
| Binary Search Tree | O(logn) | O(logn) | O(logn) |
Below, we first introduce the binary search method in array form as a conceptual reference, and then continue to introduce the search method of binary search trees.
III. Illustration of the Binary Search Method Process
The idea of binary search was proposed in 1946. The search problem is a very important fundamental problem in computer science. Binary search can only be used on ordered sequences. If we want to find an element, first look at the relationship between the middle value V of the array and the target data. There are three cases:
- 1. If it equals the target data, it is found directly.
- 2. If it is less than V, continue searching in the group less than V.
- 2. If it is greater than V, continue searching in the group greater than V.
IV. Java Example Code
Source code package download:Download
src/example/binary/BinarySearch.java file code:
/**
* Binary search method
*/
public class BinarySearch {
// Binary search method: find target in the sorted array arr
// If target is found, return the corresponding index
// If target is not found, return -1
public static int find(Comparable[] arr, Comparable target) {
// find target in arr[l...r]
int l = 0, r = arr.length-1;
while( l <= r ){
//int mid = (l + r)/2;
// to prevent integer overflow in extreme cases, use the following logic to calculate mid
int mid = l + (r-l)/2;
if( arr[mid].compareTo(target) == 0 )
return mid;
if( arr[mid].compareTo(target) > 0 )
r = mid - 1;
else
l = mid + 1;
}
return -1;
}
}