Двоичные деревья: бесконечность под рукой

Binary Trees: Infinity in the Palm of Your Hand

В этой главе мы узнаем In this chapter, you will learn:

• Как создавать двоичные деревья, добавлять, удалять и искать значения в них. • How to create and manipulate binary trees by inserting, removing, and searching for values.

• Как поддерживать в дереве свойства, двоичного дерева поиска: • How to manage a binary search tree that enforces the global property that:

  • Чтобы в каждом узле значения из левого поддерева не превосходили значения самого узла. — Values in the left subtree of a node are all smaller than or equal to that node’s value.

  • Чтобы в каждом узле значения из правого поддерева были не меньше значения самого узла. — Values in the right subtree of a node are all larger than or equal to that node’s value.

• Как сложность добавления, удаления и поиска в сбалансированном дереве (O(Log N)) может при неосторожной потере баланса доходить до неприемлемого порога в O(N). • That search, insert, and remove operations can be O(log N) in balanced binary trees but can degrade to become an unacceptable O(N) if you aren’t careful. • How to rebalance a binary search tree after insert and remove operations to guar‐ antee O(log N) performance for search, insert, and remove.

• Как поэлементно проходить двоичные деревья в восходящем порядке, затратив на это O(N) действий. • How to traverse a binary search tree to process each value in ascending order in O(N) performance.

• Как из двоичного дерева смоделировать хеш-таблицу, которую можно проходить поэлементно в порядке возрастания ключей. • How to use a binary tree structure to implement a symbol table data type with the added benefit that its keys can be retrieved in sorted order.

• Как из двоичного дерева смоделировать приоритетную очередь, которую можно проходить поэлементно в порядке удаления согласно приоритету, не меняя при этом структуру очереди. • How to use a binary tree structure to implement a priority queue with the added benefit that you can generate the (key, value) entries in priority order without disrupting the priority queue.

Введение

Getting Started

Информация в связных списках хранится последовательно — в виде цепочки. В этой главе мы познакомимся с новой структурой данных — двоичным деревом. Идея двоичного дерева чрезвычайно важно для программирования и теории алгоритмов. В пятой главе мы изучили рекурсию — с точки зрения Python так называется ситуация, когда функция вызывает сама себя. Теперь же мы рассмотрим двоичное дерево как рекурсивную структуру данных — потому что двоичное дерево состоит из двоичных деревьев! Для начала убедимся в том, что уже известный нам связный список тоже может быть смоделирован как рекурсивная структура. Linked lists and arrays store information in a linear arrangement. In this chapter, I introduce the binary tree recursive data structure, one of the most important concepts in the field of computer science. In Chapter 5, you learned about the concept of recur‐ sion, where a function calls itself. In this chapter, you will learn that the binary tree is a recursive data structure—that is, it refers to other binary tree structures. To intro‐ duce the concept of a recursive data structure, let’s revisit the linked list data structure you have already seen.

В самом деле, каждый узел связного списка — это value, полезная нагрузка, и next — ссылка на первый узел хвостовой части списка, которая сама по себе — тоже список. Список, в отличие от статического массива, можно оперативно увеличивать и сокращать, то есть менять N, количество элементов в нём. В примере 6-1 представлена рекурсивная функция sum_list(), которая вычисляет сумму всего его элементов. Сравним её с обычным суммированием в цикле, sum_iterative(). A linked list is an example of a recursive data structure because each node has a next reference to the first node of a sublist. Linked lists improve upon fixed-length arrays by supporting dynamic growth and reduction of a collection of N values. The sum_list() recursive function, shown in Listing 6-1, processes a linked list to return its sum. Compare its implementation against a traditional iterative solution.

   1 class Node:
   2   def __init__(self, val, rest=None):
   3     self.value = val
   4     self.next = rest
   5 
   6 def sum_iterative(n):
   7   total = 0                             # 1
   8   while n:
   9     total += n.value                    # 2
  10     n = n.next                          # 3
  11   return total
  12 
  13 def sum_list(n):
  14   if n is None:                         # 4
  15     return 0
  16   return n.value + sum_list(n.next)     # 5

• Пример 6-1. Рекурсивный и итеративный способ посчитать сумму элементов связного списка Listing 6-1. Recursive and iterative functions to sum the values in a linked list

1. Сумма изначально нулевая. Initialize total to 0 to prepare for computation.

2. Добавим поле n.value каждого узла списка n к сумме. For each node, n, in linked list, add its value to total.

3. Перейдём к следующему узлу связного списка (или к маркеру конца None). Advance to the next node in the linked list.

4. Основание рекурсии: сумма элементов пустого списка нулевая. Base case: the sum of a nonexistent list is 0.

5. Рекурсивный вызов: сумма элементов пустого списка n — это значение n.value его первого узла плюс сумма элементов хвостового списка. Recursive case: the sum of a linked list, n, is the sum of its value added to the sum of the rest of the list.

В цикле while мы сначала полагаем сумму total нулевой, а затем прибавляем к ней значения всех элементов списка. В рекурсивной функции наоборот: нулевое значение суммы пустого списка — это основание рекурсии, то есть то, на чём рекурсивный вызов остановится. Если список n состоит хотя бы из одного узла, происходит рекурсивный вызов, который вычисляет сумму элементов хвостового списка (который начинается с n.next), и к результату прибавляется n.value — это и есть общая сумма. The while loop visits each node in the linked list and accumulates a running total of all values stored by nodes in the list. In contrast, sum_list() is a recursive function with a base case that terminates the recursion and a recursive case that composes results of smaller problem instances together. In the base case, the sum of a nonexis‐ tent list is 0. If a list, n, has at least one node, then the recursive case computes the sum of the rest of the list (that is, the list starting with n.next) and adds that result to n.value to determine the total sum.

Список из N узлов рекурсивно раскладывается на первый узел и хвостовой список из N - 1 узлов. Это разложение по определению рекурсивно: хвостовой список — это тоже список, причём меньшего размера. Но критерию эффективной рекурсии наша функция не соответствует, потому что сводит обработку объёма данных размера N (сумму списка из N элементов) к обработке данных размера N - 1, ибо в хвостовом списке всего на один элемент меньше. Давайте вообразим рекурсивную структуру данных, в которой разделение на подструктуры более эффективно. Например, возьмём арифметическое выражение, состоящее только из двухместных операций умножения, вычитания, сложения и деления. Атомарное арифметическое выражение — это некоторое число, составное — это операция над двумя арифметическими выражениями. Например (для простоты заключим все операции в скобки):

• 3: число — это выражение

• (3 + 2): сложение двух чисел — это выражение

• (((1 + 5) ∗ 9) – (2 ∗ 6)): вычитание двух выражений, (2 ∗ 6) слева из ((1 + 5) ∗ 9) справа, — это выражение (при условии, что уменьшаемое и вычитаемое — это действительно выражения)

A linked list of N nodes is recursively decomposed into a first node, n, and the rest, a sublist containing N – 1 nodes. This is a recursive decomposition—since, by defini‐ tion, the rest is a sublist—but it only subdivides the problem of size N (i.e., find the sum of the values contained in N nodes) into a smaller problem of size N – 1 (i.e., find the sum of the values contained in N – 1 nodes). To envision a recursive data structure that has more productive subdivisions, consider representing basic mathe‐ matical expressions using binary operations, such as multiplication. A valid expres‐ sion is either a value or combines two sub-expressions using a binary operation: • 3 — any numeric value is valid • (3 + 2) — add a left value 3 with a right value 2 • (((1 + 5) ∗ 9) – (2 ∗ 6)) — subtract a right expression (2 ∗ 6) from a left expres‐ sion ((1 + 5) ∗ 9)

Таким образом выражения можно сочетать в любом объёме. На иллюстрации 6-1 представлено арифметическое выражение из семи операций над восемью числами. Такую нелинейную структуру уже нельзя представить в виде списка. Кто когда-нибудь разбирался с генеалогическим семейным древом, легко согласится с тем, что нашу структуру можно назвать деревом разбора. Expressions can combine and grow to be as large as desired—the expression in Figure 6-1 has seven mathematical operations and eight numeric values. Linked lists cannot model this non-linear expression. If you’ve ever tried to visualize genealogies using family trees, then you can see why the diagram is called an expression tree.

Иллюстрация 6-1. Дерево разбора арифметического выражения

Узел с умножением имеет два дочерних узла (с делением и разностью), потомками которых в свою очередь являются четыре «внучатых» узла (один из них — число 4), шесть «правнучатых» и два «праправнучатых» узла. The top multiply node has two child nodes, ultimately leading to four grandchild nodes (one of which is the value 4), six great-grandchild nodes, and two great-great grandchild nodes.

Арифметическое выражение с иллюстрации 6-1 — это произведение двух других арифметических выражений, в чём, собственно, и выражается его рекурсивность. Чтобы его посчитать, надо сначала вычислить — рекурсивно! — левое выражение; получится 1. Затем рекурсивно же вычислить правое; получится 42. Теперь наконец можно и умножить, так что значение всего выражения — 1 · 42 = 42. The expression in Figure 6-1 represents the multiplication of two expressions, which demonstrates its recursive structure. To compute the value of this expression, first recursively compute the left expression to produce the result 1. In similar recursive fashion, the right expression evaluates to 42, so the overall result of the original expression is 1 ∗ 42 = 42.

На иллюстрации 6-1 исходное выражение представлено в виде рекурсивной структуры. На её вершине — квадрат с операцией умножения, от которого идут стрелки к левому и правому подвыражениям. Если на вершине подвыражения находится квадрат, то это снова некоторая операция, а если круг — это основание рекурсии, числовое значение, на котором рекурсивный разбор останавливается. В примере 6-2 мы смоделировали такую схему разделения на левое и правое подвыражение в классе Expression. Figure 6-1 visualizes the recursive substructures of the original expression. At the top is a box representing a multiplication expression, with a left arrow and a right arrow to its left and right sub-expressions. Each circle represents a Value node containing a numeric value, providing the base cases that stop recursion. The Expression data structure in Listing 6-2 models expressions using left and right sub-expressions.

   1 class Value:                            # 1
   2   def __init__(self, e):
   3     self.value = e
   4 
   5   def __str__(self):
   6     return str(self.value)
   7 
   8   def eval(self):
   9     return self.value
  10 
  11 class Expression:                       # 2
  12   def __init__(self, func, left, right):
  13     self.func = func
  14     self.left = left
  15     self.right = right
  16 
  17   def __str__(self):                    # 3
  18     return f"({self.left} {self.func.__doc__} {self.right}")
  19 
  20   def eval(self):                       # 4
  21     return self.func(self.left.eval(), self.right.eval())
  22 
  23 def add(left, right):                   # 5
  24   """+"""
  25   return left + right

• Пример 6-2. Класс Expression, моделирующий арифметическое выражение Listing 6-2. Expression data structure to represent mathematical expressions

• Экземпляр класса Value может хранить любые значения, например, числа. Класс нужен для того, чтобы и у узла-числа, и у узла-операции был метод .eval(). При преобразовании в строку возвращается строковое представление поля .value. A Value stores a numeric value. It can return its value and string representation.

• Экземпляр класса Expression хранит выражение — то есть функцию func и её операнды — левое подвыражение left и правое, right. An Expression stores a function, func, and left and right sub-expressions.

• Строковое представление выражения рекурсивно собирается из трёх строк, заключённых в скобки. Provides built-in str() method to recursively produce strings with paren‐ theses around expressions.

• Чтобы вычислить значение выражения, надо вычислить значение девого и правого его потомков, и обработать результат функцией func. Evaluate an Expression by evaluating left and right children and passing those values to func.

• Пример функции, реализующей сложение. Нам понадобится строковое представление соответствующей арифметической операции. В Python мы можем хранить его в т. н. строке документации, которую потом можно использовать, обратившись к полю .__doc__ объекта-функции. Реализация других арифметических операций, например, mult() для умножения, делается точно так же. Function to perform addition; mult() for multiplication is similar. The doc String doc for the function contains the operator symbol.

Вычисление выражения — рекурсивная операция, которая останавливается, когда дойдёт до объекта типа Value. Разложим рекурсивное вычисление выражения ((1 + 5) * 9) на стадии, как мы это делали в главе 5. Результат разложения приведён на иллюстрации 6-2. Evaluating an Expression is a recursive process that will eventually terminate at Value objects. Using the same technique I introduced in Chapter 5, Figure 6-2 visual‐ izes the recursive evaluation of the expression m = ((1 + 5) ∗ 9):

   1 >>> a = Expression(add, Value(1), Value(5))
   2 >>> m = Expression(mult, a, Value(9))
   3 >>> print(m, '=', m.eval())
   4 ((1 + 5) * 9) = 54
   5 

Чтобы вычислить m, необходимо вызвать два метода .eval(), соответственно, для правого и для левого подвыражений. Каждый из этих вызовов может оказаться рекурсивным. Здесь левое подвыражение, a = (1 + 5), приводит к рекурсии, а правое, 9, — нет. Затем вычисляется и возвращается результат — 54. Становится понятно, чем хорошо рекурсивное представление выражение в виде двоичного дерева Expression, да и сами рекурсивные алгоритмы выглядят коротко и ясно. To evaluate m, there could be up to two recursive calls, one on the left and right sub-expressions, respectively. In this case, the left sub-expression, a = (1 + 5) is evalu‐ ated recursively, while the right sub-expression, 9, is not. The final computation of 54 is returned as the final result. This example demonstrates the usefulness of the Expres sion recursive binary tree data structure. It also shows that recursive implementa‐ tions are brief and elegant.

