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

Введение

В предыдущей статье «От базового до среднего уровня: очереди, списки и деревья (VII)» мы объяснили один из многих возможных способов удаления узла из дерева. Эту операцию необходимо хорошо понимать, чтобы работать с деревьями, предназначенными для различных целей. Как мы уже упоминали в предыдущей статье, существуют и другие способы удаления. Однако, на мой взгляд, показанный там вариант — один из самых простых среди тех, которые не используют рекурсию. При удалении узлов следует избегать рекурсии, потому что, если потребуется удалить несколько узлов, расположенных глубоко в дереве, придётся накапливать в стеке множество вызовов, а затем разворачивать стек обратно. Такой рекурсивный обход требует значительных вычислительных затрат и увеличивает время, необходимое для выполнения операций построения и поддержки дерева.

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

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

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

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

Однако эта идея вновь возвращает нас к спискам: нужно определить, какой элемент займёт центральную позицию и послужит исходной точкой для поиска. Кажется, это просто, не правда ли, мой дорогой читатель? Если список содержит, например, 100 элементов, нам следует использовать элемент, расположенный на 50-й позиции, поскольку он делит список пополам.

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

Рисунок 01

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

"Хорошо, думаю, я понял идею. Однако у меня есть один вопрос. Если мы выполняем вставку данных в дерево, разве нельзя указать, в каком узле должны храниться каждые из них? Это позволило бы избежать дисбаланса или, по крайней мере, уменьшить проблему".

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

В реальном дереве хранящиеся данные НЕ БУДУТ ДИСКРЕТНЫМИ ЗНАЧЕНИЯМИ; это будут записи или иные структуры данных.

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

Предположим следующий сценарий: у вас есть набор записей в базе данных SQL, каждая из которых содержит идентификатор (ID) и некоторые связанные данные. Вы решаете использовать идентификатор для поиска. Если база данных содержит 1 000 000 записей, в худшем случае вам придётся просмотреть их все, чтобы найти нужную запись. Однако, если использовать идеально сбалансированное дерево в качестве индекса поиска, вам придётся пройти максимум через 20 узлов. "Что? Как такое возможно? Что это за безумный расчёт, который позволяет найти запись среди 1 000 000, пройдя максимум всего 20 узлов? Ну же, объясните мне этот трюк, потому что я тоже хочу понять, как это сделать".

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

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

Рисунок 02

В этом уравнении n обозначает рассматриваемый уровень. Например, уровень 1 содержит только корневой узел, тогда как уровень 5 может содержать максимум 16 узлов. И так далее. В общем случае выражение, показанное на рисунке 02, можно переформулировать и получить следующее выражение.

Рисунок 03

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

Рисунок 04

Как видно, количество узлов, которые нужно пройти во время поиска, значительно уменьшается. Однако у этого есть своя цена: на каждом уровне нужно определить, к какому дочернему узлу следует перейти. Вернёмся к самому простому случаю, когда каждый узел имеет не более двух дочерних узлов. При максимуме в 20 уровней мы могли бы хранить упомянутые 1 000 000 записей, по одной на узел. Однако количество используемых уровней всегда будет меньше значения n, используемого в выражении. Причина очень проста: узлы каждого уровня добавляются к общему числу узлов предыдущих уровней. То есть на практике нам понадобится 19 уровней, чтобы разместить эти 1 000 000 узлов, при условии, что дерево хорошо сбалансировано. Те, кто разбирается в химии, наверняка уже поняли идею: каждый электронный слой может содержать только определённое количество электронов. А чтобы понять, на каком слое образовалась связь, вам нужно правильно распределить электроны.

"Что ж, думаю, теперь я понял, почему для поиска нужных данных нам приходится проходить так мало узлов. Я всегда задавался вопросом, зачем кому-то тратить столько времени на реализацию дерева, если, в конце концов, всё это казалось мне полной ерундой. Однако, увидев эти цифры, теперь я понимаю, в чём причина".

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

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

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

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

Код 01

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

Рисунок 05

Теперь, опираясь на знания, изложенные в предыдущей статье, вы сможете изучить структуру, представленную на рисунке 05, и представить себе, как устроено дерево. Чрезвычайно важно, чтобы вы могли это сделать. В противном случае то, что мы увидим и реализуем далее, не будет иметь никакого смысла. Так или иначе вы можете ясно видеть, что поддеревья корня имеют разную высоту. Вопрос в следующем: какова разница между этими двумя высотами?

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

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

