От начального до среднего уровня: Очереди, списки и деревья (VII)

Введение

В предыдущей статье «От начального до среднего уровня: очереди, списки и деревья (VI)» мы показали, как реализовать базовый механизм построения дерева. В конце той статьи мы адаптировали код так, чтобы он использовал шаблон, и тем самым немного обобщили разработанный механизм.

Хотя, вероятно, многие не используют деревья активно, понимание механизмов, лежащих в основе реализации этой структуры данных, позволит вам лучше использовать возможности MQL5. Помните, что здесь главная цель — учебная. Поэтому каждый принятый принцип должен адаптироваться под ваши задачи и особенности конкретной ситуации. Хотя в теории всё, что здесь реализовано и показано, может показаться применимым к любой ситуации, не исключено, что для вашей конкретной цели это будет не самым подходящим решением. В таком случае правильное понимание понятий, представленных и объяснённых в статьях, поможет вам найти наилучшее решение для вашей ситуации.

Хорошо, исходя из этого принципа, мы должны понять, как выполнять другой тип операций в дереве. Хотя вы, вероятно, не будете часто использовать эту реализацию, понимание того, как она работает, может помочь вам решать и другие типы задач. В этой статье мы сначала сосредоточимся на удалении узлов из двоичного дерева.

Если вы считаете, что это простая задача, то вы правы. Однако, если вы не понимаете определённых понятий, эта задача, которая, на мой взгляд, относительно проста и легка в реализации, может превратиться в настоящую головную боль, мой дорогой читатель. Особенно если вы только начинаете знакомиться с программированием. Без лишних предисловий перейдём к основной теме этой статьи.

Очереди, списки и деревья (VII)

Когда речь заходит об удалении узлов из связанной структуры, многие сталкиваются с определёнными трудностями. Однако, в отличие от очередей и списков, где удалить узел относительно просто, в случае дерева дело обстоит иначе. Поэтому точное понимание того, что происходит при удалении узла из дерева, может помочь вам понять и другие аспекты, которые мы рассмотрим позже. Это связано с тем, что при удалении узла из дерева возникает довольно любопытная ситуация: мы временно создаём второе дерево.

Чтобы вы могли понять, как удаляется узел из дерева и что происходит с его структурой, сначала нужно разобраться в самой структуре дерева по выводу, который функции обхода генерируют в терминале. Я знаю, что поначалу это может показаться довольно странным, и в первых примерах деревьев, которые вы будете моделировать, это будет трудно представить, поэтому мы разберём всё вместе и не спеша. Прежде всего нам нужно проанализировать код, представленный в предыдущей статье, хотя и с небольшим изменением. Ниже приведён полный код:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         void Seq(C_TreeNode *ptr, const E_SEQ type)
064.         {
065.             if (ptr == NULL) return;
066. 
067.             switch (type)
068.             {
069.                 case eInOrder   :
070.                 case ePostOrder :
071.                 case eDestroy   :
072.                     Seq((*ptr).GetLeft(), type);
073.                     if (type == eInOrder) break;
074.                     Seq((*ptr).GetRight(), type);
075.             }
076.             m_szInfo += def_InfoToString(ptr);
077.             switch (type)
078.             {
079.                 case ePreOrder  :
080.                     Seq((*ptr).GetLeft(), type);
081.                 case eInOrder   :
082.                     Seq((*ptr).GetRight(), type);
083.                     break;
084.                 case eDestroy   :
085.                     delete ptr;
086.             }
087.         }
088. //+----------------+
089.     public  :
090. //+----------------+
091.         C_Tree()
092.             :root(NULL)
093.         {}
094. //+----------------+
095.         ~C_Tree()
096.         {
097.             Seq(root, eDestroy);
098.         }
099. //+----------------+
100.         void Store(T info)
101.         {
102.             if (root == NULL) root = Insert(root, root, info);
103.             else Insert(root, root, info);
104.         }
105. //+----------------+
106.         string In_Order(void)
107.         {
108.             m_szInfo = "In Order: ";
109.             Seq(root, eInOrder);
110.             
111.             return m_szInfo;
112.         }
113. //+----------------+
114.         string Pre_Order(void)
115.         {
116.             m_szInfo = "Pre Order: ";
117.             Seq(root, ePreOrder);
118. 
119.             return m_szInfo;
120.         }
121. //+----------------+
122.         string Post_Order(void)
123.         {
124.             m_szInfo = "Post Order: ";
125.             Seq(root, ePostOrder);
126. 
127.             return m_szInfo;
128.         }
129. //+----------------+
130.     #undef def_InfoToString
131. //+----------------+
132. };
133. #undef C_TreeNode
134. //+------------------------------------------------------------------+
135. void OnStart(void)
136. {
137.     C_Tree <int> Tree;
138. 
139.     Tree.Store(10);
140.     Tree.Store(-6);
141.     Tree.Store(47);
142.     Tree.Store(35);
143.     Tree.Store(85);
144.     Tree.Store(40);
145. 
146.     Print(Tree.In_Order());
147.     Print(Tree.Pre_Order());
148.     Print(Tree.Post_Order());
149. }
150. //+------------------------------------------------------------------+

