Tree Structures

Software Development; Coding Techniques; Computer Science

A tree structure is a way of representing how a hierarchical system is organized. As such, tree structures are ideal for storing hierarchical data. A binary search tree is a tree structure in which each nonterminal node has no more than two child nodes. Binary search trees are used in computer programming to store and manipulate data. They facilitate fast data retrieval, insertion, and deletion.

A tree structure is a method of representing a how a hierarchical system is organized. It resembles an upside-down tree, with the roots at the top and the branches growing downward, ending in leaves at the bottom. A classic example of a tree structure is an organizational chart.

The fundamental unit of a tree structure is called a node. Each node represents one of the entities in hierarchical system. The node at the top of the hierarchy is called the root node. In a company's organizational chart, for example, the root node might represent the president of the company. In most scenarios encountered in computer programming, tree structures have a single root node.

Relationships between nodes in a tree structure are described using kinship terminology. As in a family tree (another example of a tree structure), a node is the child of the node one level directly above it and the parent of any nodes one level directly below it. Children with the same parent are referred to as siblings. A node with no children is called a terminal node or a leaf node. Nonterminal nodes are ancestors to all nodes that descend directly from their children, which in turn are descendants of their ancestor nodes. The root node is at the top of the hierarchy and does not have a parent.

A binary search tree is a tree structure that is often used in computer programming to store data. A binary tree is one in which each node can have only two children, a left child and a right child. The value of the left-hand child is always lower than that of the right-hand child. Binary search trees are most efficient when they are balanced, meaning that both sides are the same height, or at most differ by only one level. The median value of the data set is stored in the root node, and all values lower than the median descend from the root's left child note, while all greater values descend from the right child node.

Many types of data are organized in a hierarchical fashion. Examples include governmental entities (country, state or province, county, city) and biological taxonomy (domain, kingdom, phylum, class, order, family, genus, species). This makes the tree structure an excellent match for modeling such data.

Binary search trees offer additional advantages. Their design facilitates quick and flexible searches, insertions, and deletions. However, arrays or linked lists might offer improved performance over binary search trees, depending on the amount of data and the operation being performed. A properly balanced binary search tree can search for, insert, or delete data faster than an array, especially if there is a large number of data elements. Yet arrays can access data faster than binary search trees. If the binary search tree is unbalanced, the array may complete other operations faster as well. Linked lists take longer to search than binary search trees but are faster for inserting or deleting data.

Binary search trees are a good structure to use when a large amount of data needs to be frequently searched, and each data element is associated with a unique value, or key. For example, imagine an application used by customer service representatives for a large corporation. The representatives will frequently perform searches to retrieve customer information, and each customer can be identified by a unique customer identification (ID) number. This number is the key, and accessing it allows the program to retrieve all of the other data associated with the customer, such as their name and phone number.

The internal design of the binary search tree structure specifies that the value of right child node is always greater than the value of the left child node. So, the tree can be traversed efficiently in the following manner. First, the root node, which contains the median customer ID value, is examined. If the root node contains the customer ID value that the program is looking for, then the data has been located. If it does not, the value of the root node is compared to the search key. If the search key value is lower than the root node value, then the search algorithm checks the value in the left child node; if it is greater, the algorithm checks the right child node. If the child node value matches the search key, the correct customer ID has been located. If not, the same comparison procedure is conducted on the child node.

This process continues until the correct customer ID is located. This process is efficient because every time a node is checked, even if it does not match the search key, half of the remaining unchecked nodes are eliminated as possibilities.

Tree structures are an ideal construct to use when working with hierarchical data and with data that has unique keys. As so much of the information people deal with is hierarchically ordered, many people find tree structures easy to conceptualize and understand. It is an intuitive choice for modeling data objects and other hierarchical data structures in software architectures. The widespread use of hierarchical data in human activities across all areas of society has caused tree structures to become a key component in software development. As tree structures parallel the ways in which humans store and process information, they are like to remain an important tool in the future.

—Maura Valentino, MSLIS