Category: 

What Is a Search Tree?

Article Details
  • Written By: Eugene P.
  • Edited By: A. Joseph
  • Last Modified Date: 13 November 2016
  • Copyright Protected:
    2003-2016
    Conjecture Corporation
  • Print this Article
Free Widgets for your Site/Blog
Although they mainly functioned as downspouts, gargoyles were also intended to scare people into attending church.  more...

December 3 ,  1989 :  The Cold War officially ended.  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.

Ad

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.

Ad

You might also Like

Recommended

Discuss this Article

Post your comments

Post Anonymously

Login

username
password
forgot password?

Register

username
password
confirm
email