Код 01

Хотя здесь приведён полный код, на самом деле нас интересует, какую структуру создают инструкции между строками 139 и 144. И хотя вызовы функций обхода между строками 146 и 148 генерируют вывод в линейном формате, мне нужно, чтобы вы, мой дорогой и уважаемый читатель, приложили немного усилий и интерпретировали его по-другому. Этот вывод должен помочь вам мысленно представить структуру, которую создаёт код. В некоторых случаях мы можем получить структуру, похожую на связанный список. Однако из-за порядка, в котором были добавлены значения, мы создадим не линейную структуру, а древовидную. Именно это я и хочу, чтобы вы попытались мысленно представить, потому что, если у вас это не получится, вы не сможете понять, как удалить узел из дерева, не разрушив само дерево.

При выполнении этого кода 01 вы увидите в терминале вывод, показанный на следующем рисунке:

Рисунок 01

А теперь, дорогой читатель, мне нужно, чтобы вы сосредоточились на этом рисунке 01 и одновременно мысленно восстановили, как функции Pre_Order и Post_Order сгенерировали вывод, показанный на рисунке 01. Почему вы не упоминаете вывод, сгенерированный функцией In_Order? Причина проста, мой дорогой читатель. Функция In_Order всегда генерирует вывод, похожий на вывод упорядоченного связанного списка. Поскольку этот вывод не слишком нам помогает, по крайней мере в данном случае, мы можем его проигнорировать.

Хорошо, давайте сначала сосредоточимся на выводе, который генерирует функция Post_Order. Эта функция сначала показывает листовые узлы, а уже потом — внутренние узлы дерева. Помните следующее: ВЫ НЕ ЗНАЕТЕ, сколько листовых узлов существует в дереве. Вы знаете только то, что каждый узел может указывать максимум на два дочерних узла. Таким образом, мы с полной уверенностью знаем, что первые два узла, появляющиеся в выводе, являются листовыми узлами, независимо от какой-либо другой информации, поскольку сам класс C_TreeNode задаёт два возможных указателя.

Теперь нам нужно посмотреть на вывод, который генерирует функция Pre_Order. В данном случае функция начинает обход с корневого узла и сначала движется влево, пока не найдёт листовой узел. Затем она возвращается к предыдущему узлу и продолжает движение по правой ветви. Исходя из этого, мы уже можем утверждать, что корневой узел содержит значение 10, а значение -6 хранится в листовом узле, расположенном слева от корневого узла. Это позволяет нам представить изображение, показанное ниже:

Рисунок 02

Хорошо, теперь у нас есть частичное представление дерева, которое мы можем мысленно визуализировать. Теперь мне нужно, чтобы вы продолжили это небольшое усилие. Если вы внимательно посмотрите на рисунок 02, то заметите следующее: два известных и видимых на нём значения являются частью полной ветви дерева. То, чего не хватает, можно и нужно интерпретировать как новое дерево. Если вам удастся это понять, вы увидите, что, согласно выводу, сгенерированному функцией Pre_Order, следующим посещаемым узлом будет корень этого нового дерева, которое мы себе представляем. Я знаю, что это может показаться странным, но вам следует постараться представить структуру в нелинейной форме.

Хорошо, если на рисунке 02 изображена левая ветвь, корневой узел содержит значение 10, а инструкция в строке 54 определяет, как будут связаны узлы, то можно утверждать, что следующий рисунок представляет следующий шаг в мысленном построении дерева, созданного кодом 01.

Рисунок 03

