Удаление из AVL-дерева

namespace AVL_Tree
{
    /// <summary>
    /// Узел дерева.
    /// </summary>
    /// <typeparam name="T">Тип элемента.</typeparam>
    public class TreeNode<T>
    {
        /// <summary>
        /// Значение.
        /// </summary>
        public T value;
 
        /// <summary>
        /// Левый потомок.
        /// </summary>
        public TreeNode<T> left;
 
        /// <summary>
        /// Правый потомок.
        /// </summary>
        public TreeNode<T> right;
 
        /// <summary>
        /// Родитель.
        /// </summary>
        public TreeNode<T> parent;
 
        /// <summary>
        /// Показатель баланса.
        /// </summary>
        public int balance;
 
        public TreeNode(T value = default(T), TreeNode<T> left = null, TreeNode<T> right = null, TreeNode<T> parent = null)
        {
            this.value = value;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
 
        public override string ToString() => value.ToString();
    }
}

using System;
using System.Collections.Generic;
 
namespace AVL_Tree
{
    class AVLTree<T>
    {
        private TreeNode<T> root;
 
        private void ThrowIfEmpty()
        {
            if (Count == 0)
                throw new InvalidOperationException("Недопустимо малое количество элементов для произведения требуемой операции.");
        }
 
        private TreeNode<T> Find(TreeNode<T> root, T x)
        {
            if (root == null)
                return null;
 
            if (Comparer.Compare(root.value, x) > 0)
                return Find(root.left, x);
            else if (Comparer.Compare(root.value, x) < 0)
                return Find(root.right, x);
 
            return root;
        }
 
        private TreeNode<T> Insert(ref TreeNode<T> root, TreeNode<T> parent, T x)
        {
            if (root == null)
            {
                root = new TreeNode<T>(value: x, parent: parent);
                return root;
            }
            else
            {
                if (Comparer.Compare(root.value, x) > 0)
                    return Insert(ref root.left, root, x);
                else if (Comparer.Compare(root.value, x) < 0)
                    return Insert(ref root.right, root, x);
                else
                    throw new ArgumentException($"Узел со значением {x} уже включён в бинарное дерево поиска.");
            }
        }
 
        private void TryChangeRoot(TreeNode<T> pivot)
        {
            if (pivot == root)
                root = pivot.parent;
        }
 
        private void RotateRight(TreeNode<T> pivot)
        {
            TreeNode<T> left = pivot.left;
            pivot.left = left.right;
            if (left.right != null)
                left.right.parent = pivot;
 
            TreeNode<T> parent = pivot.parent;
            left.right = pivot;
            pivot.parent = left;
 
            left.parent = parent;
            if (parent != null)
                if (parent.right == left.right)
                    parent.right = left;
                else
                    parent.left = left;
 
            TryChangeRoot(pivot);
 
            left.right.balance = Math.Max(left.balance, 0) + 1;
            left.balance = Math.Min(0, left.right.balance) - 1;
        }
 
        private void RotateLeft(TreeNode<T> pivot)
        {
            TreeNode<T> right = pivot.right;
            pivot.right = right.left;
            if (right.left != null)
                right.left.parent = pivot;
 
            TreeNode<T> parent = pivot.parent;
            right.left = pivot;
            pivot.parent = right;
 
            right.parent = parent;
            if (parent != null)
                if (parent.left == right.left)
                    parent.left = right;
                else
                    parent.right = right;
 
            TryChangeRoot(pivot);
 
            right.left.balance = Math.Min(0, right.balance) - 1;
            right.balance = Math.Max(right.left.balance, 0) + 1;
        }
 
        private void RotateLeftRight(TreeNode<T> pivot)
        {
            RotateLeft(pivot.left);
            RotateRight(pivot);
        }
 
        private void RotateRightLeft(TreeNode<T> pivot)
        {
            RotateRight(pivot.right);
            RotateLeft(pivot);
        }
 