Очень важно, чтобы данные, которые мы помещаем в рекурсивную структуру, не ломали её. Вот как легко испортить список: It is critical that recursive data structures have no structural defects. For example:

   1 >>> n = Node(3)
   2 >>> n.next = n           # Внимание! Бездонная пропасть!
   3 >>> print(sum_list(n))
   4 RecursionError: maximum recursion depth exceeded
   5 

Вот мы задали связный список из одного узла, n, но вместо добавления элемента положили в поле .next сам этот узел! Функция sum_list() отлично работает на конченых списках, но здесь нарушена сама структура данных — и sum_list(n) никогда не доберётся до основания рекурсии. Та же история и с Expression . Нарушение структуры данных — это ошибка алгоритма, найти которую помогает аккуратное тестирование. This linked list is defined by a node, n, whose next node in the linked list is itself! There is nothing wrong with the sum_list() function—the linked list has a struc‐ tural defect and so the base case for sum_list(n) never occurs. A similar situation could occur in an Expression. These defects are programming mistakes and you can avoid them by carefully testing your code.

Иллюстрация 6-2. Пошаговый проход рекурсивного вычисления выражения ((1 + 5) ∗ 9)

Двоичные деревья поиска

Binary Search Trees

Двоичное дерево — прародитель всех рекурсивных структур данных. Двоичное дерево поиска хранит произвольные значения (если их можно сравнивать), предоставляя прежде всего эффективную операцию поиска, а также вставки и удаления. Binary trees are the godfather of all recursive data structures. A binary search tree can store collections of values with efficient search, insert, and remove operations.

Если хранить данные в упорядоченном массиве, к ним применим двоичный поиск, вычислительная сложность которого O(log N). Есть ещё немало выгод в том, чтобы хранить данные упорядоченно: например, человеку тоже будет проще искать нужное. Технически может возникнуть трудность с созданием очень большого массива, потому что он должен занимать один непрерывный фрагмент памяти, и неизвестно, может ли это обеспечить операционная система. Но главная неприятность — это произвольная вставка и удаление элемента, причём даже для такого динамического массива, как list в Python: Storing values in a sorted array is necessary for Binary Array Search to provide O(log N) performance. There are countless other reasons to produce information in sorted order to make it easier for users to view information. From a practical stand‐ point, very large fixed arrays are challenging because they require contiguous mem‐ ory that must be allocated by the underlying operating system. In addition, changing the size of the array is problematic:

• Если операция снятия с конца list или добавления в конец не приводит к масштабированию, требуется только одно действие.

• Если вставка или удаление происходят не в конце массива, действий требуется больше. При удалении элемента нужно сдвинуть все элементы справа от него на одну позицию влево. При добавлении — сначала сдвинуть вправо все элементы, начиная с нужной позиции, а затем записать туда добавляемый. В обоих случаях может потребоваться масштабирование. • To remove a value from the array, all values to the right of the removed value must shift one index location to the left. The code must remember that there are “unused” index locations at the end of the array.

• Если масштабирование всё-таки понадобилось, то нужно сначала выделить память под массив большего размера, скопировать туда старый массив (останется место для добавления новых значений), а затем освободить память, занимаемую старым массивом. • To add a new value to an array, a new and larger array is created, and values from the old array are copied into the new array—while making room for the new value. Finally, memory for the old array is released.

В программе на Python все эти действия проделываются с динамическим массивом типа list без участия программиста. Но вычислительная сложность наихудшего случая, и что ещё более важно, средняя сложность вставки в начало или удаления из произвольного места неизбежно оказываются O(N). Второй и третий столбец таблицы 6-1 показывает время тысячи операций вставки одного значения в динамический массив и тысячи операций добавления одного значения в его конец. Python programs avoid these difficulties because the built-in list structure can already grow and shrink without programmer effort, but in the worst case, inserting a value into a Python list remains O(N). Table 6-1 measures the runtime performance both when prepending 1,000 values (one at a time) to the front of a list of size N, and when appending 1,000 values (one at a time) to the end of a list of size N.

• Таблица 6-1. Сравнение операций вставки и добавления для массива типа list и двоичного дерева (время в миллисекундах) Table 6-1. Comparing insert and remove performance of lists against binary search tree (time in ms)

Как и следовало ожидать, время добавления элемента в конец списка — это константа, 0.004; это наилучший случай для вставки в значения структуру типа list. Время добавления тысячи элементов в начало списка практически удваивается с удвоением длины списка N. Стало быть, сложность этого действия линейна — O(N). Возможно, сразу этого видно не было, но теперь становится понятно, что поддерживать порядок элементов в массиве — дело довольно затратное. Столбец «Удаление» таблицы 6-1 показывает, что удалить тысячу элементов из начала списка столь же затратно: вычислительная сложность этого действия тоже линейна. Время добавления удваивается с увеличением размера списка вдвое, в каждой следующей строке этого столбца записано число, примерно вдвое большее числа над ним. As you can see in Table 6-1, the time to append values to the end of a list is constant at 0.004; this can be considered the best case for inserting values into a list. The time to prepend 1,000 values to the front of a list essentially doubles when the size of the problem instance, N, doubles. This operation can be classified as O(N). This table demonstrates the hidden cost of using a list to maintain a collection of sorted val‐ ues. The column labeled “Remove” in Table 6-1 reveals that removing the first value from a list 1,000 times is O(N) too, since its runtime performance doubles as N dou‐ bles. Each successive value in this column is almost exactly twice as large as the value above it.

В второй главе мы уже выяснили: если вставка тысячи элементов имеет сложность O(N), то и вставка одного — тоже O(N). Вставка десяти тысяч элементов — по тем же соображениям — также будет O(N). Отличаются все три числа только мультипликативной постоянной.

Итак, опыт показал, что вставка или удаление произвольного элемента имеет линейную сложность. Это значит, что если в алгоритме имеется массив, то постоянное соблюдение порядка элементов в нём может сильно замедлить программу. А теперь посмотрим на столбец «Дерево» таблицы 6-1, в котором приведены замеры тысячи операций вставки значения в сбалансированное двоичное дерево. Когда количество элементов в дереве увеличивается вдвое, время работы увеличивается — но не в разы, а на фиксированное значение, а это признак логарифмической сложности, O(log N). К тому же помимо эффективной вставки в дерево, мы ожидаем от него не менее эффективных поиска и удаления. This empirical trial reveals O(N) performance when simply inserting or removing a value; maintaining the array in sorted order will only slow the program down. In contrast, the column labeled “Tree” in Table 6-1 reports the runtime performance when using a balanced binary search tree to maintain the collection of values while inserting 1,000 new values. As the problem size doubles, the runtime performance appears to increase by a constant amount, which is characteristic of O(log N) perfor‐ mance. Even better, the binary search tree provides efficient search, insert, and remove operations.

Давайте возьмём упорядоченный массив, который мы использовали для изучения двоичного поиска, и превратим его в двоичное дерево поиска, для чего возьмём центральный элемент массива и поместим его в корень дерева. Два поддерева справа и слева от корня формируются по тому же принципу из отрезков массива справа и слева от центрального элемента. По причинам историческим то, что, например, в стеке или куче называлось «вершиной», в дереве называется «корнем»: да, наши деревья растут сверху вниз! В сумме в нашем дереве получится сем элементов, как и в массиве. Поместим обе структуры данных рядом на иллюстрации 6-3. Figure 6-3 contains an example of a binary search tree placed side by side with a sor‐ ted array containing the same values. This is the same array from Figure 2-5, where I presented Binary Array Search. The top node in a binary tree is designated as the root of the tree, analogous to how the first node in a linked list is specially designated. In total there are seven nodes in this tree.

Иллюстрация 6-3. Дерево двоичного поиска из семи элементов

Каждый узел двоичного дерева поиска соответствует примеру 6-3: поле left ссылается на узел, и этот узел — корень собственного поддерева, поле right — аналогично. В дереве поиска вводится два дополнительных общих правила для всех узлов: Each node in the binary search tree has the structure defined in Listing 6-3. left refers to a node that is the root of its own subtree; the same is true of right. A binary sea rch tree adds two global constraints for each node, n, in the tree:

• Если у узла n есть левое поддерево, все значения поля value в нём не превосходят n.value. • If a node, n, has a left subtree, all values in the subtree are ≤ n.value.

• Если у узла n есть правое поддерево, все значения поля value в нём не меньше n.value. • If a node, n, has a right subtree, all values in the subtree are ≥ n.value.

Оба свойства соблюдены в дереве на иллюстрации 6-3. Назовём листом узел, в котором оба поддерева пусты — в нашем дереве четыре узла со значениями 3, 15, 26 и 58. Вот тут уже большинство согласится с тем, что деревья в программировании растут сверху вниз: у них не только корень вверху, но и листья внизу! You can confirm these properties hold in Figure 6-3. A leaf node is a node without a left or right subtree; there are four leaf nodes in this tree, containing the values 3, 15, 26, and 58. Many people have commented that computer science trees are upside down, because the leaves are at the bottom, while the root is at the top.

   1 class BinaryNode:
   2   def __init__(self, val):
   3     self.value = val            # 1
   4     self.left = None            # 2
   5     self.right = None           # 3

• Пример 6-3. Структура двоичного дерева (в частности, дерева поиска) Listing 6-3. Structure of a binary search tree

1. Каждый узел хранит значение value Each node stores a value.

2. Поле left — это (возможно, пустое) поддерево, все хранимые значения которого ⩽ value. Each node’s left subtree, if it exists, contains values ≤ value.

3. Поле right — это (возможно, пустое) поддерево, все хранимые значения которого ⩾ value. Each node’s right subtree, if it exists, contains values ≥ value.

Ещё раз посмотрим на иллюстрацию 6-3. Левое поддерево корневого узла — это дерево, корень которого хранит значение 14, левый потомок — лист со значением 3, а правый потомок — лист со значением 15. Это те самые значения, что лежат в массиве в правой части иллюстрации, все они не больше 19, центрального элемента массива. При добавлении элемента по одному двоичные деревья прирастают снизу, как это показано в таблице 6-2. Referring back to Figure 6-3, you can see how the left subtree of the root node is itself a tree whose root node, 14, has a left leaf node (representing 3) and a right leaf node (representing 15). These are exactly the same values in the array depicted on the right that are smaller than or equal to 19, the middle index in the array. A binary tree grows top to bottom as values are inserted, one at a time, as shown in Table 6-2.

• Таблица 6-2. Последовательное добавление значений 19, 14, 15, 53, 58, 3 и 26 в двоичное дерево поиска Table 6-2. Creating a binary search tree by inserting (in order) 19, 14, 15, 53, 58, 3, and 26

Заведём для удобства класс BinaryTree, в котором пока что будет только работа с корнем дерева, но далее в этой главе мы добавим туда другие полезные методы. В примере 6-4 задана также процедура добавления элемента в дерево. It is convenient to have a BinaryTree class to maintain the reference to the root node for a binary tree; over time in this chapter, additional functions will be added to this class. Listing 6-4 contains the code needed to insert values into a binary search tree.

   1 class BinaryTree:
   2   def __init__(self):
   3     self.root = None                                   # 1
   4 
   5   def insert(self, val):
   6     self.root = self._insert(self.root, val)           # 2
   7 
   8   def _insert(self, node, val):
   9     if node is None:
  10       return BinaryNode(val)                           # 3
  11     if val <= node.value:                              # 4
  12       node.left = self._insert(node.left, val)
  13     else:                                              # 5
  14       node.right = self._insert(node.right, val)
  15     return node                                        # 6

• Пример 6-4. Класс BinaryTree, в который мы будем добавлять методы работы с двоичными деревьями поиска Listing 6-4. BinaryTree class to improve usability of binary search tree

1. Корневой узел древа — self.root (если дерево пусто, равно None). self.root is the root node of the BinaryTree (or None if empty).

2. Вспомогательный метод ._insert() добавляет val в дерево с корнем self.root. Use _insert() helper function to insert val into tree rooted at self.root.

3. Основание рекурсии: поддерево пусто, возвращаем новый узел BinaryNode. Base case: to add val to an empty subtree, return a new BinaryNode.

4. Если val не больше значения узла, его следует добавить в левое поддерево, node.left. If val is smaller than or equal to node’s value, set node.left to be the subtree that results when inserting val into subtree node.left.

5. В противном случае (val больше значения узла) val следует добавить в правое поддерево, node.right. If val is larger than node value, set node.right to be the subtree that results when inserting val into subtree node.right.

6. По договорённости метод ._insert() всегда возвращает — существующий или только что созданный — корень дерева, в которое было добавлено значение. This method must return node to uphold its contract that it returns the root of the subtree into which val was inserted.

Метод .insert(значение) рекурсивно вызывает ._insert(узел, значение) с параметром self.root — таким образом либо создаётся прежде пустой корень дерева, либо значение добавляется в одно из поддеревьев self.root¹. The insert(val) function in BinaryTree invokes the recursive _insert(node, val) helper function to set self.root to be the subtree that results when inserting val into the subtree rooted at self.root.1

Достоинство рекурсивных структур данных — процедуры работы с ними выглядят коротко и получаются как бы сами собой, например .insert() — это всего лишь частный случай работы ._insert(), который и добавляет элемент в поддерево, и возвращает (возможно, обновлённый) его корень. The casual and elegant one-line implementation of insert() is a feature of programs using recursive data structures. The _insert() function both inserts val and returns the root of the resulting subtree.

1 All recursive helper functions start with an underscore (_) to declare that these functions are not intended to be part of the public interface for BinaryTree.