Хорошо, похоже, это имеет смысл. Однако нам ещё нужно заполнить остальные узлы на рисунке 03. Для этого мы снова воспользуемся выводом, который генерирует функция Post_Order. Обратите внимание. Первое значение, которое появляется в выводе, это -6, а второе значение 40. Почему? Потому что узел, в котором хранится значение 40, является листовым узлом. Подождите: если это листовой узел, он может занимать любую из пустых позиций на Рисунке 03, верно? Да, мой дорогой читатель. Однако вам следует изучить код функции Post_Order. Сделав это, вы поймёте, что Post_Order опускается на максимально возможную глубину, прежде чем начать возвращаться назад, и всегда сначала проходит левую ветвь, а затем правую. Очень важно, чтобы вы хорошо поняли этот момент, потому что, если изменить порядок, функция выдаст другой результат. Исходя из этого, мы можем с полной уверенностью утверждать, что на следующем рисунке показано место, которое должен занимать узел со значением 40.

Рисунок 04

Хорошо, теперь нам осталось разместить два узла на своих правильных местах. Чтобы определить, где должны располагаться узлы, хранящие эти значения, можно немного подумать или обратиться к самому рисунку 01. В обоих случаях в итоге мы получим то, что показано ниже, тем самым завершив представление нашего дерева.

Рисунок 05

Отлично. Если вы поняли, как был получен этот рисунок 05, значит, мы можем продолжить. Однако, прежде чем это сделать, я хочу показать вам одну небольшую деталь. Предположим, что обход дерева реализован в другом порядке, как показано в следующем фрагменте:

                   .
                   .
                   .
062. //+----------------+
063.         void Seq(C_TreeNode *ptr, const E_SEQ type)
064.         {
065.             if (ptr == NULL) return;
066. 
067.             switch (type)
068.             {
069.                 case ePostOrder :
070.                 case eDestroy   :
071.                     Seq((*ptr).GetRight(), type);
072.                 case eInOrder   :
073.                     Seq((*ptr).GetLeft(), type);
074.             }
075.             m_szInfo += def_InfoToString(ptr);
076.             switch (type)
077.             {
078.                 case eInOrder   :
079.                 case ePreOrder  :
080.                     Seq((*ptr).GetRight(), type);
081.                     if (type == eInOrder) break;
082.                     Seq((*ptr).GetLeft(), type);
083.                     break;
084.                 case eDestroy   :
085.                     delete ptr;
086.             }
087.         }
088. //+----------------+
                   .
                   .
                   .

Фрагмент 01

В этом случае код сгенерирует вывод, показанный на следующем рисунке:

Рисунок 06

Обратите внимание, что в данном случае простое изменение кода 01 в соответствии с предложенным во фрагменте 01 привело к тому, что результат обхода оказался таким, как показано на рисунке 06. Обратите также внимание на то, что разница между фрагментом 01 и кодом 01 очень тонкая. Она могла бы остаться незамеченной, если бы здесь, в статье, её не показали. Теперь вы уже знаете, мой дорогой читатель: всякий раз, когда вы анализируете вывод такого типа, старайтесь также изучать исходный код, чтобы получить более полное представление о ситуации.

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

Рисунок 07

Ого, это действительно довольно тревожно, потому что у нас есть корневой узел со значением 10, отключённое поддерево, корневой узел которого имеет значение 35, и изолированный узел со значением 85. Именно такой станет структура, мой дорогой читатель, если мы без всякой осторожности и без какого-либо критерия удалим узел, значение которого равно 47.

