Implementation of a AVL Tree

Question

I attempted to write a AVL Tree in a functional style and I am hoping to get it reviewed. I am looking for the code to be clear and concise, any opportunity for improvement would be greatly appreciated!

This is the general binary tree class. I just left the insertion portion in the class to keep it easier to look at:

 public class Tree
{
    public Node RootNode;
    public Tree(int value)
    {
        this.RootNode = new Node(value);
    }

    public Tree(Node node)
    {
        RootNode = node;
    }

    public Tree()
    {
        RootNode = new Node();
    }

    public void InsertValue(int value)
    {
        InsertValue(RootNode, value);
    }

    public void InsertValue(Node currentNode, int value)
    {

        int comparison = value.CompareTo(currentNode.Value);

        if (comparison == -1)
        {
            if (currentNode.LeftNode == null)
            {
                currentNode.LeftNode = new Node(value);
            }
            else
            {
                InsertValue(currentNode.LeftNode, value);
            }
        }
        else if (comparison == 1)
        {
            if (currentNode.RightNode == null)
            {
                currentNode.RightNode = new Node(value);
            }
            else
            {
                InsertValue(currentNode.RightNode, value);
            }
        }
    }

    public int GetMaxDepth(Node node)
    {
        return GetMaxDepth(node, 1);
    }

    public int GetMaxDepth(Node node, int depth)
    {
        if (node.RightNode == null && node.LeftNode == null)
            return depth;

        int right = 0;
        if (node.RightNode != null)
            right = GetMaxDepth(node.RightNode, depth + 1);

        int left = 0;
        if (node.LeftNode != null)
            left = GetMaxDepth(node.LeftNode, depth + 1);

        if (right < left)
        {
            return left;
        }
        else
        {
            return right;
        }
    }

    public Node GetTargetNode(Queue<bool> nav)
    {
        var temp = getTargetNode(nav, RootNode);
        return temp;
    }

    private Node getTargetNode(Queue<bool> navigation, Node node)
    {
        if (node == null || navigation.Count == 0)
            return node;

        //Going right:
        if (navigation.Dequeue())
        {
            var temp = getTargetNode(navigation, node.RightNode);
            return temp;
        }
        else
        {
            var temp = getTargetNode(navigation, node.LeftNode);
            return temp;
        }
    }

}

public class Node
{
    public int? Value;
    public Node LeftNode;
    public Node RightNode;

    public Node()
    {

    }

    public Node(int? value)
    {
        Value = value;
    }
}

Here is the AVL Portion that balances the tree via Rotations either right or left:

public class AVLSelfBalance
{
    public Node RootNode = new Node();

    public AVLSelfBalance(Node rootNode)
    {
        this.RootNode = rootNode;
    }

    public AVLSelfBalance()
    {

    }

    public void InsertValue(int value)
    {
        RootNode = InsertValue(RootNode, value);
    }

    public Node InsertValue(Node currentNode, int value)
    {

        //Insert the RootNode:
        int comparison = value.CompareTo(currentNode.Value);

        if (comparison == -1)
        {
            if (currentNode.LeftNode == null)
            {
                currentNode.LeftNode = new Node(value);
            }
            else
            {
                currentNode.RightNode = InsertValue(currentNode.LeftNode, value);
            }
        }
        else if (comparison == 1)
        {
            if (currentNode.RightNode == null)
            {
                currentNode.RightNode = new Node(value);
            }
            else
            {
                currentNode.RightNode = InsertValue(currentNode.RightNode, value);
            }
        }

        //Check Balance of the tree and rotate if needed:
        var balanceValue = GetBalanceValue(currentNode);

        if (balanceValue <= -2)
           currentNode = Rotate(currentNode, true);

        if (2 <= balanceValue)
            currentNode = Rotate(currentNode, false);

        return currentNode;
    }

    public int GetBalanceValue(Node node)
    {
        var leftDepth = 0;
        var rightDepth = 0;

        if (node.LeftNode != null)
            leftDepth = GetMaxDepth(node.LeftNode) + 1;

        if(node.RightNode != null)
            rightDepth = GetMaxDepth(node.RightNode) + 1;

        return leftDepth - rightDepth;
    }

    public int GetMaxDepth(Node node)
    {
        if (node != null)
            return GetMaxDepth(node, 0);

        return 0;
    }


    public int GetMaxDepth(Node node, int depth)
    {
        int right = 0;
        int left = 0;

        if (node.RightNode != null)
        {
            right = GetMaxDepth(node.RightNode, depth + 1);
        }

        if (node.LeftNode != null)
        {
            left = GetMaxDepth(node.LeftNode, depth + 1);
        }

        if (left > right)
        {
            return left;
        }
        else if (left <= right && right != 0)
        {
            return right;
        }

        return depth;
    }