В нашем примере все добавляемые значения были разными, но это, конечно, необязательно. Значения, хранящиеся в дереве, могут повторяться — именно поэтому _insert() сравнивает их на меньше либо равно.

Основание рекурсии в ._insert(node, val) — пустой (равный None) параметр node, это бывает, когда val нужно вставить в пустое поддерево. В этом случае просто создаётся новый BinaryNode — это и будет корень возвращаемого поддерева. В рекурсивном вызове выбирается, в какое поддерево нужно добавить val — левое (node.left) или правое (node.right). Во всех случаях должна выполняться договорённость: _insert() добавляет val в дерево с корнем node — и возвращает корень дерева, в которое добавлен val. In _insert(node, val), the base case occurs when node is None, which occurs when‐ ever val is requested to be inserted into a nonexistent subtree; it just returns a new subtree rooted by the newly created BinaryNode. For the recursive case, val is inser‐ ted into either the left subtree, node.left, or the right subtree, node.right. At the end of the recursive case, it is critical that _insert() returns node to fulfill its obliga‐ tion of returning the root of the subtree that results from adding val to the subtree rooted at node.

Вызов ._insert(node, val) следит за сохранением основного свойства двоичного дерева поиска: все значения в левом поддереве должны не превосходить node.value, а все значения в правом должны быть больше. _insert(node, val) maintains the binary search tree property such that all values in the left subtree for node are smaller than or equal to node.value, and values in the right subtree are larger than or equal to node.value.

Узел n двоичного дерева может иметь левый и правый дочерний узел. Для n.left и .right узел n называется родительским. Соответственно, потомки n — это все узлы правого и левого поддеревьев. Каждый узел, кроме корневого, имеет по меньшей мере одного или больше предков, чьим наследником он и является.

Попробуем добавить число 29 в двоичное дерево поиска с иллюстрации 6-3. 29 больше корня, 19, значит его нужно добавить в правое поддерево с корнем 53. 29 меньше 53, значит, добавлять нужно в левое поддерево с корнем 26. 29 больше 26, соответствующее правое поддерево пусто, так что число 26 становится корнем нового правого поддерева. Результат приведён на иллюстрации 6-4. Try inserting 29 into the binary search tree from Figure 6-3. 29 is larger than the root, so it must be inserted into the right subtree rooted by 53. 29 is smaller than 53, so insert into its left subtree rooted at 26. Finally, 29 is larger than 26, so it forms the new right subtree for 26, as shown in Figure 6-4.

Иллюстрация 6-4. Как добавить 29 в двоичное дерево поиска

Дерево может получиться очень разным в зависимости от того, в каком порядке мы добавляем туда элементы. Например, дерево в левой части иллюстрации 6-5 очевидно началось с добавления числа 5 (которое стало корнем), и вообще всякий предок точно был добавлен раньше своих потомков. The order in which values are inserted determines the structure of the final binary tree, as you can see in Figure 6-5. For the binary search tree on the left, you know that 5 was the first value inserted, since it is the root of the tree. In addition, every node must have been inserted after its ancestor.

На той же иллюстрации справа — также двоичное дерево поиска, которое получилось после добавления семи последовательно растущих значений. Образовался наихудший случай для двоичного дерева поиска: если повернуть картинку против часовой стрелки на 45°, получится связный список, с одним потомком у каждого узла. Это резко понижает производительность. В этой главе мы попробуем придумать, как добавляя и удаляя элементы не нарушать баланс наших древовидных структур. The binary search tree on the right was formed by inserting the seven values in increasing order, which reveals the worst case for inserting values into a binary search tree; if you rotate the image counterclockwise about 45 degrees, it looks like a linked list, in which case it loses its efficiency. Toward the end of this chapter, I present a strategy to maintain more balanced tree structures in the face of insertions and removals.

Иллюстрация 6-5. Как различаются деревья двоичного поиска

Поиск значения в двоичном дереве

Searching for Values in a Binary Search Tree

У нас уже есть метод поиска нужного места в дереве — этим занимается ._insert(), когда рекурсивно проходит до соответствующего пустого поддерева и добавляет туда узел. Можно было бы поступить так же: если нужное значение встретилось, поиск успешен, а если добрались до пустого узла — нет. Однако, как показано в примере 6-5, здесь проще обойтись без рекурсии, обычным циклом while. The _insert() method recursively finds the appropriate location to insert a new leaf node containing the value to be added. This same recursive approach could simply check whether a value is contained in a binary search tree; in practice, however, the code in Listing 6-5 offers a simpler, non-recursive solution using a while loop.

   1 class BinaryTree:
   2   def __contains__(self, target):
   3     node = self.root                    # 1
   4     while node:
   5       if target == node.value:          # 2
   6         return True
   7       if target < node.value:           # 3
   8         node = node.left
   9       else:
  10         node = node.right               # 4
  11     return False                        # 5

• Пример 6-5. Как проверить, содержится ли значение в двоичном дереве Listing 6-5. Determining whether a BinaryTree contains a value

1. Начнём поиск с корня. Start the search at the root.

2. Если значение текущего узла совпадает с target, поиск успешен; вернём True. If target value is same as node’s value, return True for success.

3. Если target меньше значения текущего узла, продолжим поиск в левом поддереве. If target is smaller than node’s value, set node to its left subtree to continue search in that subtree.

4. В противном случае (если target был больше) продолжим поиск в правом дереве. If target had been larger than node’s value, continue search in right subtree.

5. Если мы встретили пустой узел, то больше искать негде — значения в дереве нет; вернём False. If the search runs out of nodes to inspect, the value does not exist in the tree, so return False.

Метод .__contains__() мы дописали в класс BinaryTree вдобавок к уже реализованным процедурам². Работает он подобно процедуре поиска значения в связном списке, но различие в том, что всякий раз выбирается только одно следующее поддерево для поиска — левое или правое. This contains() function is added to the BinaryTree class.2 Its structure is simi‐ lar to searching for a value within a linked list; the difference is that the next node to be searched could either be left or right based on the relative value of target.

Удаление значения из двоичного дерева

Removing Values from a Binary Search Tree

Удалить значение из связного списка весьма просто, но в случае дерева всё несколько сложнее. Допустим, мы хотим удалить значение, а оно оказалось в корне дерева. Если удалить корень, как потом «срастить» два осиротевших поддерева? А если не в корне — всё равно должен быть какой-то простой и понятный общий способ? Попробуем догадаться что это за способ на примере, в котором удаляется значение именно из корня. Рассмотрим приведённые на иллюстрации 6-6 исходное двоичное дерево поиска и два варианта двоичных деревьев поиска, в которых уже нет удалённого узла. Removing a value from a linked list was relatively straightforward—as discussed in Chapter 3—but removing a value from a binary search tree is more challenging. To start with, if the value to be removed is contained in the root node, how do you “stitch together” its orphaned left and right subtrees? Also, there should be a least- effort consistent strategy that works every time. Let’s try to find an intuitive solution to remove the value contained in the root node of a binary search tree. Figure 6-6 offers two possible binary search trees after removing the root value of 19.

Иллюстрация 6-6. Два возможных варианта удаления 19 из двоичного дерева поиска

2 Implementing this function means a program can use the Python in operator to determine if a value is con‐ tained in a BinaryTree object.

Ещё раз заметим, что в обоих вариантах получаются именно деревья двоичного поиска: значения в левом поддереве не превосходят значения в корне, а значения в правом поддереве не меньше корня. И того, и другого варианта можно достичь сравнительно несложно: You can confirm that both of these options remain binary search trees: the values in each left subtree remain smaller than or equal to its root, and the values in each right subtree remain larger than or equal to its root. The effort involved appears to be min‐ imal for both options:

• Вариант 1: найти и удалить наибольшее значение в левом поддереве и использовать его в качестве корня. • Option #1: Find and remove the maximum value in the left subtree, and use that value for the root.

• Вариант 2: найти и удалить наименьшее значение в правом поддереве и использовать его в качестве корня. • Option #2: Find and remove the minimum value in the right subtree, and use that value for the root.

Разницы между вариантами никакой, давайте выберем второй. Убедимся, что полученное дерево — двоичное дерево поиска. Его новый корень, 26, — это наименьшее значение из правого поддерева, и значит, все элементы перестроенного правого поддерева на иллюстрации 6-6 не меньше 26. При этом левое поддерево не изменилось, и все его элементы были не больше 19 — старого корня, — а 26 не меньше этого корня, и стало быть, всех остальных элементов левого поддерева.

Each of these options is acceptable, and I choose to implement the second one. The resulting binary tree is a valid binary search tree because the new root value of 26 is the smallest value in the original right subtree—which means by definition it is smaller than or equal to all values in the revised subtree shaded in Figure 6-6. In addition, it is larger than or equal to all values in the original left subtree because it is larger than or equal to the original root value of 19, which was already larger than or equal to the values in the original left subtree.

Для начала разберёмся с тем, как удалить наименьшее значение в поддереве. Если подумать, становится ясно, что у минимального элемента поддерева нет левого потомка — иначе этот левый потомок сам был бы минимальным элементом³. Например, на иллюстрации 6-7 наименьшее значение правого поддерева с корнем 53 — это 26, и у него нет левого потомка. Если этот узел удалить, останется только «поднять» его правое поддерево (с корнем 29) на место левого поддерева узла 53. Наименьший узел всегда можно при удалении заменять его правым поддеревом, потому что левого поддерева у него нет, и других узлов мы при этом не потеряем. Let’s start by solving the sub-problem that removes the minimum value in a given subtree. If you think about it, the minimum value in a subtree cannot have a left child —since otherwise a smaller value would exist. Given the binary search tree in Figure 6-7, the minimum value in the right subtree rooted at 53 is 26, and as you can see, it has no left child. Removing this value only requires “lifting up” its right sub‐ tree, rooted at 29, to become the new left subtree to 53. Setting the left child of 53 to be the tree rooted at 29 will always work, since 26 has no left subtree and no values will be lost.

Иллюстрация 6-7. Удаление наименьшего значения в дереве

В примере 6-6 мы завели в BinaryTree вспомогательный метод ._remove_min(узел), который удаляет наименьший элемент дерева с корнем узел; метод можно вызывать только на непустых узлах. Если передать этому методу правого потомка дерева с иллюстрации 6-7, произойдёт рекурсивный вызов, а именно — попытка удалить наименьшее значение из левого поддерева с корнем 26. Это уже основание рекурсии, потому что у 26 нет левого потомка, значит, настала пора «поднять» правое поддерево (с корнем 29) на место удалённого узла и вернуть это правое поддерево в качестве нового левого поддерева 53. Listing 6-6 contains the helper function in BinaryTree, _remove_min(node), that removes the minimum value in the subtree rooted at node; this function is never called when node is None. When invoking _remove_min() on rc—the right child of the tree in Figure 6-7—the recursive case is invoked, namely to remove the minimum value in the left subtree rooted at 26. This leads to the base case, since 26 has no left subtree, and in its place the function “lifts up” and returns its right subtree rooted at 29 to become the new left subtree to 53.

   1 def _remove_min(self, node):
   2   if node.left is None:                         # 1
   3     return node.right
   4 
   5   node.left = self._remove_min(node.left)       # 2
   6   return node                                   # 3

• Пример 6-6. Как удалить наименьшее значение. Listing 6-6. Removing minimum value

1. Основание рекурсии: у узла нет левого потомка, значит он содержит наименьшее значение в поддереве, «поднимаем» на его место правое поддерево (которое может быть и пустым) и возвращаем его. Base case: if node has no left subtree, then it is the smallest value in the subtree rooted at node; to remove it, just “lift up” and return its right subtree (which could be None).

2. Рекурсивный вызов: удаляем наименьшее значение из левого поддерева, а то, что нам возвратил метод ._remove_min(), записываем в левое поддерево узла. Recursive case: remove the minimum value from left subtree, and the returned subtree becomes new left subtree for node.

3. При рекурсивном вызове ._remove_min() сам узел не меняется (возможно, меняется его левое поддерево), возвращаем его. _remove_min() completes the recursive case by returning the node whose left subtree may have been updated.

Снова у нас вышло коротко и ясно! Метод ._remove_min(), как и предыдущие рекурсивные методы, возвращает корень обновлённого поддерева. Теперь можно дополнить класс BinaryTree методом .remove(), которые удаляет значение из двоичного дерева поиска. На примере диаграмм в таблице 6-3 рассмотрим, как именно должно происходить удаление значения 19, которое находится в корне двоичного древа поиска. На диаграммах упоминаются две переменные: original, указывающая на удаляемый узел, и node, в которой окажется узел на замену удаляемому. Once again, this code is brief and elegant. As with the other recursive functions dis‐ cussed earlier, _remove_min() returns the root node of the modified subtree. With this helper function, I can now complete the implementation of remove() that removes a value from a binary search tree. To visualize what the code must do, Table 6-3 shows an example of the changes to a binary tree when removing the value, 19, contained in its root node.

• Таблица 6-3. Как удалить корень двоичного дерева поиска Table 6-3. Demonstrating how root node is removed from binary search tree

На диаграммах перевод не требуется -- FrBrGeorge 2022-11-30 15:53:39