Хорошо, как мы найдём в дереве узел, который хранит значение 47? Вы ещё не объяснили, как это делается. Хм, и правда. Я ещё не объяснил, как найти узел по содержащемуся в нём значению. Это была моя оплошность. Простите меня, мой дорогой читатель. Прежде чем приступить к удалению, давайте посмотрим, как найти конкретный узел по хранящемуся в нём значению. Поиск очень прост: нам нужно лишь добавить немного кода в метод Seq, определение которого начинается в строке 63. Для этого мы воспользуемся полным кодом, приведённым ниже:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy, eSearch};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         C_TreeNode *Seq(C_TreeNode *ptr, const E_SEQ type, const T info = 0)
064.         {
065.             if (ptr == NULL) return NULL;
066. 
067.             switch (type)
068.             {
069.                 case eSearch    :
070.                     while ((ptr != NULL) && ((*ptr).GetInfo() != info))
071.                         ptr = (info < (*ptr).GetInfo() ? (*ptr).GetLeft() : (*ptr).GetRight());
072.                     return ptr;
073.                 case eInOrder   :
074.                 case ePostOrder :
075.                 case eDestroy   :
076.                     Seq((*ptr).GetLeft(), type);
077.                     if (type == eInOrder) break;
078.                     Seq((*ptr).GetRight(), type);
079.             }
080.             m_szInfo += def_InfoToString(ptr);
081.             switch (type)
082.             {
083.                 case ePreOrder  :
084.                     Seq((*ptr).GetLeft(), type);
085.                 case eInOrder   :
086.                     Seq((*ptr).GetRight(), type);
087.                     break;
088.                 case eDestroy   :
089.                     delete ptr;
090.             }
091. 
092.             return NULL;
093.         }
094. //+----------------+
095.     public  :
096. //+----------------+
097.         C_Tree()
098.             :root(NULL)
099.         {}
100. //+----------------+
101.         ~C_Tree()
102.         {
103.             Seq(root, eDestroy);
104.         }
105. //+----------------+
106.         void Store(T info)
107.         {
108.             if (root == NULL) root = Insert(root, root, info);
109.             else Insert(root, root, info);
110.         }
111. //+----------------+
112.         string In_Order(void)
113.         {
114.             m_szInfo = "In Order: ";
115.             Seq(root, eInOrder);
116.             
117.             return m_szInfo;
118.         }
119. //+----------------+
120.         string Pre_Order(void)
121.         {
122.             m_szInfo = "Pre Order: ";
123.             Seq(root, ePreOrder);
124. 
125.             return m_szInfo;
126.         }
127. //+----------------+
128.         string Post_Order(void)
129.         {
130.             m_szInfo = "Post Order: ";
131.             Seq(root, ePostOrder);
132. 
133.             return m_szInfo;
134.         }
135. //+----------------+
136.         void Address(const T info)
137.         {
138.             Print(info, " information address is: ", Seq(root, eSearch, info));
139.         }
140. //+----------------+
141.     #undef def_InfoToString
142. //+----------------+
143. };
144. #undef C_TreeNode
145. //+------------------------------------------------------------------+
146. void OnStart(void)
147. {
148.     C_Tree <int> Tree;
149. 
150.     Tree.Store(10);
151.     Tree.Store(-6);
152.     Tree.Store(47);
153.     Tree.Store(35);
154.     Tree.Store(85);
155.     Tree.Store(40);
156. 
157.     Print(Tree.In_Order());
158.     Print(Tree.Pre_Order());
159.     Print(Tree.Post_Order());
160.     Tree.Address(47);
161. }
162. //+------------------------------------------------------------------+

Код 02

Обратите внимание, что код 02 почти не отличается от кода 01. По сути, объявление в строке 40 вводит новое перечисление, а метод Seq, определение которого начинается в строке 63, перестаёт быть методом без возвращаемого значения и начинает возвращать адрес найденного узла.

В этом методе есть один момент, который важно понять, мой дорогой читатель: условное выражение, проверяемое циклом while, расположенное в строке 70. Многие люди, особенно те, кто только начинает, не до конца понимают, как работает компилятор. Возможно, в будущем я объясню это подробно. Я всё ещё об этом думаю. Возможно, многим было бы интересно узнать об этом, хотя я пока не знаю, стоит ли вообще поднимать эту тему. Если вам это интересно, напишите об этом в комментариях к статье. Если заинтересованных будет достаточно, я постараюсь объяснить это как можно подробнее. И сделаю это с практическим подходом, используя исключительно MQL5.

Ещё один момент, о котором стоит упомянуть: условное выражение в строке 71 повторяет ту же логику, что используется при вставке узлов в дерево. Обратите внимание, что здесь значения сравниваются по тому же критерию, что и в операторе вставки, приведённом в строке 59. Важно понимать это, потому что мы должны следовать одному и тому же критерию обхода, чтобы не потеряться в дереве.

Продолжим, потому что я хочу объяснить одну деталь условного выражения, проверяемого циклом while и расположенного в строке 70. Сам цикл нас не интересует; важно условие, выраженное в этой проверке.

Будьте очень внимательны, потому что то, что я вам сейчас покажу, может свести с ума любого программиста, хотя некоторых — сильнее, чем других. Обратите внимание на следующее: когда в строке 160 будет выполнен вызов Address, будет вызван этот метод, определение которого начинается в строке 136. В свою очередь, Address вызовет метод Seq, определение которого начинается в строке 63, чтобы получить адрес узла, хранящего значение, переданное в качестве аргумента. Пока всё хорошо. Действительно, при выполнении этого кода вы увидите результат, показанный ниже:

Рисунок 08

А теперь начинается самое интересное. Откройте редактор и в коде 02, приведённом в приложении, замените значение, используемое в качестве критерия поиска, на другое, которое не хранится ни в одном узле дерева. Например, используйте 50 в качестве искомого значения. Результат будет таким, как показано ниже:

