Overview

binary search tree


Show Summary Details

Quick Reference

A binary tree in which the data values stored at the nodes of the tree belong to a well-ordered set, and the value stored at any nonterminal node, A, is greater than the values stored in the left subtree of A and less than the values stored in the right subtree of A. To search a binary search tree, t, to see if the value, v, is present, the recursive search algorithm shown in the figure is used.

In data-processing applications, the data values stored at the nodes of a binary search tree will be key values with an associated link to the record to be retrieved. The same principle is used in the binary search algorithm. The concept can be generalized to a multiway search tree. See also AVL tree, optimal binary search tree.

Subjects: Computing.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.