Теперь посмотрим на реализацию .remove() в примере 6-7. The implementation of remove() is shown in Listing 6-7.

   1 def remove(self, val):
   2   self.root = self._remove(self.root, val)              # 1
   3 
   4 def _remove(self, node, val):
   5   if node is None: return None                          # 2
   6 
   7   if val < node.value:
   8     node.left = self._remove(node.left, val)            # 3
   9   elif val > node.value:
  10     node.right = self._remove(node.right, val)          # 4
  11   else:                                                 # 5
  12     if node.left is None: return node.right
  13     if node.right is None: return node.left             # 6
  14 
  15     original, node = node, node.right                   # 7
  16     while node.left:                                    # 8
  17       node = node.left
  18 
  19     node.right = self._remove_min(original.right)       # 9
  20     node.left = original.left                           # 10
  21   return node

• Пример 6-7. Удаление значения из BinaryTree Listing 6-7. Removing a value from a BinaryTree

1. Используем вспомогательный метод ._remove(): ему можно указать корень конкретного поддерева, из котрого надо удалять элемент. В нашем случае это self.root. Use _remove() helper function to remove val from tree rooted at self.root.

2. Основание рекурсии: если дерево пусто, вернём None. Base case: attempting to remove val from nonexistent tree returns None.

3. Первый вариант рекурсивного вызова: удаляемое значение меньше node.value, значит удалять надо из левого поддерева. Запишем в node.left обновлённое поддерево — результат удаления оттуда val. Recursive case #1: if value to be removed is smaller than node.value, set node.left to be the subtree that results from removing val from node.left.

4. Второй вариант рекурсивного вызова: удаляемое значение больше node.value, значит удалять надо из правого поддерева, node.right. Обновим node.right, записав туда результат удаления val из него. Recursive case #2: if value to be removed is larger than node.value, set node.right to be the subtree that results from removing val from node.right.

5. Третий вариант рекурсивного вызова: узел хранит удаляемое значение. Возможно, надо удалять именно этот узел, а может, надо поискать кандидата получше. Recursive case #3: it may be that node is root of subtree and contains value to be removed, so there’s work to be done.

6. Сначала немного оптимизации. Если одно из поддеревьев пусто, можно смело удалять именно этот узел, а возвращать оставшееся поддерево. Если и оно было пусто, значит узел — это лист, и вернётся None. Handle easy cases first. If node is a leaf, then None is returned. If it has just one child, then return that child node.

7. Поищем узел без левого потомка. Запомним исходный узел в original: нам ещё работать с его поддеревьями, .left и .right. В этом месте оба поддерева непусты. Remember original reference to node, since we don’t want to lose track of node’s original left and right subtrees, both of which must exist.

8. Согласно выбранному правилу, начнём поиск наименьшего элемента в правом поддереве. Теперь node равен node.right, и пока у node есть левое поддерево, мы не можем быть уверены, что его значение наименьшее. Так что мы в цикле будем выбирать самый левый узел без левого потомка — наименьшее значение правого поддерева original будет в нём. Start with node = node.right to find the smallest value in the subtree rooted at node.right: as long as node has a left subtree, then it does not contain the small‐ est value, so iteratively locate the node with no left subtree—this is the smallest value in the right subtree of original.

9. Мы нашли узел node, который должен стать новым корнем с поддеревьями original.left и original.right. Левое его поддерево не изменится, а вот из правого надо удалить наименьшее значение. Воспользуемся для этого уже написанным методом ._remove_min() и положим результат в original.right. Можно заметить, что рекурсивный вызов ._remove_min() выполнит заново всё то, что мы только что уже делали, но так всё-таки понятнее, чем пытаться объединить логику работы обоих методов в одном цикле while. node will become the new root to the left and right children of original. Here I set node.right to the subtree that results from removing the minimum value from original.right. You might notice that this recursive method essentially repeats the process of the while loop, but this code is much easier to understand than trying to do everything in just one pass.

10. Теперь оба поддерева original перенесены в node. Stitch the subtree rooted at node back together.

Что ещё нам нужно от двоичного дерева поиска? Хотелось бы получить упорядоченную последовательность всех его значений! В программировании это называется обходом дерева. The final capability supported by a binary search tree is returning the values in ascending order. In computer science this is known as a traversal.

Обход двоичного дерева

Traversing a Binary Tree

Связный список пройти поэлементно просто: начать с первого узла и в цикле while переходить к элементу, на которое указывает поле next, до тех пор, пока оно не пусто. НО такой линейный подход не годится для деревьев: есть сразу два пути дальнейшего просмотра, left и right. По-видимому, раз уж деревья рекурсивны, то и обход их тоже должен быть рекурсивным. В примере 6-8 мы зададим рекурсивный метод-генератор, и с его помощью аккуратно обойдём все узлы дерева. To process each element in a linked list, start at the first node and use a while loop to follow next references until all nodes are visited. This linear approach can’t work with a binary search tree because there are left and right references to follow. Given the recursive nature of a binary tree data structure, there needs to be a recursive solution. Listing 6-8 contains an elegant recursive solution that uses Python generators.

   1 class BinaryTree:
   2 
   3   def __iter__(self):
   4     yield from self._inorder(self.root):        # 1
   5 
   6   def _inorder(self, node):
   7     if node is None:                            # 2
   8       return
   9 
  10     for v in self._inorder(node.left):          # 3
  11       yield v
  12 
  13     yield node.value                            # 4
  14 
  15     for v in self._inorder(node.right):         # 5
  16       yield v

• Пример 6-8. Метод-генератор, который обходит узлы двоичного дерева пои восходящем порядке Listing 6-8. Generator that iterates over values in binary search tree in ascending order

1. Отдадим управление вспомогательному генератор-методу ._inorder(self, node), который обходит в порядке возрастания дерево с корнем node. В качестве параметра передадим ему корень всего дерева, self.root. Yield all values that result from the in order traversal of binary search tree rooted at self.root

2. Основание рекурсии — пустое поддерево. Base case: nothing to generate for a nonexistent subtree.

3. Сначала пройдём по левому поддереву, node.left. To generate all values in order, first generate all values in order from the subtree rooted at node.left.

4. Следом вернём значение текущего узла. Now it is node’s turn to yield its value.

5. Наконец пройдём по правому поддереву, node.right. Таким образом все значения окажутся перечислены в порядке возрастания. Finally, generate all values in order from the subtree rooted at node.right.

Вспомогательный метод ._inorder(self, node) проходит все узлы дерева с корнем node и возвращает их по одному. Основание рекурсии наступает, когда соответствующее поддерево пусто — ._inorder() ничего не завершает итерацию. Все узлы левого поддерева, node.left, в двоичном дереве поиска по построению не больше корня node.value, а узлы правого дерева, node.right, не меньше него. Значит, если рекурсивно обойти левое поддерево, затем вернуть значение в узле, а затем обойти правое поддерево, значения будут возвращаться в порядке возрастания. Иллюстрация 6-8 представляет этот процесс в виде диаграмм для двоичного дерева T с пятью значениями.

Метод .__iter__() — принятым в Python способом — отдаёт перечисление элементов методу ._inorder() с соответствующим параметром — корнем всего дерева⁴. The iter() function repeatedly yields the values provided by the recursive helper function, _inorder(), using a common idiom provided by Python. For the base case of the recursion, when asked to yield the values for a nonexistent binary search tree rooted at node, _inorder() returns and does nothing. For the recursive case, this function relies on the binary search tree property that all values in the sub‐ tree rooted at node.left are smaller than or equal to node.value and that all values in the subtree rooted at node.right are larger than or equal to node.value. It recur‐ sively yields all values in node.left before yielding its own value, and subsequently yielding the values in node.right. The process is visualized in Figure 6-8 with a binary search tree, T, containing five values.

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

Итак, теперь мы умеем искать значения в дереве двоичного поиска, добавлять их туда и удалять оттуда, а ещё мы научились получать упорядоченную последовательность значений дерева. Настала пора посмотреть, с какой скоростью всё это работает. I have now shown how to search, insert, and remove values from a binary search tree; in addition, you can retrieve these values in ascending order. It’s time to collectively analyze the performance of these fundamental operations.

Иллюстрация 6-8. Проход по всем узлам двоичного дерева поиска в порядке возрастания их значений

Исследование быстродействия двоичных деревьев поиска

Analyzing Performance of Binary Search Trees

Для того, чтобы замерить быстродействие поиска, добавления и удаления, нужно знать высоту дерева. Высота некоторого узла — это количество ссылок на правое или левое поддерево, которые нужно пройти, чтобы достигнуть наиболее отдалённого листового узла. Высота листового узла, соответственно, нулевая, а высота всего дерева поиска — это высота его корневого узла. The determining factor for search, insert, and remove operations is the height of the tree, which is defined as the height of its root node. The height of a node is the num‐ ber of left or right references you need to get from that node to its most distant descendant leaf node. This means the height of a leaf node is 0.

Высота листового узла равно 0, следовательно, высота пустого узла — узла со значением None — не может быть тоже нулём, она должна быть ещё меньше. В наших вычислениях удобно использовать -1 в качестве высоты пустого узла.

Количество узлов, которые в худшем случае придётся просмотреть при поиске по двоичному дереву, равно высоте этого дерева, то есть высоте корневого узла. Допустим, в дереве N узлов — какова его высота? Мы помним, что высота определяется порядком добавления элементов в дерево. Наилучший случай, то есть максимум узлов при минимуме высоты — это полное двоичное дерево, в котором заполнены все уровни. В дереве при этом 2^k-1 узлов, а высота его равна k-1. К примеру, на иллюстрации 6-9 представлено полное дерево высотой 5, в котором 63 узла. Поиск по такому дереву займёт не более шести сравнений: если начать с корневого узла и переходить по ссылкам left и right, мы посетим не более шести узлов. Поскольку 63 = 2⁶-1, время поиска по такому дереву пропорционально log(N + 1). А вот в худшем случае, когда значения добавлялись в возрастающем или убывающем порядке, двоичное дерево поиска превращается в последовательную цепочку, и высота его будет N - 1 (как на иллюстрации 6-5). В общем, если высота двоичного дерева поиска — h, то производительность оценивается на O(h). In the worst case, the number of nodes visited during a search is based on the height of the root of the binary search tree. Given N nodes in a binary search tree, what is its height? It depends entirely on the order in which the values had been inserted. A complete binary tree represents the best case since it efficiently stores N = 2k – 1 nodes in a tree whose height is k – 1. The binary tree in Figure 6-9, for example, has N = 63 nodes, and the height of the root node is 5. Searching for a target value will involve no more than 6 comparisons (since with 5 left or right references you will visit 6 nodes). Since 26 – 1 = 63, this means that the time to search for a value is propor‐ tional to log (N + 1). But in the worst case, all values were inserted in ascending (or descending) order, and the binary search tree is just a long linear chain, as shown in Figure 6-5. In general, the runtime performance of search is O(h), where h is the height of the binary search tree.

Иллюстрация 6-9. Полное дерево содержим маскимум узлов при минимально возможной высоте

Добавить новый узел занимает столько же времени, что и найти несуществующий — надо пройти до какого-то листового узла, разница только в том, что у этого узла появится левое или правое поддерево, куда придётся добавить ещё один листовой узел. Но сложность при этом остаётся O(h). Inserting a value has the same time complexity as searching for a value—the only dif‐ ference is that a new leaf node is inserted once the search ends with a nonexistent left or right subtree; so inserting a value is O(h) as well.

Чтобы удалить узел из двоичного дерева поиска, надо проделать три операции: Removing a value from a binary search tree requires three steps:

1. Найти узел с нужным значением Locate the node containing the value to be removed

2. Найти в правом поддеревеве этого узла узел с наименьшим значением Locate the minimum value in the right subtree of the node containing the value to be removed

3. Удалить наименьший узел из правого поддерева (и подменить значение текущего узла)

В наихудщшем случае количество действий в каждой из этих операций пропорционально высоте⁵, так что в самом худшем варианте врема, потраченное на удаление, будет пропорционально 3·h (где h — высота всего дерева). В главе 2 мы уже выяснили, что мультипликативная постоянная не влияет на общую оценку, так что время удаления элемента также оказывается порядка O(h). Each of these substeps in the worst case can be directly proportional to the height.3 At worst, then, the time to remove a value is proportional to 3 × h, where h is the height of the binary search tree. Based on the results from Chapter 2, since 3 is just a multi‐ plicative constant, this means that the time to remove a value remains O(h).

Структура двоичного дерева поиска определяется порядком добавления элементов в него и удаления их оттуда, и нет способа этот порядок заранее определить. Значит, нужна возможность оценить, насколько эффективна сложившаяся структура дерева. В главе 3 мы посмотрели, как масштабируется хеш-таблица при достижении пороговой загруженности: размер увеличивается вдвое, а элементы хешируются заново. Геометрическое масштабирование позволяет сделать эту дорогостоящую (O(N)) операцию настолько редкой, что порядок производительности остаётся неизменным: как мы помним — константным, O(1) для действия get(). The structure of the binary search tree is based entirely on the order in which the val‐ ues are inserted and removed. Since the binary search tree cannot control how it is used, it needs a mechanism to detect when its structure is performing poorly. In Chapter 3, I explained how hashtables resized themselves—rehashing all its entries— once a threshold size was hit. It was acceptable for hashtables to do this, because this costly O(N) operation would become ever more infrequently requested using the geometric resizing strategy. As you may recall, doing so enabled the average O(1) runtime performance for get().

О геометрическом масштабировании можно было бы задуматься, если бы мы хранили узлы дерева в массиве (как кучу), но при таком подходе совершенно непонятно, когда именно хранилище нуждается в расширении, и как часто оно будет требоваться. Пороговое значение должно зависеть от N, а, например, если хранить дерево как кучу, поуровнево, порог определяется не количеством элементов, а высотой. Посмотрим на иллюстрацию 6-10: всего пара неудачных вставок — и нам требуется в четыре раза больше места под ещё два уровня! Для наглядности узлы одинаковой высоты обозначены на иллюстрации одинаковым фоном. Заметим, что само дерево при этом получается несбалансированным: кратчайший путь от корня до листового узла оказывается вдвое меньше высоты.