        private void InsertAndRebalance(T x)
        {
            TreeNode<T> current = Insert(ref root, null, x);
 
            while (current.parent != null)
            {
                if (current == current.parent.left)
                    current.parent.balance++;
                else
                    current.parent.balance--;
 
                if (current.parent.balance == 2)
                {
                    if (current.balance == -1)
                    {
                        RotateLeftRight(current.parent);
                        current = current.parent;
                    }
                    else if (current.balance == 1)
                        RotateRight(current.parent);
                    break;
                }
                else if (current.parent.balance == -2)
                {
                    if (current.balance == 1)
                    {
                        RotateRightLeft(current.parent);
                        current = current.parent;
                    }
                    else if (current.balance == -1)
                        RotateLeft(current.parent);
                    break;
                }
                else
                    current = current.parent;
            }
            Count++;
        }
 
        private T RemoveMin(ref TreeNode<T> root)
        {
            if (root.left != null)
                return RemoveMin(ref root.left);
            else
            {
                T result = root.value;
                root = root.right;
                return result;
            }
        }
 
        private void Remove(ref TreeNode<T> root, in T x)
        {
            if (root == null)
                throw new ArgumentException($"Узел со значением {x} не найден.");
 
            if (Comparer.Compare(root.value, x) == 0)
            {
                if ((root.left == null) && (root.right == null))
                    root = null;
                else if (root.left == null)
                    root = root.right;
                else if (root.right == null)
                    root = root.left;
                else
                    root.value = RemoveMin(ref root.right);
                Count--;
            }
            else if (Comparer.Compare(root.value, x) > 0)
                Remove(ref root.left, in x);
            else
                Remove(ref root.right, in x);
        }
 
        private void RemoveAndRebalance(in T x) // x - удаляемое значение
        {
 
        }
 
        private IEnumerable<T> ByAscending(TreeNode<T> root)
        {
            if (root != null)
            {
                foreach (var item in ByAscending(root.left))
                    yield return item;
 
                yield return root.value;
 
                foreach (var item in ByAscending(root.right))
                    yield return item;
            }
        }
 
        private IEnumerable<T> ByDescending(TreeNode<T> root)
        {
            if (root != null)
            {
                foreach (var item in ByDescending(root.right))
                    yield return item;
 
                yield return root.value;
 
                foreach (var item in ByDescending(root.left))
                    yield return item;
            }
        }
 
 
        /// <summary>
        /// Количество элементов.
        /// </summary>
        public int Count { get; private set; }
 
        /// <summary>
        /// Корень.
        /// </summary>
        public TreeNode<T> Root => root;
 
        /// <summary>
        /// Компаратор, используемый при сравнении элементов.
        /// </summary>
        public IComparer<T> Comparer { get; private set; }
 
        public AVLTree(IComparer<T> comparer) => Comparer = comparer;
 
        public AVLTree() : this(Comparer<T>.Default)
        {
        }
 
        /// <summary>
        /// Выполняет поиск элемента со значением x.
        /// </summary>
        /// <param name="x">Искомое значение.</param>
        /// <returns>Узел с искомым значением.</returns>
        public TreeNode<T> Find(T x) => Find(root, x);
 
        /// <summary>
        /// Вставляет элемент со значением x.
        /// </summary>
        /// <param name="x">Вставляемое значение.</param>
        public void Insert(T x) => InsertAndRebalance(x);
 
        /// <summary>
        /// Возвращает последовательность элементов дерева по возрастанию.
        /// </summary>
        /// <returns>Последовательность элементов.</returns>
        public IEnumerable<T> ByAscending() => ByAscending(root);
 
        /// <summary>
        /// Возвращает последовательность элементов дерева по убыванию.
        /// </summary>
        /// <returns>Последовательность элементов.</returns>
        public IEnumerable<T> ByDescending() => ByDescending(root);
    }
}