Рисунок 09

Пока всё верно. Здесь нет никакой проблемы. Теперь замените условие в строке 70:

while (((*ptr).GetInfo() != info) && (ptr != NULL))

Снова скомпилируйте код 02, изменив только условие в строке 70. При попытке выполнить его вы увидите вывод, показанный на следующем рисунке:

Рисунок 10

Что произошло? Ну, в этом нет никакого смысла. Вы, должно быть, шутите, потому что я никогда не видел ничего подобного. Условие в строке 70 практически не изменилось, и всё же код дал сбой? Вот это безумие. Что ж, мой дорогой читатель, даже если вам кажется, что это условие не изменилось, на самом деле это не так. Это связано с некоторыми особенностями процесса компиляции. Объяснить это теоретически довольно сложно, но, если посмотреть на практике, как работает компилятор, всё становится понятным. Поэтому, если вы хотите разобраться в этом подробнее, не забудьте написать в комментариях к этой статье: «Я хочу понять, как работает компилятор». Так я пойму, стоит ли написать несколько статей, чтобы подробно это объяснить.

Вернёмся к нашему вопросу. Благодаря методу Address, определение которого начинается в строке 136, у нас уже есть механизм для поиска узла по хранящемуся в нём значению. Пришло время реализовать код, который будет удалять узел из дерева.

Для этого нам придётся реализовать механизм удаления, который поначалу может показаться несколько запутанным. Однако, если вы поняли начало этой статьи, то прекрасно поймёте, что мы собираемся делать. Поскольку я не хочу сразу усложнять механизм удаления, а удаление узлов из дерева отличается от удаления узлов из списка, начнём с самого простого случая. Затем мы сможем рассмотреть несколько более сложный и, следовательно, более общий случай. Самый простой случай — удалить лист из дерева. Что значит, что узел является листом? Вы объяснили, что такое узел, ветвь и корень.

Однако вы ничего не сказали о листьях. Что ж, на мой взгляд, понятие «лист» должно быть довольно интуитивным. В любом случае давайте уточним, что это значит. Лист — это листовой узел, то есть узел, от которого не отходит ни одной ветви. По сути, это точка, где заканчивается ветвь, по которой мы движемся. Чтобы стало ещё понятнее, на Рисунке 05 показаны три листа: узлы со значениями -6, 40 и 85. Думаю, теперь вы уже понимаете, что такое лист.

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

"Как это так? Я не понял, что вы имеете в виду". Спокойно, дорогой читатель, скоро вы всё поймёте. Сначала реализуем код, который позволит удалять листья дерева. Ниже приведён полный пример кода:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy, eSearch};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         C_TreeNode *Seq(C_TreeNode *ptr, const E_SEQ type, const T info = 0)
064.         {
065.             if (ptr == NULL) return NULL;
066. 
067.             switch (type)
068.             {
069.                 case eSearch    :
070.                     while ((ptr != NULL) && ((*ptr).GetInfo() != info))
071.                         ptr = (info < (*ptr).GetInfo() ? (*ptr).GetLeft() : (*ptr).GetRight());
072.                     return ptr;
073.                 case eInOrder   :
074.                 case ePostOrder :
075.                 case eDestroy   :
076.                     Seq((*ptr).GetLeft(), type);
077.                     if (type == eInOrder) break;
078.                     Seq((*ptr).GetRight(), type);
079.             }
080.             m_szInfo += def_InfoToString(ptr);
081.             switch (type)
082.             {
083.                 case ePreOrder  :
084.                     Seq((*ptr).GetLeft(), type);
085.                 case eInOrder   :
086.                     Seq((*ptr).GetRight(), type);
087.                     break;
088.                 case eDestroy   :
089.                     delete ptr;
090.             }
091. 
092.             return NULL;
093.         }
094. //+----------------+
095.     public  :
096. //+----------------+
097.         C_Tree()
098.             :root(NULL)
099.         {}
100. //+----------------+
101.         ~C_Tree()
102.         {
103.             Seq(root, eDestroy);
104.         }
105. //+----------------+
106.         void Store(T info)
107.         {
108.             if (root == NULL) root = Insert(root, root, info);
109.             else Insert(root, root, info);
110.         }
111. //+----------------+
112.         string In_Order(void)
113.         {
114.             m_szInfo = "In Order: ";
115.             Seq(root, eInOrder);
116.             
117.             return m_szInfo;
118.         }
119. //+----------------+
120.         string Pre_Order(void)
121.         {
122.             m_szInfo = "Pre Order: ";
123.             Seq(root, ePreOrder);
124. 
125.             return m_szInfo;
126.         }
127. //+----------------+
128.         string Post_Order(void)
129.         {
130.             m_szInfo = "Post Order: ";
131.             Seq(root, ePostOrder);
132. 
133.             return m_szInfo;
134.         }
135. //+----------------+
136.         void DeleteNode(const T info)
137.         {
138.             C_TreeNode *tmp, *ptr = root;
139. 
140.             for (tmp = NULL; (ptr != NULL) && ((*ptr).GetInfo() != info); tmp = ptr, ptr = (info < (*ptr).GetInfo() ? (*ptr).GetLeft() : (*ptr).GetRight()));
141. 
142.             if (ptr != NULL)
143.             {
144.                 if ((*ptr).GetLeft() == (*ptr).GetRight())
145.                 {
146.                     if (info < (*tmp).GetInfo()) (*tmp).SetLeft(NULL);
147.                     else (*tmp).SetRight(NULL);
148.                     delete ptr;
149.                 }
150.             }
151.         }
152. //+----------------+
153.     #undef def_InfoToString
154. //+----------------+
155. };
156. #undef C_TreeNode
157. //+------------------------------------------------------------------+
158. void OnStart(void)
159. {
160.     C_Tree <int> Tree;
161. 
162.     Tree.Store(10);
163.     Tree.Store(-6);
164.     Tree.Store(47);
165.     Tree.Store(35);
166.     Tree.Store(85);
167.     Tree.Store(40);
168. 
169.     Print(Tree.In_Order());
170.     Print(Tree.Pre_Order());
171.     Print(Tree.Post_Order());
172. 
173.     Tree.DeleteNode(85);
174.     Print("----------------");
175. 
176.     Print(Tree.In_Order());
177.     Print(Tree.Pre_Order());
178.     Print(Tree.Post_Order());
179. }
180. //+------------------------------------------------------------------+

