# 4.3 Binary search tree

 Page 1 / 3
The binary tree structure can be used as an efficient way to organize data objects that are totally ordered. This is done by maintaining the tree in such a way that for any given subtree, the data elements in its left subtree are less than the root and the data elements in the right subtree are greater than the root. Such a binary tree is called a binary search tree.

## 1. binary search tree property (bstp)

Consider the following binary tree of Integer objects.

-7 |_ -55| |_ [] | |_ -16| |_ -20 | | |_ []| | |_ [] | |_ -9| |_ [] | |_ []|_ 0 |_ -4| |_ [] | |_ []|_ 23 |_ []|_ []

Notice the following property:

• all elements in the left subtree are less than the root element,
• and the root element is less than all elements in the right subtree.

Moreover, this property holds recursively for all subtrees.  It is called the binary search tree (BST) property.

In general, instead of Integer objects, suppose we have a set of objects that can be compared for equality with "equal to" and "totally ordered" with an order relation called "less or equal to" .  Define "less than" to mean "less or equal to" AND "not equal to".  Let T be a BiTree structure that stores such totally ordered objects.

## Definition of binary search tree property

The binary search tree property (BSTP) is defined on the binary tree structure as follows.

• An empty binary tree satisfies the BSTP.
• A non-empty binary tree T satisfies the BSTP if and only if
• the left and right subtrees of T both satisfy BSTP, and
• all elements in the left subtree of T are less than the root of T, and
• the root of T is less than all elements in the right subtree of T.

We can take advantage of this property when looking up for a particular ordered object in the tree.  Instead of scanning the whole tree for the search target, we can compare the search target against the root element and narrow the search to the left subtree or the right subtree if necessary.  So in the worst possible case, the number of comparisons is proportional to the height of the binary tree.  This is a big win if the tree is balanced .  It can be proven that when a tree containing N elements is balanced, its height is at most a constant multiple of logN.  For example, the height of a balanced tree containing 10 6 elements is at most a fixed multiple of 6.  Here is the definition of what a balanced tree is.

## Definition of balanced tree

• An empty tree is balanced .
• A non-empty tree is balanced if and only if
•  its subtrees are balanced and
• the heights of the subtrees differ by a fixed constant or by a fixed constant factor.

A binary tree with  the BST property is called a binary search tree.  It can serve as an efficient way for storage/retrieval of data.  We are lead to the following question: how to create and maintain a binary search tree?

## 2. binary search tree insertion

Suppose we start with an empty binary tree T and  a  Comparator that models a total ordering in a given set of objects S.  Then T clearly has the BST property with respect the Comparator ordering of S.  The following algorithm (visitor on binary trees) will allow us to insert elements of S into T and at the same time maintain the BST property for T.  This algorithm also works for binary search tree containing Comparable objects.

what is a good calculator for all algebra; would a Casio fx 260 work with all algebra equations? please name the cheapest, thanks.
a perfect square v²+2v+_
kkk nice
algebra 2 Inequalities:If equation 2 = 0 it is an open set?
or infinite solutions?
Kim
y=10×
if |A| not equal to 0 and order of A is n prove that adj (adj A = |A|
rolling four fair dice and getting an even number an all four dice
Kristine 2*2*2=8
Differences Between Laspeyres and Paasche Indices
No. 7x -4y is simplified from 4x + (3y + 3x) -7y
is it 3×y ?
J, combine like terms 7x-4y
im not good at math so would this help me
how did I we'll learn this
f(x)= 2|x+5| find f(-6)
Need to simplify the expresin. 3/7 (x+y)-1/7 (x-1)=
. After 3 months on a diet, Lisa had lost 12% of her original weight. She lost 21 pounds. What was Lisa's original weight?
what is nanomaterials​ and their applications of sensors.
what is nano technology
preparation of nanomaterial
Yes, Nanotechnology has a very fast field of applications and their is always something new to do with it...
can nanotechnology change the direction of the face of the world
At high concentrations (>0.01 M), the relation between absorptivity coefficient and absorbance is no longer linear. This is due to the electrostatic interactions between the quantum dots in close proximity. If the concentration of the solution is high, another effect that is seen is the scattering of light from the large number of quantum dots. This assumption only works at low concentrations of the analyte. Presence of stray light.
the Beer law works very well for dilute solutions but fails for very high concentrations. why?
how did you get the value of 2000N.What calculations are needed to arrive at it
Got questions? Join the online conversation and get instant answers!