Автор тут натурально сыграл в карго-культ. Вообще-то геометрическое масштабирование — это способ динамического выделения памяти, а не решения всех проблем, и от дисбаланса дерева он помогает не лучше модели грузовоза из мха и веток. Был выбор либо всё это удалить, либо попытаться вдумать туда смысл. Я вдумал. -- FrBrGeorge 2022-12-02 11:24:57 The geometric resizing strategy will not work here because there is no simple thres‐ hold computation based on N that can determine when to resize, and you can’t ensure that resize events become ever more infrequent: all it takes is a small sequence of awkward insertions to unbalance a tree, as visualized in Figure 6-10. Each node is color-coded by its height.

Иллюстрация 6-10. Несбалансированное дерево после добавления двух элементов

3 See a challenge exercise at the end of the chapter on this point.

Полное двоичное дерево на иллюстрации 6-10 целиком сбалансировано: его высота (и высота корня) — 2, высота всех узлов первого уровня — 1, все узлы второго уровня листовые, и их высота — 0. Как только мы добавляем 29 (средняя диаграмма на иллюстрации), в соответствующем месте появляется новый листовой узел. При этом высота всех предков узла 29 увеличивается на единицу (обозначено на диаграмме фоном). После добавления 27 дерево окончательно разбалансируется (правая диаграмма на иллюстрации): левое поддерево, с корнем 14 имеет высоту 1, а правое — с корнем 53 — уже 3. Такая же картина и для других узлов, например, для 26 и 53. В следующем разделе мы посмотрим, как определить, что дерево нуждается в балансировке, и как эту балансировку делать. The complete binary tree on the left in Figure 6-10 has a perfectly balanced structure; each leaf node has a height of 0, and the root node has a height of 2. When 29 is inserted—as shown in the middle tree—a new leaf node is created in the proper loca‐ tion. Note that all ancestor nodes of 29 increase their height by 1, and they are shaded accordingly. After 27 is inserted—as shown in the right tree—the tree has lost its bal‐ ance: its left subtree at 14 has a height of 1, but its right subtree at 53 has a height of 3. Other nodes—such as 26 and 53—are similarly out of balance. In the next section, I explain a strategy for detecting and rebalancing binary search trees.

Сбалансированные двоичные деревья

Self-Balancing Binary Trees

Самая ранняя из известных сбалансированных древовидных структур данных, АВЛ-дерево, была изобретена в 1962 году⁶. Идея была в том, что при всяком добавлении или удалении значения отслеживается эффективность получившегося дерева, и если она недостаточна, дерево реорганизуется. В АВЛ-дереве гарантируется, что в каждой вершине высота правого и левого поддеревьев отличаются не более, чем на 1 (то есть разница между высотой правого поддерева и высотой левого может быть только -1, 0 или 1). The first known self-balancing binary tree data structure, the AVL tree, was invented in 1962.4 The premise is that as values are inserted into, or removed from, a binary search tree, weaknesses in the structure of the resulting tree are detected and repaired. An AVL tree guarantees that the height difference of any node—defined as the height of the node’s left subtree minus the height of the node’s right subtree—is –1, 0, or 1. 4 Named after the inventors Adelson-Velsky and Landis.

Как показано в примере 6-9, высоту поддерева удобно знать заранее и хранить в BinaryNode в поле height. Всякий раз при добавлении элемента в дерево высоты узлов, изменивших место в иерархии, вычисляются заново, так что несбалансированный узел будет видно сразу. As shown in Listing 6-9, each BinaryNode must store its height in the binary search tree. Whenever a node is inserted into the binary search tree, the height of the affec‐ ted nodes must be computed so an unbalanced tree node can be detected immediately.

   1 class BinaryNode:
   2   def __init__(self, val):
   3     self.value = val                                            # 1
   4     self.left = None
   5     self.right = None
   6     self.height = 0                                             # 2
   7 
   8   def height_difference(self):                                  # 3
   9     left_height = self.left.height if self.left else -1         # 4
  10     right_height = self.right.height if self.right else -1
  11     return left_height - right_height                           # 5
  12 
  13   def compute_height(self):                                     # 6
  14     left_height = self.left.height if self.left else -1
  15     right_height = self.right.height if self.right else -1
  16     self.height = 1 + max(left_height, right_height)

• Пример 9-6. Структура узла В АВЛ-дереве Listing 6-9. Structure of AVL binary node

1. BinaryNode в целом такой же, как и в простом двоичном дереве поиска. Structure of a BinaryNode is essentially the same as a binary search tree.

2. Здесь хранится высота узла. Record the height for each BinaryNode.

3. Вспомогательный метод, который вычисляет разность между высотами правого и левого поддеревьев. Helper function that computes the height difference between left and right sub‐ tree.

4. Если поддерево пусто, его высота, по договорённости, -1; в противном случае используем настоящую высоту. Set left_height to —1 for nonexistent left subtree, or its proper height.

5. Вернём разницу высот. С учётом высоты пустого поддерева это просто разность left_height и right_height. Return height difference, which must be left_height subtracting right_height.

6. Вспомогательный метод, который вычисляет высоту узла в предположении, что поле height левого и правого поддеревьев соответствует действительности (включая высоту -1 для пустых поддеревьев). Helper function that updates the height for a node assuming that the height of its respective left and right subtrees (if they exist) have accurate height values.

Теперь допишем метод _insert(): он должен вычислять значение узла при добавлении. Listing 6-10 shows that the node returned by _insert() has its height properly computed.

   1   def _insert(self, node, val):
   2     if node is None:
   3       return BinaryNode(val)                            # 1
   4 
   5     if val <= node.value:
   6       node.left = self._insert(node.left, val)
   7     else:
   8       node.right = self._insert(node.right, val)
   9 
  10     node.compute_height()                               # 2
  11     return node

• Пример 6-10. Дополним метод _insert() вычислением высоты Listing 6-10. Modify _insert() to compute height properly

1. Основание рекурсии — создание нового листового узла — не трбует вычисления длины, которая и так по умолчанию 0. For the base case, when a newly created leaf node is returned, its height is already 0 by default.

2. Когда отработает рекурсивный вызов, и val будет добавлено в правое или в левое поддерево, высота узла вполне можно измениться, так что её надо высчитать заново. When the recursive case completes, val has been inserted into either node.left or node.right. This means the height for node needs to be recomputed.

Посмотрим на иллюстрацию 6-11. Вот мы вызвали insert(27), и после нескольких рекурсивных вызовов создали новый листовой узел для 27, добавив его в двоичное дерево поиска. Концевой вызов _insert() достиг основания рекурсии и вернул только что созданный листовой узел 27. На иллюстрации видно, что оба узла — новый листовой (27) и старый листовой (29, будущий родитель) — ненадолго оба имеют высоту 0. Осталось только добавить единственный оператор — вычисление новой высоты узла — в конец _insert(), перед возвратом из рекурсивного вызова. Пока рекурсивные вызовы завершаются, высота каждого родителя пересчитывается (отмечено на иллюстрации фоном) — и заметим, что только у этих узлов двоичного дерева могла от добавления элемента измениться высота. Метод compute_height() высчитывает высоту узла из простого логического соображения: высота узла на единицу больше, чем высота самого высокого из поддеревьев этого узла. During the invocation of insert(27), a new leaf node for 27 is added to the binary search tree at the end of a sequence of recursive invocations, depicted in Figure 6-11. The final invocation to _insert() involves the base case where a new leaf node con‐ taining 27 is returned. This figure captures the brief moment when both the new leaf node (for 27) and the original leaf node (for 29) have a height of 0. With just one additional statement to compute the node’s height at the end of _insert(), as the recursion unwinds, the height for each ancestor node (highlighted in Figure 6-11) are recomputed—note that these are the only nodes in the binary search tree whose heights need to be adjusted. The compute_height() function captures the logical def‐ inition for the height of a node, namely, that it is one greater than the larger of the heights of its children subtrees.

Иллюстрация 6-11. Рекурсивные вызовы при добавлении элемента в дерево

Итак, с каждым завершением рекурсивного вызова пересчитывается высота соответствующего предка узла 27. Поскольку к этому моменту у всех потомков высота своевременно посчитана, _insert() может определить, что узел стал несбалансированным — это когда высоты правого и левого поддеревьев этого узла отличаются более чем на единицу. As the recursive invocations unwind, each ancestor node to 27 has its height recom‐ puted. Because each node has an accurate height in the binary search tree, _insert() can detect whenever a node has become unbalanced—that is, when the height of the left and right subtrees for that node differ by more than 1.

Разность высот узла определяется как разность между высотой правого поддерева данного узла и высотой его левого поддерева. Высота пустого поддерева равно -1. В АВЛ-деревьях разность высот любого узла должна быть -1, 0 или 1.

Будем говорить, что узел 26 «перевешивает вправо», потому что разница его весов равна -1 - -1 = -2. Соответственно, узел 53 перевешивает влево, потому что разница его весов — 2 - 0 = 2, а корень — вправо с разницей весов 1 - 3 = -2. После того, как мы отметили все потерявшие равновесие узлы, хотелось бы применить какой-нибудь алгоритм для восстановления баланса. Это можно сделать, например, в процессе возврата из рекурсивных вызовов, когда _insert() уже определил, что добавление узла разбалансировало дерево. Возврат из рекурсивных вызовов начинается с конца, с основания рекурсии, то есть первым найденным несбалансированным узлом будет 26. The node containing 26 leans to the right because its height difference is –1 – 1 = –2; the node containing 53 leans to the left because its height difference is 2 – 0 = 2; lastly the root node leans to the right because its height difference is 1 – 3 = –2. Once these nodes are identified, there needs to be a strategy to adjust the tree in some way to bring it back into balance. In the same way that the height is computed as the recur‐ sion unwinds, the _insert() function can immediately detect when the insertion of a new node has unbalanced the tree. It detects the imbalance as the recursion unwinds, which means the first unbalanced node detected is 26.

Тут изобретатели АВЛ-дерева вводят понятие «поворот узла», которое проще всего представить наглядно , как на иллюстрации 6-12. Три узла со значениями 10, 30 и 50 раскрашены в соответствии с их высотами. Корневой узел, 50, имеет вес h. Серые треугольники — это поддеревья, причём они являются двоичными деревьями поиска, и притом сбалансированными. Левое поддерево узла 10 обозначено 10L, в нём содержатся узлы, значение которых не превосходит 10. Нам достаточно знать, что по построению высота такого дерева равна h - 3. Поскольку все поддеревья на диаграмме (10L, 10R, 30R и 50R) раскрашены одинаково, можно сделать вывод о том, что их высоты тоже равны h-3. The designers of the AVL tree invented the concept of a node rotation, which is best described visually in Figure 6-12. The three nodes—containing the values 10, 30, and 50—are shaded to present their height. The root node, containing 50, has height h. The gray triangles are subtrees whose values conform to the binary search tree prop‐ erty. The left subtree of the node containing 10, for example, is labeled 10L, and it contains values that are all smaller than or equal to 10. All you need to know is that the height of this subtree (and the other three shaded subtrees, 10R, 30R, and 50R) is h – 3.

Я не стал переводить номенклатуру 10L/10R в 10Л/10П, потому что Л и П визуально иногда не отличаются, зависит от шрифта. -- FrBrGeorge 2022-12-04 11:44:06

Тогда всё дерево перевешивает влево: высота левого поддерева — h - 1, а правого — h - 3, значит, разница весов равна +2. После того, как в АВЛ-дереве определился дисбаланс, происходит «вращение» узлов, и дерево меняет конфигурацию, как это показано на иллюстрации 6-12. После вращения высота всего дерева оказывается h - 1, а узел 30 становится новым корнем. На иллюстрации представлено правое вращение дерева. Если представить себе дерево в виде сцепленных подвесок с одним кольцом сверху и двумя — снизу, то вращение — это когда вы перестаёте держать всю цепочку за старый корень (50), берётесь за новый (30) и встряхиваете всю конструкцию. При этом новый корень поднимается на верхний уровень, а старый корень оказывается справа и опускается ниже. Ненадолго получится, что у 30 три потомка, но зато у 50 теперь точно осталось только правое поддерево (50R), а 30R отлично может стать его левым поддеревом, потому что его узлы не превосходят 50 и не меньше 30. The tree leans to the left: its left subtree has a height of h – 1, while its right subtree has a smaller height of h – 3, meaning the height difference is +2. An AVL tree reba‐ lances itself by detecting this imbalance and rotating nodes to reconfigure the tree, as shown on the right in Figure 6-12. After the rotation, the resulting binary search tree has a height of h – 1, and the node containing 30 has become the new root. This par‐ ticular rotation is a rotate right, which you can visualize as placing your hand on the original node containing 30 and rotating your hand to the right, which “lifts up” the node containing 30 while “dropping down” the node containing 50.

Иллюстрация 6-12. Как сбалансировать двоичное дерево поиска, вращая его корень вправо