Код 02

При выполнении этого кода 02 вы увидите результат, приведённый ниже.

Рисунок 06

Обратите внимание на значение, выделенное на рисунке 06. Это локальный фактор баланса корня, вычисленный как разность между высотой его правого поддерева и высотой его левого поддерева. Поскольку значение положительное, правое поддерево имеет большую высоту. В данном случае высота правого поддерева на три уровня превышает высоту левого. Выделенное значение как раз и указывает на локальный фактор баланса корня; само по себе оно не описывает глобальное состояние дерева. "Как я могу быть уверен, что вы меня не обманываете?" Итак, уважаемый читатель, в предыдущей статье я объяснил, как восстановить структуру дерева по результатам, показанным на рисунках 05 и 06. Сделайте это, и вы поймёте, как фрагмент кода смог вычислить локальный фактор баланса корня. Только тогда код 02 станет для вас понятным. Поскольку я хочу, чтобы вы изучали статьи, я не буду показывать структуру дерева, которую можно восстановить по этим двум результатам.

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

                   .
                   .
                   .
044. //+----------------+
045.         int countLayers(C_TreeNode *ptr, const bool branchR)
046.         {
047.             int count = 0;
048. 
049.             while ((branchR ? (*ptr).GetRight() : (*ptr).GetLeft()) != NULL)
050.             {
051.                 ptr = (branchR ? (*ptr).GetRight() : (*ptr).GetLeft());
052.                 count++;
053.                 if (((branchR?(*ptr).GetRight():(*ptr).GetLeft())==NULL)&&((branchR?(*ptr).GetLeft():(*ptr).GetRight())!= NULL)) while((branchR?(*ptr).GetLeft():(*ptr).GetRight())!= NULL)
054.                 {
055.                     ptr = (branchR ? (*ptr).GetLeft() : (*ptr).GetRight());
056.                     count++;
057.                 }
058.             }
059. 
060.             return count;
061.         }
062. //+----------------+
                   .
                   .
                   .
116. //+----------------+
117.         void CheckBalance(void)
118.         {
119.             Print("Balance: ", countLayers(root, true) - countLayers(root, false));
120.         }
121. //+----------------+
                   .
                   .
                   .

Фрагмент кода 01

Поскольку остальная часть кода остаётся без изменений, я не вижу причин постоянно её повторять. Если показывать только изменённые части, нам будет проще сосредоточиться на самом главном. Итак, мы уже вычисляем локальный фактор баланса корня. Теперь возникает вопрос: чем нам поможет этот фактор баланса? То, что мы сделали до сих пор, — лишь часть необходимого расчёта. Сравнение высот левого и правого поддеревьев позволяет выявить локальный дисбаланс корня; чтобы определить глобальное состояние дерева, нужно выполнить тот же расчёт для остальных узлов. Вопрос в следующем: как мы можем скорректировать те локальные факторы баланса, которые выходят за пределы допустимого диапазона? Существует несколько возможных методов, каждый из которых имеет свои преимущества и недостатки. Здесь мы будем использовать вращения.

Балансировка с помощью вращений относительно проста. Когда локальный фактор баланса узла выходит за пределы допустимого интервала, к поддереву, корнем которого является этот узел, применяется левое или правое вращение. В результате вращения связи «родитель — дочерний узел» в затронутом поддереве перераспределяются с целью восстановления его локальной балансировки, при этом критерий упорядочения не изменяется: после реорганизации меньшие ключи по-прежнему располагаются слева, а большие — справа. Сама по себе эта локальная корректировка не означает, что всё дерево восстановило глобальную балансировку.

Чтобы вам, дорогой читатель, было понятнее, посмотрите на следующий рисунок.

Рисунок 07

Главное, что вам нужно понять, дорогой читатель, — это то, что вращение изменяет связи «родитель — дочерний узел», но сохраняет последовательность ключей, полученную при симметричном обходе. В приведённом примере узлы со значениями 35 и 47 больше не сохраняют то же иерархическое отношение, но при обходе 35 по-прежнему предшествует 47. При применении вращения к узлу, локальный фактор баланса которого выходит за пределы допустимого интервала, корень поддерева может измениться, а локальные факторы затронутых узлов корректируются. Затем необходимо обновить факторы баланса их предков. Дерево в целом оказывается сбалансированным только тогда, когда локальный фактор баланса всех его узлов остаётся в пределах допустимого интервала.

