Fun with Binary Search Trees
Ξ September 29th, 2008 | → 1 Comments | ∇ .Net Framework, Algorithms |
It has been a long while since I actually got to implement some tree data structures, and in order not to get rusty, I’ve decided to try to create a simple Binary Search Tree in C#. My main goals for this piece of code was to create a BST in one of the most general ways possible. This being said, I’ve decided to use generic classes to define the
structure. As a quick reminder, I will provide the Wikipedia definition for a Binary Search Tree:
In computer science, a binary search tree (BST) is a binary tree data structure which has the following properties:
- each node (item in the tree) has a value;
- a total order (linear order) is defined on these values;
- the left subtree of a node contains only values less than the node’s value;
- the right subtree of a node contains only values greater than or equal to the node’s value.
The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.
I’ve decided to create 2 classes, a Node class that will represent the tree node abstraction and a BinarySearchClass that will represent the binary search tree abstraction. Both classes are generic. The Node class implements the IComparable<T> interface with the restriction that the type parameter must also implement the IComparable interface. This is required because while performing various operations on the BST, several comparisons will be performed on the information field of the node.
namespace TreeUtility { using System; /// <summary> /// Represents a tree node /// </summary> /// <typeparam name="T">Specifies the element type of the tree</typeparam> public class Node<T> : IComparable<T> where T : IComparable { /// <summary> /// Gets or sets the node information /// </summary> public T Info { get; set; } /// <summary> /// Gets the node level /// </summary> public int Level { get; internal set; } /// <summary> /// Gets or sets the left node /// </summary> public Node<T> Left { get; set; } /// <summary> /// Gets or sets the right node /// </summary> public Node<T> Right { get; set; } /// <summary> /// Gets or sets the node's parent /// </summary> public Node<T> Parent { get; set; } /// <summary> /// Creates a new instance of the Node class /// </summary> /// <param name="info">The value of the new node</param> public Node(T info) { if (info == null) { throw new ArgumentNullException("info"); } Info = info; Level = 0; } /// <summary> /// Creates a new instance of the Node class /// </summary> /// <param name="info">The value of the new node</param> /// <param name="parent">The parent of the new node</param> /// <remarks>This constructor sets the node level based on the parent's level</remarks> internal Node(T info, Node<T> parent) { this.Info = info; this.Parent = parent; if (parent != null) { this.Level = parent.Level + 1; } else { this.Level = 0; } } /// <summary> /// Creates a new instance of the Node class /// </summary> /// <param name="info">The value of the new node</param> /// <param name="level">The level of the new node</param> internal Node(T info, int level) { if (info == null) { throw new ArgumentNullException("info"); } Info = info; Level = level; } #region IComparable<T> Members /// <summary> /// Compares this instance to an another instance and returns an indication /// of their relative values /// </summary> /// <param name="other">An instance to compare</param> /// <returns>An indication of the object's relative values</returns> public int CompareTo(T other) { return other.CompareTo(this.Info); } #endregion /// <summary> /// Formats the string value to be displayed for the current instance /// </summary> /// <returns>The formated string</returns> internal string ToFormatedString() { return "".PadLeft(Level, '+') + Info.ToString(); } } }
And here is the code for the actual Binary Search tree class:
namespace TreeUtility { using System; using System.Text; /// <summary> /// Represents a binary search tree /// </summary> /// <typeparam name="T">Specifies the element type of the binary search tree</typeparam> public partial class BinarySearchTree<T> where T : IComparable { /// <summary> /// The root of the BST /// </summary> private Node<T> root; /// <summary> /// Adds a new node to the BST /// </summary> /// <param name="info">The value of the new node</param> public void Add(T info) { // check if the root is null. if (root == null) { // If it is, create the new tree root root = new Node<T>(info); } else { Node<T> iterator = root; Node<T> previous = root; // Search the appropriate place where to add the new node while (iterator != null) { if (iterator.CompareTo(info) < 0) { // if the value is smaller, go to the left subtree previous = iterator; iterator = iterator.Left; } else if (iterator.CompareTo(info) > 0) { // if the value is larger, go to the right subtree previous = iterator; iterator = iterator.Right; } else { // else break the execution break; } } // update the parent's links if (previous.CompareTo(info) < 0) { previous.Left = new Node<T>(info, previous); } else { previous.Right = new Node<T>(info, previous); } } // rebalance the tree BalanceTree(); } /// <summary> /// Removes a node from the BST /// </summary> /// <param name="info">The value used to search the node to be removed</param> public void Remove(T info) { if (root == null) { throw new InvalidOperationException("Cannot remove an item from an empty tree"); } else { // Search for the node to be deleted Node<T> toDelete = Search(info); // Get the leftmost child of the node Node<T> leftmost = GetLeftMostNode(toDelete); // Get the rightmost child of the node Node<T> rightmost = GetRightMostNode(toDelete); // Node that will contain the max between the leftmost // and rightmost children Node<T> max; // if both are null, just delete the node if (leftmost == null && rightmost == null) { toDelete = null; return; } else if (leftmost != null && rightmost != null) // else get the max { max = leftmost.Level > rightmost.Level ? leftmost : rightmost; } else { max = leftmost == null ? rightmost : leftmost; } // Update the max parent's links RemoveLinks(max); // Update the node's links max.Parent = toDelete.Parent; max.Left = toDelete.Left; max.Right = toDelete.Right; max.Level = toDelete.Level; // Update the node's new parent links if (max.Parent == null) { root = max; } else if (toDelete.Parent.Left == toDelete) { toDelete.Parent.Left = max; } else { toDelete.Parent.Right = max; } // delete the old node toDelete = null; // rebalance the tree BalanceTree(); } } /// <summary> /// Removes the links of a node /// </summary> /// <param name="node">The node for which the links will be removed</param> private void RemoveLinks(Node<T> node) { Node<T> parent = node.Parent; if (parent.Left == node) { parent.Left = node.Left != null ? node.Left : node.Right; } else { parent.Right = node.Left != null ? node.Left : node.Right; } } /// <summary> /// Searches the tree for a node containing the specified value /// </summary> /// <param name="info">The value to be searched for</param> /// <returns>The node with the specified value, or null if no node was found</returns> public Node<T> Search(T info) { Node<T> iterator = root; while (iterator != null) { if (iterator.CompareTo(info) < 0) { iterator = iterator.Left; } else if (iterator.CompareTo(info) > 0) { iterator = iterator.Right; } else { return iterator; } } return null; } /// <summary> /// Gets the rightmost node from the specified node /// </summary> /// <param name="node">The node used to begin the search</param> /// <returns>The rightmost node of the tree with the specified node as root</returns> internal Node<T> GetRightMostNode(Node<T> node) { Node<T> iterator = node; Node<T> previous = node; while (iterator != null) { previous = iterator; iterator = iterator.Right; } return previous; } /// <summary> /// Gets the leftmost node from the specified node /// </summary> /// <param name="node">The node used to begin the search</param> /// <returns>The leftmost node of the tree with the specified node as root</returns> internal Node<T> GetLeftMostNode(Node<T> node) { Node<T> iterator = node; Node<T> previous = node; while (iterator != null) { previous = iterator; iterator = iterator.Left; } return previous; } /// <summary> /// Converts the BST to a string /// </summary> /// <returns>The string representation of the object</returns> public new string ToString() { StringBuilder sb = new StringBuilder(); GetString(root, sb); return sb.ToString(); } /// <summary> /// Method used construct recursivly the string representation of the BST /// </summary> /// <param name="node">The root of tree</param> /// <param name="sb">A string builder helper object</param> private void GetString(Node<T> node, StringBuilder sb) { if (node != null) { GetString(node.Left, sb); sb.AppendLine(node.ToFormatedString()); GetString(node.Right, sb); } } // Method used to balace the tree partial void BalanceTree(); } }
Note that I didn’t implement the actual balance tree operation, but I defined it as a partial method. In this case, a custom balancing algorithm can be used. Finally, let us look over a method used to test the functionality of the newly created classes.
namespace TreeUtility { using System; class Program { static void Main(string[] args) { Test(); Console.ReadKey(true); } /// <summary> /// Tests the functionality of the BST /// </summary> static void Test() { // Creates an initial array int[] numbers = { 8, 1, 5, 7, 2, 3, 9, 10, 2, 4, 6, 12 }; // Creates a new instance for of a BST BinarySearchTree<int> bst = new BinarySearchTree<int>(); // Adds some new elements in the tree foreach (int number in numbers) { bst.Add(number); } // removes an element from the tree bst.Remove(1); // Displays the trees structure Console.WriteLine(bst.ToString()); } } }
This being said, I will conclude this post by stating that I will provide some additional posts that will extend the functionality provided by this classes.
on August 5th, 2009 at 5:12 pm
[...] time ago I wrote a post showing how to implement a generic binary search tree data structure in C#. In today’s post I will provide a way of extending the binary data structure [...]