    public Node Rotate(Node node, bool rotateRight)
    {
        bool goRight = false;

        if (rotateRight)
            goRight = rotateRight;

        Tree t = new Tree(node);
        //Move from the children to the root:
        //Get Children of Children
        var orphanChild = t.GetTargetNode(new Queue<bool>(new[] { goRight, !goRight}));
        //Get Direct Children
        var newLeftChild = node;
        var tailOfRoot = t.GetTargetNode(new Queue<bool>(new[] { goRight, goRight}));
        //Get New Root
        var newRoot = t.GetTargetNode(new Queue<bool>(new[] { goRight}));


        //Perform Rotation:
        //Attach Children of Children to Direct Children
        if (goRight)
        {
            newLeftChild.RightNode = orphanChild;
        }
        else
        {
            newLeftChild.LeftNode = orphanChild;
        }

        //Attach Children to Root:
        if (goRight)
        {
            newRoot.LeftNode = newLeftChild;
            newRoot.RightNode = tailOfRoot;
        }
        else
        {
            newRoot.RightNode = newLeftChild;
            newRoot.LeftNode = tailOfRoot;
        }

        return newRoot;
    }
}

Answer 1

public Node RootNode;

Don't use public fields, use public auto-properties instead and think whether that auto-property needs a public setter.

---

this.RootNode = new Node(value);
RootNode = node;

Why are you sometimes using this and sometimes not? People disagree about which style is better, but you should pick just one style and stick to it.

---

public Tree()
{
    RootNode = new Node();
}

I don't quite understand what is the intended behavior of this "empty node", since it looks like the empty node behaves just like any other node. Instead, I think that empty nodes shouldn't be allowed, but empty tree (i.e. one where RootNode is null) should.

---

int comparison = value.CompareTo(currentNode.Value);

if (comparison == -1)
{
    …
}
else if (comparison == 1)
{
    …
}

int.CompareTo() is not guaranteed to return -1, 0 or 1, it can return any int, so you should use comparison < 0 and comparison > 0 here.

Also, if you're going to stick with ints (see below), I think just using value < currentNode.Value and value > currentNode.Value is much clearer.

---

public int GetMaxDepth(Node node, int depth)

I don't understand why is this method so complicated, you could simplify it to just this:

public int GetMaxDepth(Node node)
{
    if (node == null)
        return 0;

    return Math.Max(GetMaxDepth(node.LeftNode), GetMaxDepth(node.RightNode)) + 1;
}

---

var temp = getTargetNode(nav, RootNode);
return temp;

The temp variable doesn't serve any purpose here, get rid of it:

return getTargetNode(nav, RootNode);

Also, it's usually better not to shorten names to things like nav, those few additional characters will make the code more readable.

---

if (node == null || navigation.Count == 0)
    return node;

I think reaching null node should throw a descriptive exception, not just return null.

---

if (navigation.Dequeue())
{
    var temp = getTargetNode(navigation, node.RightNode);
    return temp;
}
else
{
    var temp = getTargetNode(navigation, node.LeftNode);
    return temp;
}

Try to avoid duplicated code, for example like this:

var nextNode = navigation.Dequeue() ? node.RightNode : node.LeftNode;

return getTargetNode(navigation, nextNode);

(I'm usually not a big fan of the ternary operator, but I think it's the best choice here.)

---

public int? Value;

Why does Value have to be an int? I think that these classes are very suitable for generics.

---

public class AVLSelfBalance

That's a weird name: it doesn't say what this class actually represents (a tree), while the SelfBalance part doesn't actually add anything, since AVL trees are always self-balanced. A better name would be AVLTree.

Also, have you considered making this class inherit from Tree? That way, you could share some of the code and it would also mean that the two classes are interchangeable.

---

//Check Balance of the tree and rotate if needed:
var balanceValue = GetBalanceValue(currentNode);

Doing this will negate any performance (and time complexity) benefits from using AVL tree, because now every insert requires an \$\mathcal{O}(n)\$ operation: finding the balance.

What you need to do is to store the depth in each node and change it when it changes due to insertion or rotation. With that computing the balance value of a node becomes \$\mathcal{O}(1)\$ operation.

---

bool goRight = false;

if (rotateRight)
    goRight = rotateRight;

This can be simplified to just:

bool goRight = rotateRight;

---

Tree t = new Tree(node);
…
t.GetTargetNode(…);

This is a weird way to do this. I would probably just change Tree.getTargetNode() into a public static method, and use it here.

---

var orphanChild = t.GetTargetNode(new Queue<bool>(new[] { goRight, !goRight}));
var tailOfRoot = t.GetTargetNode(new Queue<bool>(new[] { goRight, goRight}));
var newRoot = t.GetTargetNode(new Queue<bool>(new[] { goRight}));

This looks like an interesting attempt at avoiding duplicated code, but I don't think its much of a success, because of its verbosity.

What you could do instead is to add method like this to Node:

public Node GetChild(bool right)
{
    return right ? RightNode : LeftNode;
}

With that, the above code could be simplified to:

var newRoot = node.GetChild(goRight);
var orphanChild = newRoot.GetChild(!goRight);
var tailOfRoot = newRoot.GetChild(goRight);

And you could also create public void SetChild(bool right, Node newNode) to avoid repetition in the last part of the code.