Код 03

Узлы можно удалять разными способами — как с помощью рекурсии, так и с помощью итеративных подходов. В данном случае мы будем использовать итеративный подход. Причина в том, что такой подход немного быстрее, прежде всего потому, что удаление узлов может очень быстро нарушить баланс дерева. Возникающая вслед за этим деградация структуры снижает эффективность рекурсивных обходов, используемых для удаления узлов. Давайте посмотрим, что мы делаем в Коде 03.

Когда будет выполнен вызов DeleteNode, содержащийся в строке 173, будет вызван метод DeleteNode, определение которого начинается в строке 136. Внутри этого метода цикл поиска будет обходить дерево, пока не найдёт узел, значение которого совпадает с полученным аргументом. Почему мы не используем поиск, выполняемый методом Seq? Потому что Seq возвращает адрес найденного узла, но не сохраняет ссылку на его родительский узел. Для DeleteNode нужны обе ссылки, чтобы обновить в родительском узле указатель, указывающий на узел, который будет удалён.

Обратите внимание на следующее, мой дорогой читатель. Цикл, определение которого начинается в строке 140, будет сравнивать значение, хранящееся в каждом узле, с искомым значением, пока не найдёт узел, который мы хотим удалить. На каждой итерации присваивание переменной tmp будет сохранять ссылку на узел, посещённый на предыдущей итерации; по завершении поиска это будет родительский узел найденного узла. Когда поиск завершится, условие, расположенное в строке 144, проверит, является ли найденный узел листом. В этом случае присваивание в строке 146 изменит левый или правый указатель родительского узла так, чтобы он больше не указывал на удаляемый лист. Наконец, оператор delete, содержащийся в строке 148, освободит память, занятую этим листом.

Таким образом, при выполнении этого кода 03 мы получим показанный ниже результат:

Рисунок 11

А теперь обратите внимание на одну деталь на этом рисунке 11, а именно на ту часть, которую я выделил. Если вы внимательно посмотрите, то заметите, что узел, хранивший значение, переданное в качестве аргумента при вызове в строке 173, отсутствует в этой выделенной области. Это подтверждает, что присваивание разорвало связь между родительским узлом и удалённым листом, а инструкция delete освободила память, занятую этим листом. Важно, чтобы вы это заметили, потому что с помощью той же техники, показанной в коде 03, мы сможем удалить почти все узлы дерева, лист за листом. И я говорю «почти», потому что при удалении корневого узла возникает проблема. Если вы попытаетесь удалить его с помощью этого кода 03, даже если это единственный узел в дереве, код неизбежно завершится с ошибкой. Это связано с тем, что присваивание в строке 146 пытается обратиться к предполагаемому родительскому узлу корня через недействительную ссылку. Чтобы решить эту проблему, нам нужно добавить условие, которое предотвратит такой доступ.

