Chapter 5. Seeing the Forest through the Tree
In Chapter 3, Standing on the Shoulders of Giants, we learned about the most basic data structures and how to build them with Swift; queues, stacks, lists, hash tables, and heaps. Those data structures have helped us to learn the different types of basic data structures available. Right now, you are ready to learn more advanced topics. This chapter is going to introduce a new data structure: the tree.
Trees are a great data structure because, as we will see later, common operations such as search, insertion, and deletion are fast.
The topics covered in this chapter are as follows:
Tree – definition and properties
Overview of different types of tree
Binary trees
Binary search trees (BST)
B-trees
Splay trees
Tree – definition and properties
A tree is made of a set of nodes. Each node is a data structure that contains a key value, a set of children nodes, and a link to a parent node. There is only one node that has no parent: the root of the tree. A tree structure represents data in a hierarchical form, where the root node is on top of the tree and the child nodes are below it.
The tree has some constraints: a node cannot be referenced more than once, and no nodes point to the root, so a tree never contains a cycle:
Basic tree data structure
Let's see some important terms when talking about tree data structures:
Root: The node that is on the top of the tree and is the only node in the tree that has no parent.
Node: A data structure that has a value key, and can contain a set of children and a reference to a parent node. If there is no reference to a parent node, the node is the root of the tree. If the node has no children, it is called a leaf.
Edge: Represents the connection between a parent...
Overview of different types of tree
There are different types of tree data structures, each one with their own benefits and implementations. We are going to have a quick look over the most common ones so we can gain a good overview of the different types and choose which one to use in each case wisely.
After the following introduction to the different types of trees, we will go deeper into the details, properties, uses, and implementations.
This is the most basic type of tree to start with. A binary tree is a tree data structure in which any node has at most two children.
In a binary tree, the data structure needs to store values and references inside each node, contain a value key, and potentially, a reference to the parent (except the root), a left reference to a child, and a right reference to another child.
When a node doesn't have a parent, a left child, or a right child, the reference to that element exists, but it contains NULL/nil value.
Binary tree data structure
As we have seen before, a binary tree consists of a tree in which the maximum number of children per node is two. This property ensures us that every node has a finite number of children. Moreover, we can assign them known references, left and right children.
Before getting into the Swift implementation, let's define some different types of binary tree:
Full binary tree compared to a not full binary tree
Perfect binary tree
Complete binary tree
Balanced binary tree
For a binary tree implementation, the data structure...
Binary search tree basic operations such as access, search, insertion, and deletion take between O(n) and O(log(n)) time. Being both values the worst and the average scenarios. At the end, these times are going to depend on the height of the tree itself.
For example, for a complete binary search tree with n nodes, these operations could take O(log(n)) time. But if a tree with the same number of nodes n is built like a linked list (just 1 child per node), having more levels/depth for the same n nodes, then the operations are going to take O(n) time.
In order to make basic operations such as insertion or search, we need to scan nodes from the root to the leaves. Because of this, we can infer that the height of the tree (the distance or nodes between the root and a leaf) will affect the time we spend performing basic operations.
Now, before jumping into the code of some operations, such as inserting and searching nodes in a binary search tree, lets recall the basic property...
B-trees are similar to binary search trees in many ways, but they have two big differences: the number of children per node is not limited to two and the number of keys in the node is also variable (not just 1).
B-trees are self-balanced, rooted, sorted trees. They allow operations such as insert, search, deletion, and access in logarithmic time.
Each internal node has n keys. These keys are like dividing points between child nodes. So, for n keys, the internal node has n+1 child nodes.
This feature makes B-trees suitable for different applications in fields such as databases and external storage. Having more than two children per node and multiple keys allows the B-tree to perform multiple comparisons for each internal node, so it has less tree height and therefore reduces the time complexity to access and search nodes.
As has been said, each internal node in a B-tree has a different number of keys inside. These keys are used to divide the subtrees below them in order. Look at the...
Splay trees are a specific type of binary search tree in which there is an operation called splaying, which grants the tree the ability to quickly access recently visited nodes.
The splay operation puts the last accessed node as the new root of the tree. Recently visited nodes always have a minimum height, therefore they are easy and quick to access again. We can say that splay trees optimize themselves by performing a mix of searches and tree rotations.
The average height is O(log(n)) and the worst (and most unlikely) scenario is O(n). The amortized time of each operation on a n-node tree is O(log(n)). The amortized time analysis is used when we don't always expect the worst scenario so we can consider different scenarios (not just the worst) in the overall time complexity of the algorithm.
Two common uses of splay trees are caches and garbage collections. In both cases, we get the benefits of quick access to recently visited nodes, so this particular implementation of the binary...
In this chapter, we've learned about a new data structure that you can add to the basic ones that you already know and use in your own project: the tree data structure, including the basic one and other types, such as binary search tree, B-tree, and splay tree. We also introduced red-black trees, which we will see in Chapter 6, Advanced Searching Methods.
We have seen how trees work, when they are useful, what type of tree is better depending on the problem to solve, and how to implement the most common one, the binary search tree.
Moreover, we have seen the basic operations and how to implement them in Swift: insert, search, and delete operations.
By the end of the chapter, we have reviewed the general characteristics of other types of tree such as B-trees and splay trees, both used in very specific situations. In the next chapter, we are going to go further and view more advanced tree structures.
