Chapter 6. Advanced Searching Methods

In Chapter 5, Seeing the Forest through the Tree, we introduced the tree data structure and some of its variants. After seeing the binary search trees, we made a quick overview of other types of advanced trees such as red-black and AVL trees. During this chapter, we are going to dive deeper and learn about trees that allow us to make advanced search methods.

The topics covered in this chapter are as follows:

• Red-black trees

• AVL trees

• Trie trees (Radix trees)

• A look at several substring search algorithms

Red-black trees

Red-black trees are similar to binary search trees with a new parameter for every node, the color of that node.

The color of the node can be either red or black. So, the data structure needed for red-black tree nodes contains a key value, a color, the reference to a parent, and the references to the left and right child.

Red-black trees need to satisfy the following color conditions:

1. Every node must have a color red or black

2. The root is black

3. All the NULL/nil leaves are black

4. For any red node, both children are black

5. For each node, all simple paths from the node to descendant leaves contains the same number of black nodes

   

Red-black tree data structure

Because of color condition number five (see the preceding figure), red-black trees offer worst-case guarantees for key operations such as search, insertion, and deletions that are proportional to its tree height. Unlike regular binary search trees, this makes red-black trees a great candidate to be used in real-time processes and applications...

Red-black tree node implementation

So now that we know the main characteristics of red-black trees, let's see how to implement the base class.

Then, we will progress to the insertion scenario, which is a little bit more complex than in the binary search tree case, because this time we have to maintain the five color conditions after the insertion of a new node in the tree.

Let's see the first version of the RedBlackTreeNode class and the RedBlackTreeColor enumeration that will help us with the color.

In Xcode, go to File | New | Playground, and call it B05101_6_RedBlackTree. In the Sources folder, add a new file called RedBlackTreeNode.swift. Add the following code inside it:

//Enumeration to model the possible colors of a node 
public enum RedBlackTreeColor : Int { 
    case red = 0 
    case black = 1 
} 
 
public class RedBlackTreeNode<T:Comparable> { 
    //Value and children-parent vars 
    public var value:T 
    public var leftChild...

Rotations

Now, let's see the process that helps the red-black tree to balance (and therefore to maintain some of its color conditions): tree rotations.

Tree rotation is a mechanism that moves nodes of the tree to a different place in order to change the height of some of the nodes (and make it uniform among all the children). Let's see two different scenarios that we are going to use later in the insertion process: right rotation and left rotation.

Right rotation

We use a rotation to the right in the following scenario:

Right rotation in red-black trees

Here are the steps for right rotation:

1. Node X goes up to become the root of the new tree after the rotation (on the right side of the figure). Node Y, which was the parent of X, is now the right child (its value is greater, so it must be on the right subtree).

2. If node Y had a parent, we now assign that parent to node X.

3. The right child of node X is now the left child of its child node, Y.

Now, let's see how to implement this in Swift. Add a new...

Insertion

We have built a base class with some helper methods that represents a red-black tree node/tree. We also have an enumeration to handle the colors. We implemented two rotation methods: left and right. You are ready to learn about the insertion process.

The insertion process in the case of red-black trees is tricky, because we always need to maintain the five color conditions. The insertion process has different scenarios where it can impact those rules, so we have to make the process in a way that ensure the rules at all costs.

In order to simplify things, we are going to do the insertion in a two-step process:

1. Insert the node as we did in binary search trees, by setting the color red by default.

2. As it is possible that the first step destroyed one or more of the color rules, we will review the tree color structure and make modifications to fix those broken rules.

Let's add the following methods to the RedBlackTreeNode class:

// MARK: Insertion
//Insert operation methods 
public...

AVL trees

Invented by Georgy Adelson-Velski and Evgenii Landis, and named with their initials, AVL trees were the first self-balance binary search tree created.

AVL tree's special characteristic is if the height of a node subtree is N, the height of the other subtree of the same node must be in the range [N-1, N+1]. This means that heights of both children should differ at most one.

For example, if the height of the right subtree is 3, the height of the left subtree could be 2, 3, or 4. The difference between both heights is called the Balance factor:

Balance factor = Height(RightSubtree) - Height(LeftSubtree)

AVL tree example with balance factors of each node

In the preceding figure, the balance factor of a valid AVL tree is in the range [-1, 1] for every node. Leaves have a balance factor of 0.

• If Balance factor is < 0, the node is called left heavy

• If Balance factor is = 0, the node is called balanced

• If Balance factor is > 0, the node is called right heavy

If a child subtree doesn...

Trie tree

Until now, we have seen different types of trees, such as binary trees, binary search trees, red-black trees, and AVL trees. In all these types of tree, the content of a node (a value or a key) is not related to the content of a previous node. A single node has a complete meaning, such as a value or number by itself.

But in some scenarios in real life, we need to store a series of data in which those values have common parts; think of it as the suffixes or prefixes in related words, in the alphabet, in a telephone directory.

Here is where a trie tree shines. They are ordered data structures where edges contain part of a key and its descendant nodes have common share part of the previous values. Check this example out:

Trie tree example – storing the words plan, play, poll, post

As you can see in the previous figure, each edge of the tree contains part of a key, and by adding every edge key from the top to a specific node (or leaf), we can build a complete key.

Some implementations...

Radix tree

In trie tree, we have seen that each edge contains a single letter or single part of a key. Radix trees are like a compressed version of trie trees, where the edges can contain more than a single letter, even an entire word (if we are using them for words/letters).

This is very effective, reducing the amount of memory and space the tree needs. Let's see an example:

Trie tree (left) and radix tree (right) for the same input

In the preceding figure, you can view the difference between a trie tree and a radix tree for the same input data, PLAN, PLAY, POLL, and POST. Note the following:

• The radix version of the trie uses fewer nodes; one of the purposes of the radix trees is to reduce the amount of memory used. This is because each key has more information (each edge), so we need fewer edges.

• We can perform this compression of single letters to partial words in edges when a node has a single child. Note the trie tree edges [L ->A], [L -> L], and [S -> T] in the preceding figure...

A look at several substring search algorithms

In software programming, it is very common to find a situation where we need to search for the occurrences of a specific pattern of characters in a bigger text. We are going to see some types of search algorithm that will help us with this task.

In order to explain them, first we are going to specify some assumptions:

• The text is defined as an array T[1..n], with length n, which contains chars.

• The pattern that we are searching for is defined as an array P[1..m], with length m and m <= n.

• Where the pattern P exists in T, we call it shift s in T. In other words, the pattern P occurs in the s+1 position of the T array. So, this also implies that [1 < s < m-n] and also T[s+1 .. s+m] = P[1 .. m].

Look at the following figure to understand these concepts better:

Text, pattern, and shift example

The objective of every string matching algorithm is to find the different s positions in the text, T.

Substring search algorithm examples

Let's take a look...

Summary

In this chapter, you've learned about new advanced data structures, such as red-black trees, AVL trees, and trie trees. You also learned how to perform common operations on them, such as single and double rotations. We have seen in which specific cases we can benefit from them.

At the end of the chapter, we reviewed the general characteristics of substring search algorithms by showing the most common and basic concepts. Now you are going to be able to study in depth more complex string search algorithms with these a knowledge of fundamentals.

In the next chapter, you are going to learn about graph algorithms and the data structures used to implement them.