Итак, теперь, когда вы поняли логику кода удаления и то, что нам нужно сохранять ссылку на родительский узел удаляемого узла, мы можем реорганизовать код так, чтобы он стал более понятным и полезным как с практической, так и с учебной точки зрения. Так что не пугайтесь того, что мы увидим дальше, мой дорогой читатель. Я просто не хочу разбирать код блок за блоком, потому что тогда объяснение станет довольно утомительным.

После внесения всех необходимых изменений мы получаем приведённый ниже код, который станет нашим новым кодом для построения деревьев:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         C_TreeNode *EraseAndMerge(C_TreeNode *ptr)
064.         {
065.             C_TreeNode *tmp = ptr;
066. 
067.             if ((*tmp).GetRight() == NULL) ptr = (*ptr).GetLeft();
068.             else if ((*tmp).GetLeft() == NULL) ptr = (*ptr).GetRight();
069.             else
070.             {
071.                 tmp = (*ptr).GetLeft();
072.                 while ((*tmp).GetRight() != NULL) tmp = (*tmp).GetRight();
073.                 (*tmp).SetRight((*ptr).GetRight());
074.                 tmp = ptr;
075.                 ptr = (*ptr).GetLeft();
076.             }
077.             delete tmp;
078. 
079.             return ptr;
080.         }
081. //+----------------+
082.         void Seq(C_TreeNode *ptr, const E_SEQ type)
083.         {
084.             if (ptr == NULL) return;
085. 
086.             switch (type)
087.             {
088.                 case eInOrder   :
089.                 case ePostOrder :
090.                 case eDestroy   :
091.                     Seq((*ptr).GetLeft(), type);
092.                     if (type == eInOrder) break;
093.                     Seq((*ptr).GetRight(), type);
094.             }
095.             m_szInfo += def_InfoToString(ptr);
096.             switch (type)
097.             {
098.                 case ePreOrder  :
099.                     Seq((*ptr).GetLeft(), type);
100.                 case eInOrder   :
101.                     Seq((*ptr).GetRight(), type);
102.                     break;
103.                 case eDestroy   :
104.                     delete ptr;
105.             }
106.         }
107. //+----------------+
108.     public  :
109. //+----------------+
110.         C_Tree()
111.             :root(NULL)
112.         {}
113. //+----------------+
114.         ~C_Tree()
115.         {
116.             Seq(root, eDestroy);
117.         }
118. //+----------------+
119.         void Store(T info)
120.         {
121.             if (root == NULL) root = Insert(root, root, info);
122.             else Insert(root, root, info);
123.         }
124. //+----------------+
125.         string In_Order(void)
126.         {
127.             m_szInfo = "In Order: ";
128.             Seq(root, eInOrder);
129.             
130.             return m_szInfo;
131.         }
132. //+----------------+
133.         string Pre_Order(void)
134.         {
135.             m_szInfo = "Pre Order: ";
136.             Seq(root, ePreOrder);
137. 
138.             return m_szInfo;
139.         }
140. //+----------------+
141.         string Post_Order(void)
142.         {
143.             m_szInfo = "Post Order: ";
144.             Seq(root, ePostOrder);
145. 
146.             return m_szInfo;
147.         }
148. //+----------------+
149.         void DeleteNode(const T info)
150.         {
151.             C_TreeNode *tmp, *ptr = root;
152. 
153.             for (tmp = NULL; (ptr != NULL) && ((*ptr).GetInfo() != info); tmp = ptr, ptr = (info < (*ptr).GetInfo() ? (*ptr).GetLeft() : (*ptr).GetRight()));
154. 
155.             if (ptr != NULL)
156.             {
157.                 if (ptr == root) root = EraseAndMerge(ptr); else
158.                 {
159.                     if ((*tmp).GetLeft() == ptr) (*tmp).SetLeft(EraseAndMerge(ptr));
160.                     else (*tmp).SetRight(EraseAndMerge(ptr));
161.                 }
162.             }
163.         }
164. //+----------------+
165.     #undef def_InfoToString
166. //+----------------+
167. };
168. #undef C_TreeNode
169. //+------------------------------------------------------------------+
170. void OnStart(void)
171. {
172.     C_Tree <int> Tree;
173. 
174.     Tree.Store(10);
175.     Tree.Store(-6);
176.     Tree.Store(47);
177.     Tree.Store(35);
178.     Tree.Store(85);
179.     Tree.Store(40);
180. 
181.     Print(Tree.In_Order());
182.     Print(Tree.Pre_Order());
183.     Print(Tree.Post_Order());
184. 
185.     Tree.DeleteNode(10);
186.     Print("----------------");
187. 
188.     Print(Tree.In_Order());
189.     Print(Tree.Pre_Order());
190.     Print(Tree.Post_Order());
191. }
192. //+------------------------------------------------------------------+