"Подождите минутку. Прежде чем реализовывать код вращения, меня беспокоит стоимость вычисления локальных факторов баланса. Предположим, что у нас есть идеально сбалансированное дерево высотой около 30 уровней. И речь идёт о дереве, которое я считаю относительно неглубоким. Если каждый раз при вставке новых данных нам приходится проходить всё дерево, чтобы пересчитать высоты и проверить, не выходит ли локальный фактор баланса какого-либо узла за пределы допустимого интервала, то такая проверка после каждой вставки в итоге окажется довольно медленной. Чтобы вычислить фактор узла, нам пришлось бы выполнить функцию, приведённую во фрагменте кода 01, для обоих его поддеревьев. Повторять эти обходы после каждой вставки было бы неэффективно. Итак, мой друг-автор, даже если код станет немного сложнее, разве не найдётся более эффективный способ обновлять высоту каждого узла и на её основе вычислять его фактор баланса? Разве каждый узел не мог бы хранить высоту собственного поддерева?"

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

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. template <typename T>
05. class C_TreeNode
06. {
07.     private :
08. //+----------------+
09.         T           info;
10.         C_TreeNode  *left,
11.                     *right;
12.         int         prof;
13. //+----------------+
14.     public  :
15. //+----------------+
16.         C_TreeNode(T arg)
17.             :left(NULL),
18.             right(NULL),
19.             info(arg),
20.             prof(1)
21.         {}
22. //+----------------+
23.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
24. //+----------------+
25.         void SetRight(C_TreeNode *ptr) { right = ptr; }
26. //+----------------+
27.         void SetProf(const int arg) { prof = arg; }
28. //+----------------+
29.         int GetProf(void) { return prof; }
30. //+----------------+
31.         T GetInfo(void) const { return info; }
32. //+----------------+
33.         C_TreeNode *GetLeft(void) const { return left; }
34. //+----------------+
35.         C_TreeNode *GetRight(void) const { return right; }
36. //+----------------+
37. };
38. //+------------------------------------------------------------------+
                   .
                   .
                   .

Фрагмент кода 02

Итак, теперь в классе C_TreeNode есть новая переменная. Инструкция в строке 20 инициализирует переменную, хранящую высоту. Однако присвоенное значение имеет одну особенность, которую я объясню позже, поскольку сейчас не имело бы смысла упоминать о последствиях её изменения.

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

                   .
                   .
                   .
50. //+----------------+
51.         int WhatProf(C_TreeNode *ptr)
52.         {
53.             C_TreeNode *p1, *p2;
54. 
55.             p1 = (*ptr).GetLeft();
56.             p2 = (*ptr).GetRight();
57. 
58.             if (p1 && p2)
59.                 return MathMax((*p1).GetProf(), (*p2).GetProf()) + 1;
60.             return  (p1 && (p2 == NULL) ? (*p1).GetProf() : (*p2).GetProf()) + 1;
61.         }
62. //+----------------+
                   .
                   .
                   .

Фрагмент кода 03

Итак, обратите внимание, что функция, приведённая в этом фрагменте кода, вернёт высоту, сохранённую в узле. Мы вернёмся к этому вопросу позже. Следовательно, для вычисления локального фактора баланса нам потребуется реализовать ещё одну функцию. Однако, в отличие от того, что мы делали раньше, теперь мы НЕ БУДЕМ ИСПОЛЬЗОВАТЬ ФАКТОР КОРНЯ КАК ГЛОБАЛЬНЫЙ ПОКАЗАТЕЛЬ ДЕРЕВА, А БУДЕМ ВЫЧИСЛЯТЬ ЛОКАЛЬНЫЙ ФАКТОР ДЛЯ КАЖДОГО УЗЛА. Этот фактор определяется как разность высот левого и правого поддеревьев соответствующего узла. Глобальное состояние структуры не выражается одним-единственным фактором: дерево в целом будет сбалансированным, если локальный фактор баланса всех его узлов остаётся в допустимом диапазоне. Для выполнения этого вычисления мы воспользуемся функцией, приведённой в следующем фрагменте кода.

                   .
                   .
                   .
