TECHY360
Everything You Need To Know About Tech

Binary search tree: Algorithms and data structures for beginners

0 8

So far, we have considered data structures in which data is arranged linearly. In the linked list – from the first node to the only last. In a dynamic array, in the form of a continuous block.

In this part, we will look at a completely new data structure – the tree. Or rather, the binary (binary) search tree (binary search tree). A binary search tree has a tree structure, but the elements in it are arranged according to certain rules.

For a start, we will look at a regular tree.

Trees

A tree is a structure in which each node can have zero or more nodes – “children”. For example, a tree might look like this:

This tree shows the structure of the company. Nodes represent people or divisions, lines — communications and relationships. A tree is the most efficient way to present and store such information.

Organization Structure
Organization Structure

The tree in the picture above is very simple. It reflects only the relationship of category kinship but does not impose any restrictions on its structure. A CEO may have one direct subordinate, or several or none. In the picture, the sales department is to the left of the marketing department, but the order doesn’t really matter. The only limitation of the tree is that each node can have at most one parent. The topmost node (the board of directors, in our case) has no parent. This node is called the “root” or “root.”

Binary search tree

The binary search tree is similar to the tree from the example above, but is built according to certain rules:

  • Each node has no more than two children.
  • Any value less than the value of the node becomes the left child or the child of the left child.
  • Any value greater than or equal to the value of the node becomes the right child or the child of the right child.

Let’s look at a tree built according to these rules:

Notice how these limitations affect the structure of the tree. Each value to the left of the root (8) is less than eight, each value to the right is greater than or equal to the root. This rule applies to any node in the tree.

Given this, let’s imagine how you can build such a tree. Since the tree was initially empty, the first added value — the eight — became its root.

We do not know exactly in which order the other values ​​were added, but we can imagine one of the possible ways. Nodes are added by a method Addthat accepts an added value.

BinaryTree tree = new BinaryTree ();
tree.Add (8);
tree.Add (4);
tree.Add (2);
tree.Add (3);
tree.Add (10);
tree.Add (6);
tree.Add (7);

Let’s take a closer look at the first steps.

The first is added 8. This value becomes the root of the tree. Then we add 4. Since 4 is less than 8, we put it in the child, according to rule 2. Since the node with the eight does not have children on the left, 4 becomes the only left child.

After that we add 2. 2 less than 8, so we go to the left. Since there is already a value on the left, we compare it with the inserted one. 2 is less than 4, and the four have no children on the left, so 2 becomes the left child 4.

Then we add the top three. She goes to the left of 8 and 4. But since 3 is more than 2, she becomes a right child 2, according to the third rule.

Sequential comparison of the inserted value with the potential parent continues until a place to insert is found, and is repeated for each inserted value until the entire tree is built.

Class BinaryTreeNode

A class BinaryTreeNoderepresents a single binary tree node. It contains links to the left and right subtrees (if there is no subtree, the link matters null), the node data and the method IComparable.CompareTofor comparing nodes. It is useful for determining which subtree this node should go to. As you can see, the class is BinaryTreeNodevery simple:

class BinaryTreeNode: IComparable
    where TNode: IComparable
{
    public BinaryTreeNode (TNode value)
    {
        Value = value;
    }
 
    public BinaryTreeNode Left {get; set; }
    public BinaryTreeNode Right {get; set; }
    public TNode Value {get; private set; }
 
    /// 
    /// Compares the current node with the given.
    /// 
    /// The comparison is made by the field Value.
    /// Method returns 1 if the value of the current node is greater than
    /// than passed to the method, -1 if less and 0 if they are equal
    public int CompareTo (TNode other)
    {
        return Value.CompareTo (other);
    }
}

Class BinaryTree

The class BinaryTreeprovides basic methods for manipulating data: inserting an element ( Add), deleting ( Remove), a method Containsto check if there is such a value in the tree, several methods for traversing the tree in various ways, a method Countand Clear.

In addition, the class has a link to the root node of the tree and the field with the total number of nodes.

