Guide to Operations for the Tree Data Structure

1
3957

Before we can get into how trees can be utilized in real world programs it is helpful to take a step back and walk through the basic operations for the tree data structure.

When it comes to coding interviews, being able to properly answer questions related to trees can be the difference between getting the job and being passed over. So with that in mind it’s critical to have a strong knowledge of how to work with this data structure.

Operations for the Tree Data Structure

There are six fundamental tools that are utilized when working with trees. These operations are what allow trees to be the powerful computer science mechanism that they are.

The six operations for the tree data structure are:

  • Enumerating
  • Searching
  • Adding
  • Deleting
  • Pruning
  • Grafting

A few of these, such as adding and deleting are self explanatory. However concepts such as grafting may take a little more study.

We’ll cover each of these operations in detail while studying trees. For right now let’s take a high level view at the behavior of each operation.

Enumerating

While working with the tree data structure, one of the most common tasks is enumerating through the tree. Essentially this means that your algorithm can traverse through the tree.

Enumerating can take a few forms.

operations for the tree data structure

A straightforward example would be to find the path from a root node in a binary tree to another node (this also falls into the realm of searching, but this still requires enumerating through the tree).

operations for the tree data structure

However a more practical example would be if we were creating a mapping application. If we had a set of cities, represented as nodes, and needed to generate a route that took the shortest path… this is also enumeration.

In this example our algorithm will have to navigate our tree of geographical nodes in order to find the most efficient route. This is the type of algorithm that the creators of applications such as Google Maps work on daily.

Searching

Next on the list of operations for the tree data structure is searching. Searching within trees, especially binary search trees, is one of the tools that makes working with this data structure so powerful.

operations for the tree data structure

Trees specialize in organizing data in an efficient manner. Imagine that you are in charge of doing laundry in your home. Will you be able to find a matching pair of socks faster if you first have all of the socks in their own pile? Or would it be more efficient to simply look at every…. single… piece of clothing? Of course it would be faster if your socks are all in the same pile.

Searching within trees works the same way as our laundry example. A tree allows you to efficiently organize your data in a way that searching can be exponentially more efficient compared with other data structures.

Adding

When it comes to adding to a tree, the concept is straightforward. You simply add a new node to the structure. The key is that the element has to follow the rules of the tree.

operations for the tree data structure

For example, if you were to add a new city to the routing application, it would have to be added in a manner that did not cause a nasty detour. For example, if you wanted to add a visit to San Francisco, you wouldn’t want to add the new location while in the middle of the trip since this would dramatically decrease the efficiency of the route (and you’d have some annoyed drivers).

operations for the tree data structure

Instead you would need to ensure that when you add new nodes they follow the rules your routing algorithm has already set in place.

Deleting

In deleting nodes from a tree, the process of removing the nodes typically requires you to implement a set of processes for ensuring that the tree remains stable. This can be a complex process, such as ensuring that a binary search tree remains balanced after removing a node (we’ll discuss this in detail later on). Or it can be as straightforward and updating a reference on a single node.

operations for the tree data structure

For example, going back to our mapping tree, let’s imagine that we removed our stop in Dallas. All we would have to do is:

  • Delete the Dallas node.
  • Update the reference so that the Scottsdale node points to the Houston node.

Pruning

Many new students eyes glaze over when they hear the term pruning in relation to data structures. However don’t tune our now, pruning is actually a relatively straightforward process when you think about it practically.

operations for the tree data structure

Pruning is the process of removing an entire section of a tree. So for our mapping application, let’s imagine that we had a tour of the Northwest US included in our route.

operations for the tree data structure

In order to prune the tree we simply removing a section from the tree. In this case we’d remove the nodes associated with the Northwest portion of the trip.

Grafting

If the concept of pruning makes sense, then you will pick up on grafting quite easily. The concept of grafting is adding an entire section to a tree.

operations for the tree data structure

In this example we’re adding a new section of the tree that includes taking a tour of New England. So grafting is simply adding new sub sections to a tree. As with adding a single element, the key to grafting is ensuring that the new section follows the rules of the rest of the tree.

1 COMMENT

LEAVE A REPLY

Please enter your comment!
Please enter your name here