62. //+----------------+
63.         int BalanceFactor(C_TreeNode *ptr)
64.         {
65.             C_TreeNode *p1, *p2;
66. 
67.             p1 = (*ptr).GetLeft();
68.             p2 = (*ptr).GetRight();
69. 
70.             if (p1 && p2) return ((*p1).GetProf() - (*p2).GetProf());
71.             return (p1 && (p2 == NULL) ? (*p1).GetProf() : -(*p2).GetProf());
72.         }
73. //+----------------+
                   .
                   .
                   .

Фрагмент 04

А теперь внимание, мой дорогой читатель. Функция, показанная во фрагменте 04, вернёт локальный фактор баланса узла. Его знак указывает, какое из поддеревьев имеет большую высоту, а его величина — разницу между этими высотами. С помощью этого фактора мы сможем определить, какое вращение следует применить к поддереву, корнем которого является данный узел. В зависимости от конфигурации его дочерних узлов нам придётся выполнить один из четырёх видов вращения. Ниже приведены фрагменты кода, соответствующие каждому вращению.

                   .
                   .
                   .
073. //+----------------+
074.         C_TreeNode *Rotation_R(C_TreeNode *ptr)
075.         {
076.             C_TreeNode *p1;
077.             
078.             p1 = (*ptr).GetRight();
079.             (*ptr).SetRight((*p1).GetLeft());
080.             (*p1).SetLeft(ptr);
081. 
082.             return p1;
083.         }
084. //+----------------+
085.         C_TreeNode *Rotation_L(C_TreeNode *ptr)
086.         {
087.             C_TreeNode *p1;
088.             
089.             p1 = (*ptr).GetLeft();
090.             (*ptr).SetLeft((*p1).GetRight());
091.             (*p1).SetRight(ptr);
092. 
093.             return p1;
094.         }
095. //+----------------+
096.         C_TreeNode *Rotation_2R(C_TreeNode *ptr)
097.         {
098.             C_TreeNode *p1, *p2;
099. 
100.             p1 = (*ptr).GetRight();
101.             p2 = (*p1).GetLeft();
102.             (*ptr).SetRight((*p2).GetLeft());
103.             (*p1).SetLeft((*p2).GetRight());
104.             (*p2).SetLeft(ptr);
105.             (*p2).SetRight(p1);
106. 
107.             return p2;
108.         }
109. //+----------------+
110.         C_TreeNode *Rotation_2L(C_TreeNode *ptr)
111.         {
112.             C_TreeNode *p1, *p2;
113. 
114.             p1 = (*ptr).GetLeft();
115.             p2 = (*p1).GetRight();
116.             (*ptr).SetLeft((*p2).GetRight());
117.             (*p1).SetRight((*p2).GetLeft());
118.             (*p2).SetRight(ptr);
119.             (*p2).SetLeft(p1);
120. 
121.             return p2;
122.         }
123. //+----------------+
                   .
                   .
                   .

Фрагмент 05

Хорошо, чтобы понять фрагмент 05, мы воспользуемся рисунками, приведёнными ниже.

Рисунок 08

На рисунке 08 показано, как функция, объявление которой начинается в строке 74, переназначает связи «родитель — дочерний узел» внутри поддерева, корнем которого является узел, отмеченный красным цветом.

Рисунок 09

На рисунке 09 показано, как функция, объявление которой начинается в строке 85, переназначает связи «родитель — дочерний узел» внутри затронутого поддерева, не изменяя при этом порядок ключей.

Рисунок 10

На рисунке 10 показана реорганизация связей «родитель — дочерний узел», которую выполняет функция, объявление которой начинается в строке 96.

Рисунок 11

Наконец, на рисунке 11 показано, как функция, объявление которой начинается в строке 110, реорганизует связи «родитель — дочерний узел» поддерева. На всех четырёх изображениях красный кружок обозначает узел, который передаётся в качестве аргумента функциям фрагмента кода 05 и служит корнем поддерева до вращения.