Если взять дерево всего из трёх элементов, получится четыре варианта дисбаланса — как на иллюстрации 6-13. В частности «левый-левый» дисбаланс — это упрощённая версия дерева с иллюстрации 6-12. Чтобы восстановить равновесие, такое дерево достаточно повернуть вправо — так же, как и зеркальное к нему дерево с «правым-правым» дисбалансом нужно с той же целью повернуть влево. Варианты дисбаланса поименованы сообразно тому, как расположены в нём узлы, начиная с корневого. Во всех четырёх случаях мы получаем сбалансированное дерево с корнем 30, левым потомком 10 и правым — 50. There are four possible unbalanced scenarios in a binary search tree containing just three values, as shown in Figure 6-13. Scenario Left-left represents a simplified ver‐ sion of the example in Figure 6-12, which only needs a rotate right to balance the tree; similarly, scenario Right-right represents its mirror image, needing only a rotate left to bring the tree back into balance. These scenarios are named for the relative posi‐ tioning of each descendant node to the root. These rotate operations result in a bal‐ anced tree whose root node contains 30, with a left child containing 10 and a right child containing 50.

Иллюстрация 6-13. Четыре типа вращения узла

«Левый-правый» дисбаланс чуть сложнее: такое дерево приводится к норме в два шага. Сначала надо повернуть влево левое поддерево с корнем 10, при этом узел 10 опустится на уровень, а узел 30 — поднимется. Всё дерево при этом приобретает уже знакомый нам «левый-левый» дисбаланс, и теперь его достаточно повернуть вправо — равновесие восстановится. Назовём такую двухступенчатую операцию «лево-правым поворотом». Дерево с «право-левым» дисбалансом зеркально воспроизводит эту ситуацию, и для восстановления равновесия его нужно «повернуть вправо-лево». В репозитории примеров к нашей книге есть оптимизированные версии всех этих операций. Scenario Left-right presents a more complicated unbalanced tree that can be reba‐ lanced in two steps. First, rotate left the left subtree rooted at 10, which “drops down” the 10 node and “lifts up” the 30 node, resulting in a tree that matches scenario Left- left. Second, perform a rotate right to balance the tree. This two-step composite oper‐ ation is called rotate left-right. Scenario Right-left represents the mirror image of scenario Left-right, resulting in a rotate right-left operation that rebalances the tree. The repository contains an optimized implementation for these composite operations.

В примере 6-11 приведены функции, которые используют готовые операции поворота и восстанавливают равновесие, когда дерево перевешивает влево или вправо⁷. Two new helper functions resolve situations when a node is unbalanced to the left (or to the right), as shown in Listing 6-11.

   1   def resolve_left_leaning(node):
   2     if node.height_difference() == 2:           # 1
   3       if node.left.height_difference() >= 0:    # 2
   4         node = rotate_right(node)
   5       else:
   6         node = rotate_left_right(node)          # 3
   7     return node                                 # 7
   8 
   9   def resolve_right_leaning(node):
  10     if node.height_difference() == -2:          # 4
  11       if node.right.height_difference() <= 0:   # 5
  12         node = rotate_left(node)
  13       else:
  14         node = rotate_right_left(node)          # 6
  15     return node                                 # 7

• Пример 6-11. Вспомогательные функции, которые выбирают подходящие операции поворота Listing 6-11. Helper functions that choose appropriate rotation strategy

1. Узел перевешивает влево с разницей +2. A node leans to the left when height difference is +2.

2. Если левое поддерево не перевешивает вправо, можно просто повернуть узел влево (вызвать rotate_right()). Detects the rotate_right case by confirming that node’s left subtree is partially leaning left.

3. В противном случае левое поддерево перевешивает вправо, и нужно поворачивать узел «влево-право» (вызывать rotate_left_right()). Otherwise, node’s left subtree is partially leaning right, meaning a rotate_left_right is in order.

4. Узел перевешивает вправо с разницей –2. A node leans to the right when height difference is –2.

5. Если правое поддерево не перевешивает влево, можно просто повернуть узел вправо (вызвать rotate_left()). Detects the rotate_left case by confirming that node’s right subtree is partially leaning right.

6. В противном случае правое поддерево перевешивает влево, и нужно поворачивать узел «вправо-лево» (вызывать rotate_right_left()). Otherwise, node’s right subtree is partially leaning left, meaning a rotate_right_left is in order.

7. Возвращаем узел (если он был разбалансирован, то мы вернули ему равновесие). Be sure to remember to return node of (potentially rebalanced) subtree.

Идея в том, чтобы сразу ликвидировать дисбаланс, как только в процессе работы с деревом он проявился. В последний раз дополним метод ._insert() — как показано в примере 6-12 — в котором для этого сразу вызываются наши вспомогательные функции. Если добавлять значение в левое поддерево, сам узел не может перевесить вправо, так что достаточно исправить перевес влево, если он появился. Аналогично, если добавлять элемент в правое поддерево, сам узел не перевесит влево. The strategy is to immediately resolve an unbalanced node once this situation has been detected. The final implementation of _insert() is shown in Listing 6-12, which takes immediate advantage of these resolution helper functions. Adding a value to a left subtree of a node can never make that node right-leaning; similarly, adding a value to a right subtree of a node can never make that node left-leaning.

   1   def _insert(self, node, val):
   2     if node is None:
   3       return BinaryNode(val)
   4 
   5       if val <= node.value:
   6         node.left = self._insert(node.left, val)
   7         node = resolve_left_leaning(node)               # 1
   8       else:
   9         node.right = self._insert(node.right, val)
  10         node = resolve_right_leaning(node)              # 2
  11 
  12       node.compute_height()
  13       return node

• Пример 6-12. Если узел не сбалансирован, сразу повернём его Listing 6-12. Rotating nodes when an unbalanced node is detected

1. Левое поддерево может перевешивать — это надо исправить! If left subtree is now left-leaning, resolve it.

2. Правое поддерево может перевешивать — это тоже надо исправить! If right subtree is now right-leaning, resolve it.

Текст функций поворота можно найти в репозитории к нашей книге. В таблице 6-4 показано, как по мере выполнения функции rotate_left_right() меняется балансируемое дерево. Начинается всё с определения new_root и остальных затронутых дисбалансом узлов, а заканчивается сбалансированным деревом; нелишне заметить, что высоты child и node в нём пересчитаны заново. The implementations for these rotation functions can be found in the code reposi‐ tory. Table 6-4 describes the rotate_left_right case, showing the code and the rebalanced tree. At the top, the new_root and the other affected nodes and subtrees are identified. Below, the tree is rebalanced, and, importantly, new heights are compu‐ ted for child and node.

Обратим внимание на то, что rotate_left_right() возвращает корень нового сбалансированного дерева: если мы восстанавливаем равновесие некоторого узла в составе большего дерева, нам понадобится старый корень поддерева поменять на новый. При этом пересчитывать высоту new_root не надо — это уже сделано в ._insert() или ._remove(). По последней диаграмме видно, что полученное двоичное дерево — это дерево поиска: например, все значения в 30L не меньше 10 и не больше 30, так что это поддерево вполне может быть правым для узла 10. Точно так же 30R может быть левым поддеревом узла 50. Pay attention to how rotate_left_right() returns the new root node for the bal‐ anced binary tree, since this unbalanced node could exist within a larger binary tree. There is no need to recompute the height of new_root since the calling function—in _insert() or _remove()—will do that. You can confirm visually that the resulting binary tree still conforms to the binary search tree property: for example, all of the values in 30L are greater than or equal to 10 and less than or equal to 30, so this sub‐ tree can be a right subtree of the node containing 10. A similar argument explains why the subtree labeled 30R can be a left subtree to the node containing 50.

   1 def rotate_left_right(node):
   2     child = node.left
   3     new_root = child.right
   4     grand1 = new_root.left
   5     grand2 = new_root.right

   1     child.right = grand1
   2     node.left = grand2
   3     new_root.left = child
   4     new_root.right = node
   5     child.compute_height()
   6     node.compute_height()
   7     return new_root

• Таблица 6-4. Реализация лево-правого вращения Table 6-4. Implementation of rotate left-right

Дополненный метод ._insert() теперь при необходимости восстанавливает баланс двоичного дерева поиска. Доделать ._insert() и ._remove_min() с помощью наших вспомогательных функции тоже довольно просто — это сделано в примере 6-13. В тексте метода отслеживаются все четыре случая, когда меняется структура дерева и требуется вмешательство. The revised _insert() method now rebalances the binary search tree as needed. A similar change to _remove() and _remove_min() is straightforward with these helper functions, as shown in Listing 6-13. The code is modified to include four targeted interventions whenever the tree’s structure is changed.

   1   def _remove_min(self, node):
   2     if node.left is None: return node.right
   3 
   4       node.left = self._remove_min(node.left)
   5       node = resolve_right_leaning(node)                   # 1
   6       node.compute_height()
   7       return node
   8 
   9   def _remove(self, node, val):
  10     if node is None: return None
  11 
  12       if val < node.value:
  13         node.left = self._remove(node.left, val)
  14         node = resolve_right_leaning(node)                 # 2
  15       elif val > node.value:
  16         node.right = self._remove(node.right, val)
  17         node = resolve_left_leaning(node)                  # 3
  18       else:
  19         if node.left is None: return node.right
  20         if node.right is None: return node.left
  21 
  22           original = node
  23           node = node.right
  24           while node.left:
  25             node = node.left
  26 
  27           node.right = self._remove_min(original.right)
  28           node.left = original.left
  29           node = resolve_left_leaning(node)                # 4
  30 
  31       node.compute_height()
  32       return node

• Пример 6-13. Улучшенный метод ._remove() восстанавливает свойства АВЛ-дерева Listing 6-13. Updating _remove() to maintain AVL property

1. Если мы удаляем наименьший элемент, это по договорённости происходит в левом поддереве. При этом узел может перевесить вправо — тогда для восстановления баланса понадобится его повернуть. Removing the minimum value from a subtree rooted at node.left could make node right-leaning; rotate to rebalance as needed.

2. Если мы удаляем элемент из левого поддерева, узел может перевесить вправо, понадобится восстановление баланса и поворот. Removing a value from the left subtree of node could make node right-leaning; rotate to rebalance as needed.

3. Если мы удаляем элемент из правого поддерева, узел может перевесить влево, понадобится восстановление баланса и поворот. Removing a value from the right subtree of node could make node left-leaning; rotate to rebalance as needed.

4. Если мы нашли узел с нужным значением и удалили в правом поддереве минимальный узел, наш узел может перевесить влево, понадобится восстановление баланса и поворот. After the minimum has been removed from the subtree returned to be node.right, node could be left-leaning; rotate to rebalance as needed.

После того, как мы добавили в BinaryTree поддержку свойств АВЛ-дерева, каждое добавление или удаление элемента приводит к балансировке всей структуры. Балансировка выполняет всегда одинаковое количество действий, так что оценка времени её работы должна быть константой — O(1). Методы поиска и обхода менять не нужно, потому что АВЛ-дерево продолжает оставаться двоичным деревом поиска. The AVL implementation now properly rebalances whenever a new value is inserted into the tree or a value is removed. Each rebalancing contains a fixed number of oper‐ ations and executes in O(1) constant time. Because an AVL tree is still a binary search tree, the search and traversal functions do not need to change.

Производительность сбалансированных деревьев

Analyzing Performance of Self-Balancing Trees

И вспомогательный метод .compute_height(), и все процедуры поворота работают константное время — ни в одной из них них нет ни рекурсивного вызова, ни циклов. Все три метода вызываются только когда обнаружился дисбаланс. Если внимательно посмотреть, как элемент добавляется в АВЛ-дерево, обнаружится, что на это потребуется не более одного поворота. Удаление элемента посложнее: теоретически возможен наихудший случай, когда поворотов потребуется несколько (одно из тренировочных заданий посвящено разбору этой ситуации). Но даже в наихудшем случае поворотов будет не больше log₂ N, так что общее быстродействие операций поиска, добавления и удаления элементов можно оценить как O(log N). The compute_height() helper function and the different node rotation methods all perform in a constant amount of time—there are no further recursive calls or loops in any of these functions. These tree maintenance functions are invoked only when a node is detected to be unbalanced. It turns out that when inserting a value into an AVL tree, there will never be more than one node rotation required. When removing a value, it is theoretically possible there will be multiple node rotations (see the chal‐ lenge exercise at the end of this chapter that investigates this behavior). In the worst case, there will never be more log (N) rotations, which means that the runtime per‐ formance for search, insert, and remove are all O(log N).

Потренировавшись в этой главе на деревьях, мы можем начать исследовать любую рекурсивную структуру данных. А сейчас давайте сравним работу уже известных нам структур — хеш-таблиц и приоритетных очередей — с работой двоичных деревьев: не окажутся ли они эффективнее? Using the information from this chapter, you are now prepared to further investigate any recursive data structures. To close this chapter, I now reconsider the symbol table and priority queue data types to consider whether a binary tree can provide a more efficient implementation.

Хранение пар (ключ, значение) в двоичном дереве

Using Binary Tree as (key, value) Symbol Table

Структура двоичного дерева поиска позволяет без качественных изменений хранить в нём соответствующие ключу произвольные значения — то есть реализовать абстракцию «ассоциативный массив», которую мы уже наблюдали в хеш-таблицах. The same binary search tree structure can be used to implement the symbol table data type introduced in Chapter 3, as shown in Figure 6-14.

Иллюстрация 6-14. Двоичное дерево поиска как ассоциативный массив: ключ — атомный вес химического элемента

Чтобы реализовать структуру, изображённую на иллюстрации 6-14, необходимо доработать класс BinaryNode — в нём, помимо ключа, должно храниться значение. Пример 6-14 содержит такую доработку. To do this, you have to modify the BinaryNode structure to store both key and value, as shown in Listing 6-14.

   1 class BinaryNode:
   2   def __init__(self, k, v):
   3     self.key = k                # 1
   4     self.value = v              # 2
   5     self.left = None
   6     self.right = None
   7     self.height = 0

