Sat
04
Feb 2012

What are the ways of storing a tree data structure in memory? I mean a tree with arbitrary number of child nodes. Probably first thing that comes to our minds - as high level programmers - is to dynamically allocate each node as object of some class that would store its data and a collection of pointers to its children. Opposite approach would be to store all nodes in some array - a continuous piece of memory, where each node would refer to other nodes by index or something. Third approach - something in between in terms of sophistication, as well as efficiency - is to have dynamically allocated nodes, but not to store a collection of all child nodes. It is a good idea to employ kind of linked list here. I'd like to describe such data structure and basic algorithms for manipulating it.

The idea is that each node stores - besides its data - 5 pointers (possibly null) to some other nodes: parent, previous sibling, next sibling, first child and last child. It could be seen as equivalent to doubly linked list. It has much more pointers that is needed to be able to traverse whole tree, but thanks to this you can traverse such tree in any order, as well as insert and remove nodes at any point, with best possible time complexity. A node with Parent == null is considered a tree root. Here is a picture of a single node and example tree:

Algorithms for manipulating such tree - inserting and removing nodes - are simple, but you have to be careful to always modify pointers correctly and consider all possible cases. Here is my implementation of a tree node class in C#:

public class Node
{
    public int SomeNodeData { get; set; }
    
    public Node Parent { get { return m_Parent; } }
    public Node PrevSibling { get { return m_PrevSibling; } }
    public Node NextSibling { get { return m_NextSibling; } }
    public Node FirstChild { get { return m_FirstChild; } }
    public Node LastChild { get { return m_LastChild; } }
    public bool Root { get { return Parent == null; } }

    /// <summary>
    /// Remove this and all its children from the tree.
    /// It will become root of a separate tree.
    /// </summary>
    public void Remove()
    {
        // I already am root of separate tree.
        if (Parent == null)
            return;

        if (m_PrevSibling != null)
            m_PrevSibling.m_NextSibling = m_NextSibling;
        else
            m_Parent.m_FirstChild = m_NextSibling;

        if (m_NextSibling != null)
            m_NextSibling.m_PrevSibling = m_PrevSibling;
        else
            m_Parent.m_LastChild = m_PrevSibling;

        m_PrevSibling = null;
        m_NextSibling = null;
        m_Parent = null;
    }

    /// <summary>
    /// Clear children list.
    /// Child nodes will be in invalid state!
    /// </summary>
    public void RemoveAllChildren()
    {
        m_FirstChild = m_LastChild = null;
    }

    /// <summary>
    /// Insert given node as first child of this node.
    /// </summary>
    /// <param name="newNode">Must be valid root of separate tree. Can have children.</param>
    public void InsertFirstChild(Node newNode)
    {
        newNode.m_Parent = this;
        newNode.m_NextSibling = m_FirstChild;

        if (m_FirstChild != null)
            m_FirstChild.m_PrevSibling = newNode;
        else
            m_LastChild = newNode;

        m_FirstChild = newNode;
    }

    /// <summary>
    /// Insert given node as last child of this node.
    /// </summary>
    /// <param name="newNode">Must be valid root of separate tree. Can have children.</param>
    public void InsertLastChild(Node newNode)
    {
        newNode.m_Parent = this;
        newNode.m_PrevSibling = m_LastChild;

        if (m_LastChild != null)
            m_LastChild.m_NextSibling = newNode;
        else
            m_FirstChild = newNode;

        m_LastChild = newNode;
    }

    /// <summary>
    /// Insert given node as previous sibling of this node.
    /// </summary>
    /// <param name="newNode">Must be valid root of separate tree. Can have children.</param>
    public void InsertPrevSibling(Node newNode)
    {
        newNode.m_Parent = m_Parent;
        newNode.m_PrevSibling = m_PrevSibling;
        newNode.m_NextSibling = this;

        if (m_PrevSibling != null)
            m_PrevSibling.m_NextSibling = newNode;
        else
            m_Parent.m_FirstChild = newNode;

        m_PrevSibling = newNode;
    }

    /// <summary>
    /// Insert given node as next sibling of this node.
    /// </summary>
    /// <param name="newNode">Must be valid root of separate tree. Can have children.</param>
    public void InsertNextSibling(Node newNode)
    {
        newNode.m_Parent = m_Parent;
        newNode.m_NextSibling = m_NextSibling;
        newNode.m_PrevSibling = this;

        if (m_NextSibling != null)
            m_NextSibling.m_PrevSibling = newNode;
        else
            m_Parent.m_LastChild = newNode;

        m_NextSibling = newNode;
    }

    /// <summary>
    /// 
    /// </summary>
    /// <returns>Returns true if this node is valid comparing to its surrounding.</returns>
    public bool NodeValid()
    {
        // This is root node.
        if (Parent == null)
        {
            // Must not have siblings.
            if (PrevSibling != null || NextSibling != null)
                return false;
        }
        // This is not root node.
        else
        {
            // Parent must have some children.
            if (Parent.FirstChild == null || Parent.LastChild == null)
                return false;
        }

        if (PrevSibling != null)
        {
            // My prev sibling must point to me.
            if (PrevSibling.NextSibling != this)
                return false;
            // My prev sibling must point to same parent.
            if (PrevSibling.Parent != Parent)
                return false;
            // I can't be first child of my parent.
            if (Parent != null && Parent.FirstChild == this)
                    return false;
        }
        else
        {
            // I must be first child of my parent.
            if (Parent != null && Parent.FirstChild != this)
                    return false;
        }

        if (NextSibling != null)
        {
            // My next sibling must point to me.
            if (NextSibling.PrevSibling != this)
                return false;
            // My next sibling must point to same parent.
            if (NextSibling.Parent != Parent)
                return false;
            // I can't be last child of my parent.
            if (Parent != null && Parent.LastChild == this)
                return false;
        }
        else
        {
            // I must be last child of my parent.
            if (Parent != null && Parent.LastChild != this)
                return false;
        }

        // I have some children.
        if (FirstChild != null)
        {
            // I must have both FirstChild and LastChild set.
            if (LastChild == null)
                return false;

            // My first child must point to me.
            if (FirstChild.Parent != this)
                return false;
            // My first child must not have prev sibling.
            if (FirstChild.PrevSibling != null)
                return false;

            // My last child must point to me.
            if (LastChild.Parent != this)
                return false;
            // My last child must not have next sibling.
            if (LastChild.NextSibling != null)
                return false;
        }
        // I have no children.
        else
        {
            // I must have neither FirstChild nor LastChild set.
            if (LastChild != null)
                return false;
        }

        return true;
    }

    /// <summary>
    /// 
    /// </summary>
    /// <returns>Returns true if this node and all child nodes recursively are valid.</returns>
    public bool TreeValid()
    {
        if (!NodeValid())
            return false;

        for (Node childNode = FirstChild; childNode != null; childNode = childNode.NextSibling)
            if (!childNode.TreeValid())
                return false;

        return true;
    }

    private Node m_Parent;
    private Node m_PrevSibling, m_NextSibling;
    private Node m_FirstChild, m_LastChild;
}

Comments | #algorithms #.net Share

Comments