Я знаю, что это похоже на одну из тех инструкций по сборке кубика Рубика. Однако, хотя на первый взгляд это и кажется довольно странным, четыре приведённых выше изображения показывают, как каждое вращение перераспределяет связи «родитель — дочерний узел» в затронутом поддереве, чтобы привести локальный фактор баланса в допустимый диапазон, не изменяя при этом порядок ключей. И есть ещё одна деталь: алгоритм будет стремиться удерживать локальный фактор баланса каждого узла в пределах этого интервала. Только когда это условие выполняется для всех узлов, можно утверждать, что дерево в целом сбалансировано. Это довольно удивительно, учитывая простоту этих вращений.

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

                   .
                   .
                   .
123. //+----------------+
124.         C_TreeNode *Insert(C_TreeNode *ptr, T info)
125.         {
126.             if (ptr == NULL)
127.                 return new C_TreeNode(info);
128. 
129.             if (info < (*ptr).GetInfo()) (*ptr).SetLeft(Insert((*ptr).GetLeft(), info));
130.             else (*ptr).SetRight(Insert((*ptr).GetRight(), info));
131. 
132.             (*ptr).SetProf(WhatProf(ptr));
133.             if ((BalanceFactor(ptr) == 2) && (BalanceFactor((*ptr).GetLeft()) == 1)) ptr = Rotation_L(ptr);
134.             else if ((BalanceFactor(ptr) == -2) && (BalanceFactor((*ptr).GetRight()) == -1)) ptr = Rotation_R(ptr);
135.             else if ((BalanceFactor(ptr) == -2) && (BalanceFactor((*ptr).GetRight()) == 1)) ptr = Rotation_2R(ptr);
136.             else if ((BalanceFactor(ptr) == 2) && (BalanceFactor((*ptr).GetLeft()) == -1)) ptr = Rotation_2L(ptr);
137. 
138.             return ptr;
139.         }
140. //+----------------+
                   .
                   .
                   .
177. //+----------------+
178.         void Store(T info)
179.         {
180.             root = Insert(root, info);
181.         }
182. //+----------------+
                   .
                   .
                   .
211. //+------------------------------------------------------------------+
212. void OnStart(void)
213. {
214.     C_Tree <int> Tree;
215. 
216.     Tree.Store(10);
217.     Tree.Store(-6);
218.     Tree.Store(47);
219.     Tree.Store(35);
220.     Tree.Store(51);
221.     Tree.Store(90);
222.     Tree.Store(85);
223.     Tree.Store(40);
224. 
225.     Print(Tree.In_Order());
226.     Print(Tree.Pre_Order());
227.     Print(Tree.Post_Order());
228. }
229. //+------------------------------------------------------------------+

Фрагмент кода 06

Теперь обратите внимание на изменения, внесённые во фрагмент кода, отвечающий за вставку новых данных в дерево. Имейте в виду, что по мере построения дерева его корень может измениться. По этой причине мы изменили инструкцию в строке 180, отвечающую за обновление ссылки на корень. Я хочу, чтобы вы особенно обратили внимание на инструкции в строках 132–136: они обновляют высоту узла, вычисляют его локальный фактор баланса и определяют, нужно ли выполнять вращение поддерева. Эти операции повторяются у предков вставленного узла, так что локальные корректировки в конечном итоге восстанавливают глобальную балансировку дерева. Поразительно, что обновление высоты, вычисление локального фактора балансировки и выбор вращения требуют так мало инструкций. Поэтому я не буду подробно объяснять каждую из них; я лишь хочу, чтобы вы обратили внимание на то, как они применяются к предкам вставленного узла. И нет, не я разработал этот алгоритм. Используемая здесь стратегия соответствует AVL-алгоритму балансировки, названному так в честь исследователей и математиков Адельсона-Вельского и Лэндиса, которые опубликовали эту концепцию в 1962 году. Представленная здесь реализация на чистом MQL5 формирует AVL-дерево.

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

Рисунок 12

А теперь обратите внимание на следующий момент, потому что именно здесь начинается самая удивительная часть алгоритма. Если вы измените на ноль значение, которым инструкция в строке 20 фрагмента кода 02 инициализирует свойство высоты, вместо того чтобы присваивать ему единицу, структура дерева, показанная на рисунке 12, будет другой. Таким образом, внеся только это изменение в код, приведённый в приложении, мы получим новую структуру, показанную ниже.

Рисунок 13