public class BinaryTree: IEnumerable
    where T: IComparable
{
    private BinaryTreeNode _head;
    private int _count;
 
    public void Add (T value)
    {
        throw new NotImplementedException ();
    }
 
    public bool Contains (T value)
    {
        throw new NotImplementedException ();
    }
 
    public bool Remove (T value)
    {
        throw new NotImplementedException ();
    }
 
    public void PreOrderTraversal (Action action)
    {
        throw new NotImplementedException ();
    }
 
    public void PostOrderTraversal (Action action)
    {
        throw new NotImplementedException ();
    }
 
    public void InOrderTraversal (Action action)
    {
        throw new NotImplementedException ();
    }
 
    public IEnumerator GetEnumerator ()
    {
        throw new NotImplementedException ();
    }
 
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ()
    {
        throw new NotImplementedException ();
    }
 
    public void Clear ()
    {
        throw new NotImplementedException ();
    }
 
    public int Count
    {
        get;
    }

Add method

  • Behavior: Adds an item to the tree to the correct position.
  • Complexity: O (log n) on average; O (n) in the worst case.

Adding a node is easy. It becomes even easier if you solve this problem recursively. There are only two cases to consider:

  1. The tree is empty.
  2. The tree is not empty.

If the tree is empty, we simply create a new node and add it to the tree. In the second case, we compare the transferred value with the value in the node, starting from the root. If the value added is less than the value of the node in question, repeat the same procedure for the left subtree. Otherwise – for the right.

public void Add(T value)
{
    // Case 1: If the tree is empty, simply create a root node.
    if (_head == null)
    {
        _head = new BinaryTreeNode(value);
    }
    // Case 2: The tree is not empty =>
    // looking for the right place to insert.
    else
    {
        AddTo(_head, value);
    }
 
    _count++;
}
 
// Recursive rate.
private void AddTo(BinaryTreeNode node, T value)
{
    // Case 1: The inserted value is less than the value of the node
    if (value.CompareTo(node.Value) < 0)
    {
        // If there is no left subtree, add the value to the left child,
        if (node.Left == null)
        {
            node.Left = new BinaryTreeNode(value);
        }
        else
        {
            // otherwise repeat for the left subtree.
            AddTo(node.Left, value);
        }
    }
    // Case 2: The value to be inserted is greater than or equal to the value of the node
    else
    {
        // If there is no right subtree, add the value to the right child,
        if (node.Right == null)
        {
            node.Right = new BinaryTreeNode(value);
        }
        else
        {
            // otherwise repeat for the right subtree
            AddTo(node.Right, value);
        }
    }
}

Remove method

  • Behavior: Removes the first node with the specified value.
  • Complexity: O (log n) on average; O (n) in the worst case.

Removing a knot from a tree is one of those operations that seem simple, but in fact they contain a lot of pitfalls.

In general, the element removal algorithm looks like this:

  • Find the node to be deleted.
  • Remove it.

The first step is quite simple. We will look for a node search in the method Containsbelow. After we found the node that needs to be removed, we have three cases.

Case 1: The node being deleted does not have the right child.

Related Posts
1 of 6

In this case, we simply move the left child (if available) to the place of the deleted node. As a result, the tree will look like this:

Case 2: The removed node has only the right child, which, in turn, has no left child.

In this case, we need to move the right child of the node to be deleted (6) in its place. After deletion, the tree will look like this:

Case 3: The removed node has the first child who has a left child.

In this case, the place of the deleted node is occupied by the leftmost child of the right child of the deleted node.

Let’s see why this is so. We know about the following subtree starting with the node to be deleted:

  • All values ​​to the right of it are greater than or equal to the value of the node itself.
  • The smallest value of the right subtree is the leftmost one.

We must place in the place of the deleted node with a value less than or equal to any node to the right of it. To do this, we need to find the smallest value in the right subtree. Therefore, we take the leftmost node of the right subtree.

After removing a node, the tree will look like this:

Now that we know how to delete nodes, let’s look at the code that implements this algorithm.

Note that the method FindWithParent(see method Contains) returns the found node and its parent, since we have to replace the left or right child of the parent of the deleted node.

Of course, we can avoid this if we keep a reference to the parent in each node, but this will increase the memory consumption and complexity of all algorithms, despite the fact that the reference to the parent node is used only in one.

public bool Remove(T value)
{
    BinaryTreeNode current, parent;
 
    // Находим удаляемый узел.
    current = FindWithParent(value, out parent);
 
    if (current == null)
    {
        return false;
    }
 
    _count--;
 
    // Случай 1: Если нет детей справа, левый ребенок встает на место удаляемого.
    if (current.Right == null)
    {
        if (parent == null)
        {
            _head = current.Left;
        }
        else
        {
            int result = parent.CompareTo(current.Value);
            if (result > 0)
            {
                // Если значение родителя больше текущего,
                // левый ребенок текущего узла становится левым ребенком родителя.
                parent.Left = current.Left;
            }
            else if (result < 0) { 
// If the value of the parent is less than the current one, 
// the left child of the current node becomes the right child. parent. 
                 parent.Right = current.Left; 
             } 
       }
   } 
// Light 2: If the right child has no children on the left // then it takes the place of the node to be deleted. 
    else if (current.Right.Left == null) { 
            current.Right.Left = current.Left; 
            if (parent == null) { 
                _head = current.Right; 
            } else { 
                int result = parent.CompareTo(current.Value); 
                if (result > 0)
                {
                // If the parent is greater than the current value,
                // the right child of the current node becomes the left child of the parent.
                parent.Left = current.Right;
            }
            else if (result < 0) { // If the value of the parent is less than the current, // the right child of the current node becomes the right child of the parent. parent.Right = current.Right; }}} // Case 3: If the right child has children on the left, the leftmost child // from the right subtree replaces the node to be deleted. else {// Find the leftmost node. BinaryTreeNode leftmost = current.Right.Left; BinaryTreeNode leftmostParent = current.Right; while (leftmost.Left! = null) {leftmostParent = leftmost; leftmost = leftmost.Left; } // The left subtree of the parent becomes the right subtree of the leftmost node. leftmostParent.Left = leftmost.Right; // The left and right child of the current node becomes the left and right child of the leftmost one. leftmost.Left = current.Left; leftmost.Right = current.Right; if (parent == null) {_head = leftmost; } else {int result = parent.CompareTo (current.Value); if (result> 0)
            {
                
                 // If the value of the parent is greater than the current,
                // leftmost node becomes the left child of the parent.
                parent.Left = leftmost;
            }
            else if (result <0)
            {
                // If the value of the parent is less than the current,
                // the leftmost node becomes the right child of the parent.
                parent.Right = leftmost;
            }
        }
    }
 
    return true;
}

Contains method

  • Behavior: Returns trueif the value is contained in the tree. Otherwise it returns false.
  • Complexity: O (log n) on average; O (n) in the worst case.

The method Containsis performed using the method FindWithParentthat passes through the tree, performing the following steps at each node:

  1. If the current node null, return null.
  2. If the current ticker value is equal to the required one, return the current node.
  3. If the desired value is less than the value of the current node, set the left child to the current node and go to step 1.
  4. Otherwise, set the right child to the current node and go to step 1.

Because it Containsreturns a boolean value, it is determined by comparing the result of the execution FindWithParentwith null. If FindWithParentreturned a non-empty node, Containsreturns true.

The method is FindWithParentalso used in the method Remove.

public bool Contains (T value)
{
    // Search for a node by another method.
    BinaryTreeNode parent;
    return FindWithParent (value, out parent)! = null;
}
 
///
/// Finds and returns the first node with the specified value. If value
/// not found, returns null. Also returns the parent of the found node (or null)
/// for use in the Remove method.
///
private BinaryTreeNode FindWithParent (T value, out BinaryTreeNode parent)
{
    // Try to find the value in the tree.
    BinaryTreeNode current = _head;
    parent = null;
 
    // Until you find ...
    while (current! = null)
    {
        int result = current.CompareTo (value);
 
        if (result> 0)
        {
            // If the desired value is less, go left.
            parent = current;
            current = current.Left;
        }
        else if (result <0)
        {
            // If the desired value is greater, go to the right.
            parent = current;
            current = current.Right;
        }
        else
        {
            // If equal, then stop
            break;
        }
    }
 
    return current;
}

Count method

  • Behavior: Returns the number of tree nodes, or 0 if the tree is empty.
  • Difficulty: O (1)

This field is incremented by the method Addand decremented by the method Remove.

public int Count
{
    get
    {
        return _count;
    }
}

Clear method

  • Behavior: Removes all tree nodes.
  • Difficulty: O (1)
public void Clear ()
{
    _head = null;
    _count = 0;
}

Tree walk

Tree traversal is a family of algorithms that allow each node to be processed in a specific order. For all traversal algorithms below, the following tree will be used as an example:

The traversal methods in the examples will take a parameter Action<T>that defines the action that is performed on each node.

Also, in addition to the description of the behavior and the algorithmic complexity of the method, the order of values ​​obtained during the traversal will be indicated.

Preorder method (or prefix traversal)

  • Behavior: Traversing the tree in the prefix order, performing the specified action on each node.
  • Difficulty: O (n)
  • Bypass order: 4, 2, 1, 3, 5, 7, 6, 8

In a prefix traversal, the algorithm gets the value of the current node before moving to the left subtree first, and then to the right subtree. Starting from the root, we first get the value 4. Then the left child and his children are treated in the same way, then the right child and all his children.

Prefix traversal is usually used to copy a tree while preserving its structure.

public void PreOrderTraversal (Action action)
{
    PreOrderTraversal (action, _head);
}
 
private void PreOrderTraversal (Action action, BinaryTreeNode node)
{
    if (node! = null)
    {
        action (node.Value);
        PreOrderTraversal (action, node.Left);
        PreOrderTraversal (action, node.Right);
    }
}

Postorder method (or postfix traversal)

  • Behavior: Traversing the tree in the prefix order, performing the specified action on each node.
  • Difficulty: O (n)
  • Bypass order: 1, 3, 2, 6, 8, 7, 5, 4

In a postfix traversal, we visit the left subtree, the right subtree, and then, after traversing all the children, go to the node itself.

Postfix traversal is often used to completely remove a tree, since in some programming languages ​​it is necessary to remove all nodes from memory explicitly, or to remove a subtree. Since the root in this case is processed last, we thus reduce the work necessary to remove the nodes.

public void PostOrderTraversal (Action action)
{
    PostOrderTraversal (action, _head);
}
 
private void PostOrderTraversal (Action action, BinaryTreeNode node)
{
    if (node! = null)
    {
        PostOrderTraversal (action, node.Left);
        PostOrderTraversal (action, node.Right);
        action (node.Value);
    }
}

Inorder method (or infix traversal)

  • Behavior: Traversing the tree in infix order, performing the specified action on each node.
  • Difficulty: O (n)
  • Bypass order: 1, 2, 3, 4, 5, 6, 7, 8

The infix traversal is used when we need to traverse the tree in the order corresponding to the node values. In the example above, the tree contains numerical values, so we go around them from the smallest to the largest. That is, from the left subtrees to the right through the root.

The example below shows two infix traversal methods. The first is recursive. It performs the specified action with each node. The second uses the stack and returns an iterator for brute force.

Public void InOrderTraversal (Action action)
{
    InOrderTraversal (action, _head);
}
 
private void InOrderTraversal (Action action, BinaryTreeNode node)
{
    if (node! = null)
    {
        InOrderTraversal (action, node.Left);
 
        action (node.Value);
 
        InOrderTraversal (action, node.Right);
    }
}
 
public IEnumerator InOrderTraversal ()
{
    // This is a non-recursive algorithm.
    // It uses the stack to avoid recursion.
    if (_head! = null)
    {
        // Stack to save missing nodes.
        Stack stack = new Stack ();
 
        BinaryTreeNode current = _head;

        // When we get rid of recursion, we need
        // remember which direction we should go.
        bool goLeftNext = true;
 
        // Put the root on the stack.
        stack.Push (current);
 
        while (stack. count> 0)
        {
            // If we go left ...
            if (goLeftNext)
            {
                // Put everything except the leftmost node on the stack.
                // We will return the leftmost node with yield.
                while (current.Left! = null)
                {
                    stack.Push (current);
                    current = current.Left;
                }
            }
 
            // Prefix order: left-> yield-> right.
            yield return current.Value;
 
            // If we can go to the right, let's go.
            if (current.Right! = null)
            {
                current = current.Right;
 
                // After we went right once
                // we have to go left again.
                goLeftNext = true;
            }
            else
            {
                // If we can't go to the right, we need to reach the parent node
                // from the stack, process it and go to its right child.
                current = stack.Pop ();
                goLeftNext = false;
            }
        }
    }
}

GetEnumerator method

  • Behavior: Returns an iterator to traverse the tree in an infix way.
  • Difficulty: Getting an iterator – O (1). Traversing the tree – O (n).
public IEnumerator GetEnumerator ()
{
    return InOrderTraversal ();
}
 
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ()
{
    return GetEnumerator ();
}

To be continued

This concludes the fifth part of the guide to algorithms and data structures. In the next article, we will look at the Set.

Get real time updates directly on you device, subscribe now.

Comments
Loading...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More