Код 04

Обратите внимание, что в этом коде 04, приведённом в приложении, я удалил часть, связанную с поиском в дереве. Это связано с тем, что мы подробнее рассмотрим этот вопрос в другой раз. Однако вы, возможно, заметили, что я добавил в класс C_Tree новый метод, определение которого начинается в строке 63. А теперь будьте внимательны, мой дорогой читатель. Новый метод будет отвечать за отсоединение узла, выбранного для удаления, и переподключение поддеревьев, которые зависели от этого узла. В этом методе применяется практически та же логика, что и в приведённом выше фрагменте кода, использовавшемся для удаления листа. Тем не менее, здесь я сразу покажу все шаги, так как объяснять их поэтапно было бы слишком утомительно и тяжело.

Операция заключается в отсоединении узла, выбранного для удаления, а затем в повторном подключении поддеревьев, которые зависели от выбранного узла. Неважно, какой узел мы собираемся удалить: последовательность действий всегда будет одной и той же. Сначала мы изолируем выбранный узел. Затем мы обновляем необходимые указатели, чтобы связать между собой оставшиеся поддеревья и занять освободившееся место в структуре. Наконец, мы освобождаем память, занятую удалённым узлом.

Итак, именно в этом и заключается главный момент: метод реструктуризации не выполняется самостоятельно. Метод, определяющий узел, который необходимо удалить, вызывает метод реструктуризации. Итак, перейдём к методу удаления, определение которого начинается со строки 149. Обратите внимание, что метод удаления в целом сохраняет ту же логику; мы изменили лишь некоторые детали. Обратите внимание, что теперь условие в строке 157 будет проверять, является ли выбранный для удаления узел корнем дерева. В этом случае метод реструктуризации отсоединит текущий корень, заново свяжет его поддеревья и установит в качестве нового корня узел, выбранный алгоритмом.

Если выбранный для удаления узел не является корнем, мы проверим, указывает ли левый или правый указатель родительского узла на выбранный узел. Далее мы обновим соответствующий указатель так, чтобы он указывал на узел, который займёт структурное место удалённого узла. В некотором смысле это очень похоже на то, что мы делали при реализации удаления узлов из связанных списков. Как видите, это очень просто и довольно практично. Как я уже говорил в начале статьи, сам код удаления довольно прост. Однако понять логику его работы не так просто. Поэтому нам пришлось пройти через все эти шаги, прежде чем дойти до этого кода 04.

Итак, какой результат даёт этот код 04? Вы можете увидеть его ниже:

Рисунок 12

А теперь будьте очень внимательны и, если возникнут сомнения, вернитесь к началу статьи, чтобы понять то, что я собираюсь объяснить. У этого дерева, которое вы можете увидеть на рисунке 12, нет ни одной ветви слева. Это связано с тем, что теперь оно полностью несбалансированно, а это снижает производительность поиска в дереве. Однако вы можете ясно видеть, что узел, который был исходным корнем, заменён единственным узлом, образовывавшим левую ветвь исходного корня. Поскольку замещающий узел занял место корня, а в исходной левой ветви не было других узлов, у нового корня нет левой ветви.

Заключительные замечания

В этой статье мы достаточно наглядно показали и объяснили, как удалить узел из дерева. Этот процесс, как правило, скорее сбивает новичков с толку, чем помогает им понять, как он выполняется и почему его нужно выполнять именно так.

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

Запомните, дорогой читатель: такие операции, как удаление и вставка узлов в дерево, могут привести к его разбалансировке. Бывают ситуации, когда это целесообразно. Однако во многих других случаях несбалансированное дерево снижает эффективность поиска в этой структуре. По этой причине я удалил часть кода, отвечающую за поиск в дереве. В следующей статье мы более подробно остановимся на этой теме. Тогда вы сможете решить, какой тип решения наиболее подходит в каждом конкретном случае.

Файл MQ5	Описание
Код 01	Простое дерево
Код 02	Простое дерево
Код 03	Простое дерево