Data Management.com

tree structure

By TechTarget Contributor

What is a tree structure?

A tree data structure is an algorithm for placing and locating files (called records or keys) in a database. The algorithm finds data by repeatedly making choices at decision points called nodes.

A node can have as few as two branches (also called children) or as many as several dozen. Although the tree structure's composition is straightforward, in terms of the number of nodes and children, a tree can be gigantic and complex.

Advantage of a tree structure

A tree structure consists of nodes connected by edges. One of its significant advantages over other data structures such as arrays, linked lists, stacks and queues is that it is a non-linear data structure that provides easier and quicker access to data. While linear data structures store data sequentially, tree structures permit data access in different directions.

As data sizes increase, access in such structures becomes slower, which can be hugely problematic in today's hyper-digital world. Tree structures can avoid such issues.

Tree structure properties

A tree can contain one special node called the "root" with zero or many subtrees. It may also contain no nodes at all. Every edge directly or indirectly originates from the root. The tree is always drawn upside-down, which means the root appears at the top. One parent node can have many children, but every child node has only one parent node. The maximum number of children per node is called the tree "order.".

In a tree, records are stored in locations called "leaves." The name indicates that records always exist at endpoints; there is nothing beyond them. Not every leaf contains a record, but more than half do. A leaf that does not contain data is called a "null." The maximum number of access operations required to reach the desired record is called the "depth."

The only way to perform any operation on a tree is by reaching the specific node. For this, a tree traversal algorithm is required.

Balanced and unbalanced trees

If the order is the same at every node and the depth is the same for every record, the tree is said to be balanced. Other trees have varying numbers of children per node, and different records might lie at different depths. In this case, the tree is said to have an unbalanced or asymmetrical structure.

This illustration shows three examples of tree structures. Structures A and B are balanced, and structure C is unbalanced.

The key elements in each tree are as follows:

As the process moves away from the root and toward the leaves, children can branch out from a node. However, children never merge into a node.

A practical tree can have thousands, millions or billions of nodes, children, leaves and records. The trees shown here are simple enough to be rendered in two dimensions, but with some large databases, three dimensions are needed to clearly depict the tree structure.

Tree structure terms

Common terms associated with tree structures include:

Different types of tree structures

A general tree is a data structure with no constraints on the hierarchical structure. This means that a node can have any number of children. This tree is used to store hierarchical data, such as folder structures.

Other common tree structures are:

Applications of tree structures

Popular applications of tree structures include:

Check out essential big data best practices for businesses and how to improve data quality.

24 Nov 2021

All Rights Reserved, Copyright 2005 - 2024, TechTarget | Read our Privacy Statement