Search methods often use a linear ordering of keys. The obvious method here is the “binary search” method (binary, dichotomous, half division):
First the key k is compared to the middle key in the table, the result of the comparison allows to determine in which half of the table the search should be continued by applying the same procedure to it, etc.
The function returns the number of the searched key or N+1 if no key is found. BP never uses more than log2N+1 comparisons for both successful and unsuccessful searches.
This property follows from the fact that the number of records processed in each cycle is halved.
Interpolation search works in log(logN) operations if the data is uniformly distributed. As a rule, it is used only on very large tables, and several steps of interpolation search are made, and then binary or sequential variants are used on a small subarray.
Binary trees
Let us define a tree as a finite set T, which is either empty or has one specially labeled node, called the root, and all other nodes are contained in non-overlapping sets T1, T2,…, Tm, each of which is a tree. The trees T1, T2,…, Tm are called subtrees of the given root.
The number of subtrees m of a node is called the degree of the node. The degree of a tree is the maximum of the degrees of all nodes in the tree. If the relative order of subtrees T1, T2,…, Tm is important, the tree is said to be ordered. An ordered tree of degree two is called a binary tree. Thus, in a binary tree, each node has at most two subtrees (left, right).
There exist m-ary trees in which the semidegree of the outcome of each node is less than or equal to m. If the semidegree of the outcome of each vertex is exactly equal to either m or zero, then such a tree is called a complete m-ary tree.
When m=2, such trees are called binary trees, or complete binary trees, respectively.
A special kind of binary tree is a search tree organized in such a way that for each node T all the el- ters in the left subtree are less than the element of node T, and all the el- ters in the right subtree are greater than the element of node T.
SEARCH TREES play a special role in data processing algorithms. They are used in lexicographic tasks, construction of frequency dictionaries, data sorting tasks. The main advantage of this data structure is that it is ideal for the search problem. The place of each element can be found by moving from the root to the left or right depending on the value of the element.
To simplify the search procedure, you can use a tree with a barrier node (the last empty node z where the element to search for x is sent).
The main operations when working with search trees are tree search with inclusion of a new element and tree search with exclusion of an element. These tasks are widely used when the tree grows or shrinks during the program itself.