AVL Tree

avl_tree.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SearchTree2
{
    public class AVLNode
    {
        public AVLNode parent { get; set; }
        public AVLNode left { get; set; }
        public AVLNode right { get; set; }
        public int data { get; set; }
        public int height = 1;
    }

    public class AVLBinaryTree
    {
        private AVLNode node = new AVLNode();
        private int count = 0;

        private bool isLeftChild(AVLNode elem)
        {
            if (Object.ReferenceEquals(elem, elem.parent.right))
                return false;
            return true;
        }

        public void add(int item)
        {
            if (count == 0)
            {
                count++;
                node.data = item;
                node.parent = node;
                return;
            }
            AVLNode curr_node = this.node;
            while (true)
            {
                if (item < curr_node.data)
                {
                    if (curr_node.left == null)
                    {
                        curr_node.left = new AVLNode();
                        curr_node.left.data = item;
                        curr_node.left.parent = curr_node;
                        count++;
                        fullBalance(curr_node);
                        break;
                    }
                    else
                        curr_node = curr_node.left;
                }
                else if (item > curr_node.data)
                {
                    if (curr_node.right == null)
                    {
                        curr_node.right = new AVLNode();
                        curr_node.right.data = item;
                        curr_node.right.parent = curr_node;
                        count++;
                        fullBalance(curr_node);
                        break;
                    }
                    else
                        curr_node = curr_node.right;
                }
                else break;
            }
        }
        public bool search(int item)
        {
            AVLNode curr_node = node;
            while (true)
            {
                if (curr_node == null)
                {
                    return false;
                }
                else if (curr_node.data == item)
                {
                    return true;
                }
                else if (item < curr_node.data)
                {
                    curr_node = curr_node.left;
                }
                else if (item > curr_node.data)
                {
                    curr_node = curr_node.right;
                }
            }
        }
        public void remove(int item)
        {
            AVLNode curr_node = node;
            while (true)
            {
                if (curr_node.data == item)
                {
                    bool isLeftChild = true;
                    if (Object.ReferenceEquals(curr_node, curr_node.parent.right))
                        isLeftChild = false;

                    if (curr_node.left == null && curr_node.right == null)
                    {
                        if (isLeftChild)
                            curr_node.parent.left = null;
                        else
                            curr_node.parent.right = null;
                        fullBalance(curr_node);
                        count--;
                        return;
                    }
                    else if (curr_node.left == null && curr_node.right != null)
                    {
                        if (isLeftChild)
                            curr_node.parent.left = curr_node.right;
                        else
                            curr_node.parent.right = curr_node.right;
                        fullBalance(curr_node);
                        count--;
                        return;
                    }
                    else if (curr_node.left != null && curr_node.right == null)
                    {
                        if (isLeftChild)
                            curr_node.parent.left = curr_node.left;
                        else
                            curr_node.parent.right = curr_node.left;
                        fullBalance(curr_node);
                        count--;
                        return;
                    }
                    else if (curr_node.left != null && curr_node.right != null)
                    {
                        AVLNode temp = curr_node.right;
                        while (temp.left != null)
                        {
                            temp = temp.left;
                        }
                        curr_node.data = temp.data;
                        if (temp.right != null)
                            if (Object.ReferenceEquals(temp, temp.parent.left))
                                temp.parent.left = temp.right;
                            else
                                temp.parent.right = temp.right;
                        else
                            if (Object.ReferenceEquals(temp, temp.parent.left))
                            temp.parent.left = null;
                        else
                            temp.parent.right = null;
                        fullBalance(curr_node);
                        count--;
                        return;
                    }
                }
                else if (curr_node == null)
                {
                    return;
                }
                else if (item < curr_node.data)
                {
                    curr_node = curr_node.left;
                }
                else if (item > curr_node.data)
                    curr_node = curr_node.right;
            }
        }

        private int height(AVLNode elem)
        {
            if (elem != null)
                return elem.height;
            else
                return 0;
        }

        private int bfactor(AVLNode elem)
        {
            return height(elem.right) - height(elem.left);
        }

        private void fixheight(AVLNode elem)
        {
            int hl = height(elem.left);
            int hr = height(elem.right);
            elem.height = (hl > hr ? hl : hr) + 1;
        }

        private AVLNode balance(AVLNode elem)
        {
            fixheight(elem);
            if (bfactor(elem) == 2)
            {
                if (bfactor(elem.right) < 0)
                    elem.right = rotateRight(elem.right);
                return rotateLeft(elem);
            }
            if (bfactor(elem) == -2)
            {
                if (bfactor(elem.left) > 0)
                    elem.left = rotateLeft(elem.left);
                return rotateRight(elem);
            }
            return elem;
        }

        private void fullBalance(AVLNode elem)
        {
            AVLNode curr_elem = elem;
            while (true)
            {
                if (curr_elem == curr_elem.parent)
                {
                    node = balance(curr_elem);
                    break;
                }
                if (isLeftChild(curr_elem))
                    curr_elem.parent.left = balance(curr_elem);
                else
                    curr_elem.parent.right = balance(curr_elem);
                curr_elem = curr_elem.parent;
            }
        }

        public AVLNode rotateRight(AVLNode elem)
        {
            AVLNode second = elem.left;
            elem.left = second.right;
            if (second.right != null)
                second.right.parent = elem;
            second.right = elem;
            if (elem.parent != elem)
                second.parent = elem.parent;
            else
                second.parent = second;
            elem.parent = second;
            fixheight(elem);
            fixheight(second);
            return second;
        }
        public AVLNode rotateLeft(AVLNode elem)
        {
            AVLNode second = elem.right;
            elem.right = second.left;
            if (second.left != null)
                second.left.parent = elem;
            second.left = elem;
            if (elem.parent != elem)
                second.parent = elem.parent;
            else
                second.parent = second;
            elem.parent = second;
            fixheight(elem);
            fixheight(second);
            return second;
        }
    }
}