• Пример 6-14. Класс BinaryNode, дополненный полем «значение»: теперь двоичное дерево может быть использовано как ассоциативный массив Listing 6-14. Updated BinaryNode when using binary tree to store symbol table

1. Ключ используется для поиска по дереву. The key is used to navigate the binary search tree.

2. Значение может содержать любые данные: они никак не используются при работе с двоичным деревом поиска. The value contains arbitrary data that is irrelevant to the operation of the binary search tree.

Теперь надо методы .insert(ключ) и __contains__(ключ) заменить .put(ключ, значение) и .get(ключ) — тогда BinaryTree станет совместимо с нашей реализацией хеш-таблиц. Изменения минимальны и сводятся только к заполнению и возврату поля .value, так что мы их здесь не приводим. Полный текст всех примеров можно посмотреть в репозитории к данной книге (https://oreil.ly/fUosk). Обход дерева, то есть выбор между левым и правым поддеревьями, как и прежде, происходит на основании значения node.key. BinaryTree now needs put(k,v) and get(k) functions, instead of insert() and contains(), to support the expected interface for a symbol table. The changes are minimal, and only incidental changes are required, so the code is not reproduced here; find it in the associated code repository (https://oreil.ly/fUosk). When navigating through the binary search tree, that is, whether to go left or right, the decision is based on node.key.

Чем двоичное дерево несомненно лучше хеш-таблицы: значения из него можно извлекать в порядке возрастания ключей, потому что так работает метод прохода дерева .__iter__(). Using a binary search tree provides the added benefit that the keys can be retrieved from the symbol table in ascending order using the iter() traversal function.

Вспомним, что в главе 3 мы рассматривали хеш-таблицы с открытой адресацией и с раздельным хранением цепочек. Имеет смысл сравнить эффективность двоичного дерева поиска, хранящего значения, и с той, и с другой реализацией хеш-таблиц, которые приведены в таблице 3-4. Для эксперимента мы взяли 321129 слов английского словаря и добавили каждое во все три структуры данных. Какова минимальная высота дерева, в котором помещается 321129 слов? Мы помним, что она равна log(N + 1) - 1, что даёт 17.293. И действительно, если все эти слова добавить в АВЛ-дерево в порядке возрастания, его высота окажется равной 18. В очередной раз убеждаемся, что хранить информацию в АВЛ-дереве весьма удобно. Chapter 3 described how open addressing and separate chaining can implement the symbol table data type. It’s worth comparing the runtime performance of a binary search tree against the results of open addressing and separate chaining hashtables, as shown in Table 3-4. This trial inserts N = 321,129 words from the English dictionary into a symbol table. What is the smallest height for a binary tree that stores all of these words? Recall that this height is computed by the formula log(N + 1) – 1, which is 17.293. After inserting all of these words in ascending order from the English dictio‐ nary, the height of the resulting AVL binary search tree is 18, which further demon‐ strates the efficiency of AVL trees in storing information.

Оба варианта хеш-таблиц из главы 3 оказываются гораздо производительнее двоичного дерева поиска⁸, как это видно из таблицы 6-5. Даже если понадобится отсортированный список ключей, выгоднее получить его как есть из хеш-таблицы, а затем отсортировать. The hashtable implementations from Chapter 3 significantly outperform binary search trees, as shown in Table 6-5. If you ever need the keys for a symbol table in ascending order, then I recommend retrieving the keys from the symbol table and then sorting them separately.

• Таблица 6-5. Сравнение АВЛ-дерева и хеш-таблиц из главы 3 в качестве ассоциативных массивов (время в секундах) Table 6-5. Comparing AVL symbol table implementation with hashtables from Chapter 3 (time in seconds)

Двоичное дерево как приоритетная очередь

Using the Binary Tree as a Priority Queue

Поскольку двоичная куча, описанная в четвёртой глава, очевидно основывается на двоичном дереве, было бы совершенно естественным сравнить производительность приоритетной очереди и аналогичной структуры на базе АВЛ-дерева, в которой ключом для обхода дерева является приоритет — как это изображено на иллюстрации 6-15. Given that the heap data structure described in Chapter 4 is based on a binary tree structure, it is only natural to compare the runtime performance of a priority queue implemented using an AVL binary search tree where the priority is used to navigate the structure of the binary search tree, as shown in Figure 6-15.

Иллюстрация 6-15. Двоичное дерево поиска как приоритетная очередь: приоритет — это атомный вес химического элемента

Двоичное дерево поиска в качестве приоритетной очереди имеет два достоинства: There are two benefits to using a binary search tree to implement a priority queue:

• Куча, основанная на массиве определённого размера, способна хранить только фиксированное количество элементов. Двоичное дерево может расти как нам заблагорассудится⁹. • An array-based heap must create storage for a fixed number of values in advance. Using a binary search tree, the structure can grow to be as large as needed.

• Поскольку в куче нет строгого порядка, а есть только частичный, итератор по элементам кучи в порядке возрастания приоритетов — это либо последовательное снятие элементов, либо имитация такого процесса. Так или иначе это требует отдельных ресурсов, см. соответствующее тренировочное задание в конце этой главы. В двоичном дереве порядок гарантируется процедурой обхода. • In the heap structure, there is no way to provide an iterator of the entries in the priority queue in priority order without dequeuing the values.5 With a binary search tree structure, this capability now exists using the traversal logic.

Для начала, как это сделано в примере 6-15, добавим в BinaryNode поля .value и .priority: первое поле, значение, как обычно ни на что не влияет, а второе, приоритет, — это ключ для обхода дерева и операций добавления и удаления элемента. To get started, BinaryNode now stores both value and priority, as shown in Listing 6-15. The priority field will be used to navigate the binary tree for the search, insert, and remove operations.

   1 class BinaryNode:
   2   def __init__(self, v, p):
   3     self.value = v              # 1
   4     self.priority = p           # 2
   5     self.left = None
   6     self.right = None
   7     self.height = 0

• Пример 6-15. Класс BinaryNode, дополненный полем «значение»: теперь двоичное дерево можно использовать как приоритетную очередь, в которой поле «приоритет» задаёт порядок Listing 6-15. Updated BinaryNode when using binary tree to store priority queue

1. Значение может содержать любые данные: они никак не используются при работе с двоичным деревом поиска. The value contains arbitrary data that is irrelevant to the operation of the binary search tree.

2. Приоритет используется для поиска по дереву. The priority is used to navigate the binary search tree.

Мы помним, что в двоичной куче с порядком убывания элемент с наивысшим приоритетом всегда находится в storage[1], и поэтому доступен за время O(1). Если использовать двоичное дерево поиска, будет по-другому: узел с наивысшим приоритетом — самый правый в дереве. Если дерево сбалансировано (например, как сделано в этой главе), на поиск такого узла потребуется O(log N) времени. In a max binary heap, the entry with highest priority is in storage[1], and it can be located in O(1) constant time. This is not the case when using a binary search tree to store a priority queue. The BinaryNode with highest priority is the right‐ most node in the binary tree. To locate this value requires O(log N) runtime per‐ formance, if the underlying binary tree is balanced using the techniques described in this chapter.

Однако главное отличие приоритетной очереди от дерева — в том, что произвольный элемент очереди удалять не приходится никогда: удаляется только элемент с наивысшим приоритетом. Стало быть, и общий метод .remove() не нужен, а вместо него, как это сделано в примере 6-16, добавим в класс PQ вспомогательный метод ._remove_max(). Остальные вспомогательный методы — те же, что у стандартного класса, реализующего приоритетную очередь. Заметим, что класс PQ хранит и отслеживает количество пар в куче, N. The biggest change, however, is that when a priority queue uses a binary search tree for storage, the only value to remove is the one with highest priority; this means the general purpose remove() function is not needed. In its place, a _remove_max() helper function is added to PQ, as shown in Listing 6-16. The other helper functions are part of the standard priority queue interface. Note that the count, N, of pairs is stored and managed by the PQ class.

5 See challenge exercise at end of this chapter showing how to do this.

   1 class PQ:
   2   def __init__(self):
   3     self.tree = BinaryTree()                            # 1
   4     self.N = 0
   5 
   6   def __len__(self):
   7     return self.N
   8 
   9   def is_empty(self):
  10     return self.N == 0
  11 
  12   def is_full(self):
  13     return False
  14 
  15   def enqueue(self, v, p):
  16     self.tree.insert(v, p)                              # 2
  17     self.N += 1
  18 
  19   def _remove_max(self, node):                          # 3
  20     if node.right is None:
  21       return (node.value, node.left)                    # 4
  22 
  23     (value, node.right) = self._remove_max(node.right)  # 5
  24     node = resolve_left_leaning(node)                   # 6
  25     node.compute_height()                               # 7
  26     return (value, node)
  27 
  28   def dequeue(self):                                    # 8
  29     (value, self.tree.root) = self._remove_max(self.tree.root)
  30     self.N -= 1
  31     return value                                        # 9

• Пример 6-16. Класс PQ моделирует двоичную кучу при помощи BinaryTree и методов .enqueue() и .dequeue() Listing 6-16. PQ class provides enqueue() and dequeue() functions

1. В качестве хранилища используем сбалансированное двоичное дерево поиска. Use a balanced binary search tree for storage.

2. Поставим в очередь пару (ключ, значение) — добавим её в дерево и увеличим счётчик N. To enqueue a (v, p) pair, insert that pair into the binary search tree and increment N count.

3. Вспомогательный метод ._remove_max() во-первых, удаляет узел с наивысшим приоритетом из дерева с корнем node, а во-вторых — возвращает кортеж вида (значение, дерево). Значение берётся из удалённого узла, а дерево — это поддерево, получившееся после удаления. The _remove_max() helper method both removes the node with maximum prior‐ ity from the subtree rooted at node and returns its value and the node of the resulting subtree as a tuple.

4. Основание рекурсии: правое поддерево пусто, значит, мы нашли узел с наивысшим приоритетом. Возвращаем его значение и его левое поддерево (оно займёт место найденного узла). Base case: with no right subtree, this node has maximum priority; return both the value in the node being deleted and the left subtree that will eventually take its place.

5. Рекурсивный вызов: получаем значение удалённого узла и поддерево, образовавшееся после удаления. Recursive case: retrieve removed value and root of updated subtree.

6. Если узел потерял баланс, восстановим его с помощью поворотов. If node is out of balance (it could now lean left), fix with rotations.

7. Вычислим новую высоту узла и возвратим её вместо с удалённым значением. Compute node height before returning it along with value that was removed.

8. Метод .dequeue() удаляет узел с наивысшим приоритетом из двоичного дерева поиска и возвращает значение этого узла. The dequeue() method removes node with maximum priority from the binary search tree and returns its value.

9. Уменьшим счётчик, N, и возвратим значение, соответствующее наивысшему приоритету. After decrementing count, N, return the value that had been associated with highest priority.

The runtime performance of this priority queue implementation still offers O(log N) behavior, although in absolute terms it is twice as slow as the heap-based priority queue implementation from Chapter 4. The reason is that maintaining the AVL binary search tree structure is more work than actually needed for a priority queue. Still, if you need the ability to iterate over its (value, priority) pairs in the order in which they would be removed, this is an efficient alternative. У нас получилась приоритетная очередь, быстродействие которой в два раза ниже, чем у аналогичной структуры поверх двоичной кучи (из главы 4) — но порядок сложности остался O(log N), то есть отличие только в мультипликативной постоянной. Операции с АВЛ-деревом требуют больше действий, чем операции с кучей, но если, например, требуется регулярный обход пар (значение, приоритет) в порядке удаления, удобно использовать этот новый вариант.

Заключение

Summary

Binary trees are a dynamic, recursive data structure that organizes its values into left and right substructures, offering the potential to evenly subdivide a collection of N values into two structures, each containing (more or less) N/2 values. Binary trees form the basis for countless other recursive data structures that lead to efficient implementations, including: Двоичное дерево — это динамическая рекурсивная структура данных, в которой набор из N значений делится на левое и правое поддерево, в каждом из которых содержится примерно половина всех элементов. Великое множество более сложных и эффективных структур данных основано на двоичных деревьях, например:

• Красно-чёрные деревья, в которых используется более эффективный, но и существенно более сложный алгоритм балансировки, чем в АВЛ-деревьях. • Red-black trees, which offer a more efficient approach for balancing binary search trees, although the implementation is more complicated than with AVL trees.

• Сбалансированные сильно ветвистые Би-деревья и Би+-деревья(обычно используются в базах данных и файловых системах). • B-trees and B+ trees, used for databases and file systems.

• R-деревья и R*-деревья, ориентированные на хранение координатной информации (и включающие в себя понятия дистанции, достижимости и т. п.). • R-trees and R∗ trees, used for spatial information processing.

• K-мерные деревья (в частности, деревья квадрантов и октодеревья), используемые для храненния и поиска информации в многомерных пространствах. • k-d trees, Quadtrees, and Octrees for space-partitioning structures.

По итогам этой главы:

• Деревья имеют рекурсивную природлу, что что и функции для работы с ними часто бывают рекурсивными. • Because trees are recursive data structures, it is natural to write recursive func‐ tions to manipulate their structure.

• Наиболее популярен центрированный (LNR, left-node-right) обход двоичного дерева, позволяющий получить элементы в порядке возрастания значений. В примере со структурой Expression мы использовали обратный (LRN, left-right-node) обход, позволяющий представить дерево в виде выражения в постфиксной записи — как для большинства микрокалькуляторов¹⁰. • The most common technique for traversing a binary search tree is inorder traver‐ sal, which returns all values in ascending order. The Expression recursive struc‐ ture includes a postorder traversal function that produces the values in postfix order, which conforms to the postfix notation, which is used by some handheld calculators.

• Двоичным деревьям поиска необходима постоянная балансировка — иначе пострадает заявленное быстродействие основных операций, O(log N). В АВЛ-деревьях балансировка обеспечена дополнительным полем — высотой поддерева — и тем, что любое действие должно сохранять базовое свойство: высота правого и левого поддеревьев не должна отличаться более, чем на единицу. • Binary search trees must rebalance their structure to ensure they can achieve O(log N) runtime performance for its key operations. The AVL technique is able to balance a tree by enforcing the AVL property, that the height difference of any node is –1, 0, or 1. To make this work efficiently, each binary node also stores its height in the tree.

• Сбалансированное двоичное дерево поиска можно превратить в приоритетную очередь, хранящую пары (значение, приоритет), в которой сравнение узлов — это сравнение их приоритетов. Быстродействие такой структуры значимо не пострадает, а вдобавок можно будет центрировано, то есть в порядке возрастания, обходить весь набор данных без изменения самой очереди. • A priority queue can be implemented using a balanced binary search tree to store the (value, priority) pairs, using priority when comparing nodes. One benefit of this structure is you can use inorder traversal to return the pairs stored by the priority queue in priority order, without affecting the structure of the priority queue.

• С помощью двоичного дерева можно смоделировать и хеш-таблицу, если соблюдать уникальность ключа, по которому производится поиск. Впрочем, быстродействие такой модели оказывается хуже бустродействия жеш-таблицы в её классической реализации, описанной в главе 3. • A symbol table can be implemented using a balanced binary search tree by enforcing the restriction that each key is unique in the binary search tree. How‐ ever, the performance will not be as efficient as the hashtable implementations described in Chapter 3.

Тренировочные задания

Challenge Exercises

1. Write a recursive count(n, target) function that returns the number of times that target exists within the linked list whose first node is n.

1. Напишите рекурсивный метод BinaryNode.count(n), который подсчитывает количество элементов двоичного дерева с вершиной в данном узле, кратных n.

2. Нарисуйте двоичное дерево поиска, в котором для нахождения двух наибольших значений среди N элементов понадобится O(N) действий. А теперь нарисуйте двоичное дерево поиска, в котором для нахождения двух наибольших значений среди N элементов понадобится O(1) действий. 2. Sketch the structure of a binary search tree with N nodes that requires O(N) time to find the two largest values. Next, sketch the structure of a binary search tree with N nodes that requires O(1) time to find the two largest values.

3. Когда возникает необходимость найти k-й по величине элемент в дереве, можно просто обойти k узлов, но такой способ неэффективен. Добавьте в класс BinaryTree метод .select(k), который будет возвращать k-е наименьшее значение в дереве, где k выбирается из диапазона от 0 до N-1. Для этого добавьте в класс BinaryNode дополнительное поле N, в котором будет хранится общее количество значений в поддереве с корнем в данном узле (включая значение самого узла). Например, в каждом листовом узле N будет равно 1. 3. What if you wanted to find the kth smallest key in a binary search tree? An ineffi‐ cient approach would be to traverse the entire tree until k nodes have been vis‐ ited. Instead, add a function, select(k), to BinaryTree that returns the kth smallest key for k from 0 to N – 1. For an efficient implementation, you will need to augment the BinaryNode class to store an additional field, N, that records the number of nodes in the subtree rooted at that node (including that node itself). A leaf has an N value of 1, for example. Also add the companion method, rank(key), to BinaryTree that returns an inte‐ ger from 0 to N – 1 that reflects the rank of key in sorted order (or in other words, the number of keys in the tree strictly less-than key).

   Добавьте ещё один метод, .rank(key), который будет возвращать число от 0 до N-1, — позицию ключа в упорядоченном списке элементов. Иными словами, требуется подсчитать количество ключей в дереве, строго меньших заданного.

4. Значения из списка [3,14,15,19,26,53,58] можно организовать в виде двоичного дерева поиска 7! = 5040 различными способами. Подсчитайте, сколько из таких деревьев будут строго сбалансированными с высотой 2, как на иллюстрации 6-3. Можно ли обобщить ответ и вывести рекуррентное соотношение для c(k), которое для произвольного k давало бы количество различных строго сбалансированных деревьев из 2^k-1 значений? 4. Given the values [3,14,15,19,26,53,58], there are 7! = 5,040 ways to insert these seven values into an empty binary search tree. Compute the number of dif‐ ferent ways that the resulting tree is perfectly balanced, with a height of 2, such as the binary search tree shown in Figure 6-3. Can you generalize your result to an arbitrary collection of 2k-1 values and present a recursive formula c(k) that computes this for any k?

5. Добавьте в BinaryTree метод .__contains__(), который вызывал бы метод .__contains__() из BinaryNode. 5. Write a contains(val) method for BinaryTree that invokes a recursive contains(val) method in BinaryNode.

6. АВЛ-деревья, как мы это узнали в этой главе, сбалансированы, но не обязательно столь же компактны, как полное двоичное дерево. Какова наибольшая возможная высота АВЛ-дерева из N элементов? Сконструируйте 10000 случайных АВЛ-деревьев из N элементов и зафиксируйте наибольшую высоту, которой удалось достичь при каждом N. Составьте таблицу, по которой можно будет отследить, когда наибольшая высота увеличивается. Попробуйте предсказать такие N, для которых наибольшая высота АВЛ дерева из N элементов на единицу больше высоты АВЛ-дерева из N-1 элемента. 6. As described in this chapter, AVL trees are self-balancing. For a given N, can you compute the maximum height of an AVL tree containing N values, since they cannot all be so perfectly compact as a complete binary tree? Generate 10,000 random AVL trees of size N, and record the maximum observed height for each N. Create a table that records whenever this maximum observed height increases. Predict the values of N such that an AVL tree of N nodes can have a tree height that is one greater than any AVL tree with N – 1 nodes.

7. Допишите класс SpeakingBinaryTree из примера 6-17, который отчитывается о производимых с ним действиях при выполнении метода .insert(значение) примерно так, как это сделано в таблице 6-2. Данная рекурсивная процедура отличается от других, изучаемых нами в этой главе: отчёт формируется «от начала», в то время как большинство рекурсивных процедур работают «от конца», то есть от основания рекурсии. 7. Complete the SpeakingBinaryTree in Listing 6-17 whose insert(val) operation produces English descriptions of the actions as they are performed. Table 6-2 contains the desired output for each of the corresponding operations. This recur‐ sive operation is different from others in this chapter because it processes “top- down,” whereas most recursive functions process “bottom-up” from base cases.

      1       class BinaryNode:
      2         def __init__(self, val):
      3           self.value = val
      4           self.left = None
      5           self.right = None
      6 
      7       class SpeakingBinaryTree:
      8         def __init__(self):
      9           self.root = None
     10 
     11           def insert(self, val):
     12             (self.root,explanation) = self._insert(self.root, val,
     13                  'To insert `{}`, '.format(val))
     14             return explanation
     15 
     16           def _insert(self, node, val, sofar):
     17             """
     18             Return (node, explanation) resulting from inserting val into subtree
     19             rooted at node.
     20             """
   

   • Пример 6-17. Допишите метод _insert() так, чтобы он возвращал описание того, что делает Listing 6-17. Enhance the _insert() method to return description of what happened

   Измените стандартный метод ._insert() так, чтобы она возвращал кортеж (узел, описание), где узел — это корень дерева после вставки, а описание — это строка, в которую с каждым рекурсивным вызовом добавляется описание выполняемого действия. Modify the _insert() function to return a tuple (node, explanation), where node is the resulting node and explanation contains the growing explanation for the actions.

8. Напишите функцию check_avl_property(n), которая проверяет, что в дереве с корнем в n, во-первых, все поддеревья имеют правильно подсчитанную высоту, и во-вторых, все узлы соответствуют требованию для разности высот АВЛ-дерева. 8. Write a method check_avl_property(n) that validates the subtree rooted at n to ensure that (a) that each descendant node’s computed height is correct, and (b) that each descendant node satisfies the AVL tree property.

9. Напишите функцию tree_structure(n), которая конструирует строку, отражающую прямой обход дерева с корнем в n. Каждое поддерево должно быть заключено в скобки. Прямой обход (NLR, node-left-right) предусматривает, что сначала выводится значение самого узла, затем — левое поддерево, а затем — правое. Например, полное двоичное дерево с иллюстрации 6-3 должно выглядеть так: '(19,(14,(3,,),(15,,)),(53,(26,,),(58,,)))', а дерево из левой части иллюстрации 6-5 — так: '(5,(4,(2,(1,,),(3,,)),),(6,,(7,,)))'. 9. Write a tree_structure(n) function that produces a string with parentheses in prefix order to capture the structure of the binary tree rooted at n. In prefix order, the value for the node is printed first, before the left representation and right rep‐ resentation. This string should use commas and parentheses to separate informa‐ tion, so it can be parsed later. For the complete binary tree in Figure 6-3, the resulting string should be '(19,(14,(3_),(15)),(53,(26_),(58)))', while for the binary tree in the left side of Figure 6-5, the resulting string should be '(5,(4,(2,(1_),(3)),),(6₍₇)))'. Write the companion recreate_tree(expr) function that takes in an expr tree structure string using parentheses and returns the root node of a binary tree. Напишите парную функцию recreate_tree(выражение), которой на вход передаётся выражение, представляющее структуру в формате tree_structure(n). Возвращать эта функция должна корень реконструированного двоичного дерева.

10. Если считать лево-правый и право-левый поворот АВЛ-дерева такими же атомарными операциями, как левый и правый поворот, добавление элемента в дерево требует не более одной такой операции. Однако удаление элемента из АВЛ-дерева может потребовать более одной операции поворота. 10. If you count rotate left-right and rotate right-left as single rotations (in addition to rotate left and rotate right), then you will never need more than a single rotation when inserting a value into an AVL binary search tree. However, when removing a value from an AVL tree, you might need multiple rotations.

11. Каков наименьший размер АВЛ-дерева, при удалении элемента из которого может потребоваться более одного поворота? В таком дереве, очевидно, должно быть не менее четырёх узлов. Чтобы ответить на этот вопрос экспериментально, модифицируйте методы поворота так, чтобы для каждого удаления вычислялось количество проделанных поворотов. Кроме того, потребуется tree_structure() из предыдущего упражнения — чтобы можно было восстановить дерево после того, как оказалось, что удаление потребовало более одного поворота. Напишите функцию, которая конструирует 10000 случайных АВЛ-деревьев, содержащих от 4 до 40 узлов, и в каждом таком дереве удаляет случайный элемент. Должны обнаружить АВЛ-деревья, для удаления элемента из которых требуется минимум три поворота. В частности, один поворот может потребоваться для дерева уже из 4 элементов, а два — для дерева из 12 элементов. Каков наименьший размер АВЛ-дерева, при удалении элемента из которого может потребоваться три поворота? What is the smallest AVL binary search tree that requires multiple node rotations when a single value is removed? Such a tree would have to have at least four nodes. To answer this question, you will have to instrument the rotation methods to increase a count for the number of times a rotation is used. Also, use the results of tree_structure() in the previous exercise to record the tree so you can recover its structure after you have detected the multiple rotations. Write a function that (a) generates 10,000 random AVL trees containing between 4 and 40 nodes, and (b) for each of these trees, select one of its random values to remove. You should be able to compute the size of the AVL trees that require up to three rotations for a remove request. As a hint, you should be able to generate an AVL tree with 4 nodes that requires 1 rotation for a given remove request, and an AVL tree with 12 nodes that requires 2 rotations for a given remove request. What is the smallest AVL tree that you can find which requires 3 rotations for a given remove request?

12. Наиболее компактное двоичное дерево, хранящее N = 2^k-1 узел — полное, его высота равна k. А каково «наименее компактное» возможное АВЛ-дерево? Так называемые Фибоначчиевы деревья — это такие АВЛ-деревья, у которых в каждом узле высота левого поддерева больше высоты правого (всего на единицу, ибо больше нельзя). Заметим, что после добавления любого элемента в такое дерево потребуется балансировка. Напишите рекурсивную функцию, fibonacci_avl(N), которая для любого N > 0 возвращала бы объект типа BinaryNode — корень Фибоначчиева дерева из N первых натуральных чисел. Вероятно, проще будет не использовать BinaryTree. Корень такого дерева будет содержать N-е число Фибоначчи! Например, fibonacci_avl(6) вернёт корневой узел дерева, показанного на иллюстрации 6-16. /* 11. A complete binary tree with N = 2k – 1 nodes is the most compact representation for storing N nodes. This question asks what is the “least compact” AVL tree you can construct. A Fibonacci tree is an AVL tree such that in every node, the height of its left subtree is bigger (by just 1) than the height of its right subtree. Think of this as an AVL tree that is one insert away from rebalancing. Write a recursive function, fibonacci_avl(N), for N > 0 that returns a BinaryNode representing the root of a Fibonacci tree. It is simpler to do this without involving any Binary Tree objects. The root node returned contains the value FN. For example, fibonacci_avl(6) would return the root node for the binary tree depicted in Figure 6-16.

    Иллюстрация 6-16. Фибоначчивео дерево из двенадцати узлов

    Figure 6-16. A Fibonacci tree with twelve nodes