What Is a Search Tree?

Article Details
  • Written By: Eugene P.
  • Edited By: A. Joseph
  • Last Modified Date: 25 August 2016
  • Copyright Protected:
    Conjecture Corporation
  • Print this Article
Free Widgets for your Site/Blog
Built at the request of Dag Hammarskjöld, the United Nations Headquarters has a meditation room dedicated to silence.   more...

October 1 ,  1890 :  Yosemite National Park was established.  more...

A search tree is a data structure used in computer programming to contain and organize a list of data.‭ ‬Each‭ ‬search‭ ‬tree is comprised of an ordered set of nodes.‭ ‬These nodes can be connected to zero or more other nodes.‭ ‬The individual nodes contain some‭ ‬data as well as links to any other nodes.‭ ‬The data that is contained in the nodes of the tree is very often ordered in some way to allow efficient algorithms to search for,‭ ‬insert and remove nodes with ease.

The nodes of a search tree are described with four important terms.‭ ‬The top of a tree,‭ ‬where the first node is located,‭ ‬is called the root.‭ ‬If‭ ‬a‭ ‬node contains links to sub-nodes,‭ ‬that node is known as a parent.‭ ‬Nodes that‭ ‬are‭ ‬beneath the parent are called children, and any node that has no child nodes is‭ ‬called a leaf.‭ ‬So,‭ ‬a root node is identified because it does not have a parent,‭ ‬and leaf nodes will have no children.


A program is able to move through a tree searching for data by starting at a particular node,‭ ‬performing a conditional check ‬and then moving to the next logical node if the required data is not present.‭ ‬Depending on the data structure used,‭ ‬this search can take a variable amount of time.‭ ‬If the search tree is organized during the process of adding and removing‭ ‬nodes,‭ ‬the search can be very fast.‭ ‬When a tree is‭ ‬assembled‭ ‬randomly,‭ ‬is‭ ‬unsorted or allows multiple parents,‭ ‬the search can take a very long time.

One factor that affects the use of search trees is the issue of balance.‭ ‬A balanced tree is one in which both the right and left children of the root node contain either the same depth of child nodes or are within a one-node count of each other.‭ ‬The depth of‭ ‬a‭ ‬tree is the number of nodes from the lowest leaf of a tree to the root.‭ ‬An unbalanced tree could have all of the nodes on only one side or have all of the nodes arranged in a linear fashion with no branches.‭ ‬When the depth of a tree increases,‭ ‬the‭ ‬speed of search algorithms can decrease dramatically.‭

There are certain types of search trees that are described as self-balancing.‭ ‬These trees use operations such as tree rotation to help‭ ‬maintain balance‭ ‬while‭ ‬preserving the order of the data in the leaves.‭ ‬Although performing tree rotations might slow down a program when adding and removing nodes,‭ ‬this is countered by the speed at which data can be retrieved.

Although there are many types of search trees,‭ ‬the most common tree data structure is a binary search tree.‭ ‬This data type consists of nodes that each have zero to two child nodes.‭ ‬There is only one root node,‭ ‬and all of the leaves in the tree are ordered from left to right‭ ‬in ascending‭ ‬values according to‭ ‬the data they hold.‭ ‬Many‭ ‬algorithms‭ ‬exist for binary search trees that‭ ‬can‭ ‬make ordering data very easy.

There is no single standard implementation for search tree nodes.‭ ‬The nodes can be represented by a wide variety of data structures.‭ ‬Arrays of arrays can be used,‭ ‬as could multiply linked lists.‭ ‬Often,‭ ‬a search tree uses a custom data structure that is designed to aid in the completion of the necessary operations called for by the program.‭ ‬Some standard programming libraries‭ ‬even‭ ‬include their own internal implementations of search trees.


You might also Like


Discuss this Article

Post your comments

exception 'Exception' with message 'error writing captcha: Duplicate entry '2147483647' for key 'PRIMARY'' in /ssd/www/wisegeek/public_html/_core/classes/public/Captcha.php:44
Stack trace:
#0 /ssd/www/wisegeek/public_html/_core/controls/public/ControlDiscussionPostBox.php(324): Captcha->createCaptcha()
#1 /ssd/www/wisegeek/public_html/framework/classes/Control.php(104): ControlDiscussionPostBox->preRender(false)
#2 /ssd/www/wisegeek/public_html/framework/classes/Control.php(149): Control->render()
#3 /ssd/www/wisegeek/public_html/tpl/default-nocustom-lu/pages/public/article/article.htm(526): Control->__toString()
#4 /ssd/www/wisegeek/public_html/framework/classes/Control.php(300): require('/ssd/www/wisege...')
#5 /ssd/www/wisegeek/public_html/framework/classes/Control.php(309): Control->requireTpl('pages/public/ar...', Object(PageArticleCom), true)
#6 /ssd/www/wisegeek/public_html/framework/classes/Control.php(131): Control->renderTpl('pages/public/ar...', Object(PageArticleCom))
#7 /ssd/www/wisegeek/public_html/framework/classes/FormDataControl.php(87): Control->renderTemplate()
#8 /ssd/www/wisegeek/public_html/framework/classes/Control.php(109): FormDataControl->renderTemplate()
#9 /ssd/www/wisegeek/public_html/framework/classes/ScriptPage.php(50): Control->render(false)
#10 /ssd/www/wisegeek/public_html/framework/classes/Control.php(149): ScriptPage->render()
#11 /ssd/www/wisegeek/public_html/framework/classes/Page.php(97): Control->__toString()
#12 /ssd/www/wisegeek/public_html/_core/classes/public/PublicFrontController.php(443): Page->processRequest()
#13 /ssd/www/wisegeek/public_html/_core/classes/public/PublicFrontController.php(7): PublicFrontController->renderPage()
#14 /ssd/www/wisegeek/public_html/index.php(11): PublicFrontController::run()
#15 {main}