Search tree

In computer science, a search tree is an abstract data structure in which the amount of elements in which to search is displayed in a tree structure. This representation supports efficient searching on the kind of nested intervals when the elements in a total order can be arranged.

Operations

The characteristic operation is the search. Most other operations, such as insert, delete, traverse are inherited from the underlying tree structure.

The search operation is an element with a matching key back or if the key is not found, the null element, or (in the sense of total order ) nearest else.

The maximum cost for searching, i.e., the maximum number of comparisons required is proportional to the tree height. In a balanced tree height is logarithmic in the number n of elements, while it is proportional to N with a degenerate to a linear list tree.

Special search trees

In particular, in the binary search trees ( BST engl. of binary search tree ) in which a node has at most two child nodes, many variants have been developed to counteract the degeneration. For the common features of them see the

Non- binary search trees are as follows:

• 2-3 4- tree
• B- tree
• K -d tree

The Fibonacci heap uses a tree lot - also called forest.

More trees based search structures

Although complexity-theoretic details are asymptotic to understand, they can best be transferred into practice when the entire data structure in a uniform medium, such as the RAM ( main memory), to be housed.

Playing against it accesses to external media a role come further considerations come into play. In the context of search trees is referred to the article:

• B- tree
• Index structure

Memory complexity

The extra memory requirements of a search tree - on the user data out - is generally linear in the number n of elements, ie.

Runtime complexity

At runtime, a distinction operations to search, insert and delete. In the latter two in the table, the run time for the positioning is not included in the calculation, since this can be done not only about looking, but also eg on the traverse. Depending on the type of search tree mean < maximum running times are compared, and the maximum thereof is omitted if it is coincident with the center.

2 Under the unbalanced binary search trees, there are trees, which can not be guaranteed. However, the specification applies across on average over all possible tree shapes.

In addition to the above mentioned operations further are:

• Access to specific elements, such as the smallest element
• Merging of search trees

Transit time measurements of some search algorithms using realistic examples can be found at Ben Pfaff.