What Is a Search Tree?

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.