<< Chapter < Page Chapter >> Page >
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.

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.

Questions & Answers

what is a good calculator for all algebra; would a Casio fx 260 work with all algebra equations? please name the cheapest, thanks.
Kevin Reply
a perfect square v²+2v+_
Dearan Reply
kkk nice
Abdirahman Reply
algebra 2 Inequalities:If equation 2 = 0 it is an open set?
Kim Reply
or infinite solutions?
Embra Reply
if |A| not equal to 0 and order of A is n prove that adj (adj A = |A|
Nancy Reply
rolling four fair dice and getting an even number an all four dice
ramon Reply
Kristine 2*2*2=8
Bridget Reply
Differences Between Laspeyres and Paasche Indices
Emedobi Reply
No. 7x -4y is simplified from 4x + (3y + 3x) -7y
Mary Reply
is it 3×y ?
Joan Reply
J, combine like terms 7x-4y
Bridget Reply
im not good at math so would this help me
Rachael Reply
how did I we'll learn this
Noor Reply
f(x)= 2|x+5| find f(-6)
Prince Reply
Need to simplify the expresin. 3/7 (x+y)-1/7 (x-1)=
Crystal Reply
. After 3 months on a diet, Lisa had lost 12% of her original weight. She lost 21 pounds. What was Lisa's original weight?
Chris Reply
what is nanomaterials​ and their applications of sensors.
Ramkumar Reply
what is nano technology
Sravani Reply
preparation of nanomaterial
Victor Reply
Yes, Nanotechnology has a very fast field of applications and their is always something new to do with it...
Himanshu Reply
can nanotechnology change the direction of the face of the world
Prasenjit Reply
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.
Ali Reply
the Beer law works very well for dilute solutions but fails for very high concentrations. why?
bamidele Reply
how did you get the value of 2000N.What calculations are needed to arrive at it
Smarajit Reply
Got questions? Join the online conversation and get instant answers!
QuizOver.com Reply

Get the best Algebra and trigonometry course in your pocket!

Source:  OpenStax, Principles of object-oriented programming. OpenStax CNX. May 10, 2013 Download for free at http://legacy.cnx.org/content/col10213/1.37
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Principles of object-oriented programming' conversation and receive update notifications?