Это действительно удивительно. И именно поэтому я решил представить этот алгоритм в статье.

Итак, теперь, когда вы уже знаете, как изменяется дерево по мере вставки новых данных, почему бы нам не рассмотреть один из вариантов реализации удаления узлов? Моё предложение показано в следующем фрагменте кода.

142. //+----------------+
143.         C_TreeNode *Erase(C_TreeNode *ptr, T info)
144.         {
145.             C_TreeNode *tmp;
146.             int         i;
147. 
148.             if (((*ptr).GetLeft() == NULL) && ((*ptr).GetRight() == NULL))
149.             {
150.                 delete ptr;
151.                 return NULL;
152.             }
153.             if ((*ptr).GetInfo() < info) (*ptr).SetRight(Erase((*ptr).GetRight(), info)); else
154.             if ((*ptr).GetInfo() > info) (*ptr).SetLeft(Erase((*ptr).GetLeft(), info)); else
155.             {
156.                 if ((*ptr).GetLeft() != NULL)
157.                 {
158.                     tmp = (*ptr).GetLeft();
159.                     while ((*tmp).GetRight() != NULL) tmp = (*tmp).GetRight();
160.                     (*ptr).SetInfo((*tmp).GetInfo());
161.                     (*ptr).SetLeft(Erase((*ptr).GetLeft(), (*tmp).GetInfo()));
162.                 }else
163.                 {
164.                     tmp = (*ptr).GetRight();
165.                     while ((*tmp).GetLeft() != NULL) tmp = (*tmp).GetLeft();
166.                     (*ptr).SetInfo((*tmp).GetInfo());
167.                     (*ptr).SetRight(Erase((*ptr).GetRight(), (*tmp).GetInfo()));
168.                 }
169.             }
170.             i = BalanceFactor(ptr);
171.             if (i > 1) ptr = (BalanceFactor((*ptr).GetLeft()) >= 0 ? Rotation_L(ptr) : Rotation_2L(ptr)); 
172.             else if (i < -1) ptr = (BalanceFactor((*ptr).GetRight()) <= 0 ? Rotation_R(ptr) : Rotation_2R(ptr)); 
173. 
174.             return ptr;
175.         }
176. //+----------------+
                   .
                   .
                   .
242. //+----------------+
243.         void DeleteNode(const T info)
244.         {
245.             root = Erase(root, info);
246.         }
247. //+----------------+
                   .
                   .
                   .
252. //+------------------------------------------------------------------+
253. void OnStart(void)
254. {
255.     C_Tree <int> Tree;
256. 
257.     Tree.Store(10);
258.     Tree.Store(-6);
259.     Tree.Store(47);
260.     Tree.Store(35);
261.     Tree.Store(51);
262.     Tree.Store(90);
263.     Tree.Store(85);
264.     Tree.Store(40);
265. 
266.     Print(Tree.In_Order());
267.     Print(Tree.Pre_Order());
268.     Print(Tree.Post_Order());
269. 
270.     Tree.DeleteNode(10);
271.     Tree.DeleteNode(-6);
272.     Print("-----------");
273.     Print(Tree.In_Order());
274.     Print(Tree.Pre_Order());
275.     Print(Tree.Post_Order());
276. }
277. //+------------------------------------------------------------------+

Фрагмент кода 07

Конечно, некоторые инструкции в других частях кода тоже были изменены, чтобы избежать сбоя при попытке удалить узел. Однако, поскольку это лишь незначительные изменения, а полный код для изучения его работы вы найдёте в приложенном файле, я не считаю нужным их показывать или объяснять. Тем не менее, обратите внимание, что инструкции в строках 270 и 271 полностью удаляют левое поддерево корня. Однако если бы мы не применили новые вращения, на этой стороне не осталось бы ни одного узла. Однако последующие вращения после удаления перераспределят связи «родитель — дочерний узел» в затронутых поддеревьях и вновь вернут локальные факторы баланса изменённых узлов и их предков в допустимый диапазон. Когда эти обновления завершатся, дерево восстановит глобальную сбалансированность и примет конфигурацию, показанную на следующем рисунке.

Рисунок 14

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

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

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

Кроме того, нам ещё предстоит рассмотреть другие аспекты реализации деревьев. Это понадобится, когда мы будем изучать операции поиска в дереве.

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