Как мне выполнить возврат для разбивки веревки в C#?

Question

Я пытаюсь реализовать структуру данных веревки на С #. По сути, это двоичное дерево узлов, предназначенное для представления строки, и каждый узел хранит длину подстроки, которую он представляет. У меня есть код, написанный для создания веревки из заданной строки, и я дошел до того, что нашел символ по строковому индексу с помощью метода разделения. Проблема, однако, заключается в обходе дерева назад , чтобы выполнить разделение, удалив все правые ссылки на поддеревья, покрывающие символы, прошедшие позицию. i.

На данный момент я могу придумать два способа реализовать это. Первым и наиболее очевидным, что я придумал, было создание свойства родительского узла. Однако я не знаю, как реализовать это с помощью метода поддержки рекурсивной сборки, вызываемого конструктором, без его значительного переписывания. Тем не менее, рекурсия - это самый простой способ построить дерево. Другой метод, который я думал, - это хранить ссылки на каждый узел в массиве на пути вниз по дереву, а затем просто манипулировать ссылками в массиве, но я застреваю в отслеживании и повторном подключении осиротевших узлов и зная, где снова подключить их систематически.

Если у кого-то есть опыт реализации веревок на C#, мне бы очень хотелось узнать ваши мысли о том, как подойти к расколу.

      public class Rope {
        // Generic Node Class
        public class Node
        {
            public string S { get; set; }   // The string stored at the given node.
            public int Length { get; set; } // Length of the string represented by a given node.
            public Node Left { get; set; }  // Left and Right children.
            public Node Right { get; set; }

            public Node(string s, Node L, Node R)
            {
                S = s;
                Left = L;
                Right = R;
                Length = s.Length;
            }
        }
        // Rope from String Constructor
        public Rope(string s)
        {
            root = Build(s);
        }

        // Build
        // Creates a rope to represent a given string. Returns the node at which the rope is rooted.
        private Node Build(string s)
        {
            if (s.Length <= 4) // If the string is four chars or less, store it at current node.
            {
                return new Node
                {
                    Length = s.Length,
                    S = s,
                };
            }

            int mid = s.Length / 2; // Store position of the middle of the string.
            return new Node
            {
                Length = s.Length, // Node length equals the length of the string it represents.
                Left = Build(s.Substring(0, mid)), // Left built from beginning to middle of string.
                Right = Build(s.Substring(mid)) // Right built from middle to end of string.
            };
        }
        // Split
        // Splits one rope into two ropes R1 and R2.
        // Time Complexity: Probably on the internet, somewhere.
        public void Split(int i, Rope R1, Rope R2)
        {
            Node curr = root;
            List<Node> path = new List<Node>();
            while (curr.Left != null && curr.Right != null)
            {
                if (i <= curr.Left.Length) { curr = curr.Left; }
                else
                {
                    i -= curr.Left.Length; // Update i to the difference
                    curr = curr.Right; // Look right
                }
                path.Add(curr); // Record node in path
            }
            if (curr.S[i] != curr.S.Max()) // If a split occurs within a node, crack the node
            {
                Node N1 = new Node(curr.S.Substring(0, i));
                Node N2 = new Node(curr.S.Substring(i));
                curr.Left = N1;
                curr.Right = N2;
            }
            for (int j = 0; j < path.Count; ++j) // Go back through the path and 'cut the children'.
            {
                curr = path.Last();
                curr.Length -= curr.Right.Length;
                curr.Right = null;
                path.RemoveAt(path.Count - 1);
            }
            R2.root = root.Right;
            root.Right = null;
            root.Length = root.Left.Length;
            R1.root = root;
        }
}