Двоичные деревья поиска
Сбалансированное двоичное дерево поиска из 1023 ключей находит любой из них самое большее за 10 сравнений; если строить его из отсортированных данных, те же ключи могут потребовать 1023.
Двоичный поиск, встроенный в форму
Двоичный поиск в отсортированном массиве находит ключ примерно за log₂ n проверок, но вставка в отсортированный массив сдвигает значения. Хеш-таблица вставляет быстро, но забывает порядок: она не может легко назвать наименьший ключ или следующий ключ после 40. Двоичное дерево поиска (ДДП, англ. BST) стремится к обоим. Оно состоит из узлов, как связный список, но у каждого узла два указателя, left и right. Верхний узел называется корнем; узел без потомков называется листом.
Одно правило делает дерево деревом поиска: для каждого узла все ключи в его левом поддереве меньше, а все ключи в правом поддереве больше. Чтобы найти ключ, начни с корня и сравнивай. Равно значит найдено. Меньше значит иди влево, больше значит иди вправо. Каждое сравнение отбрасывает целое поддерево, как двоичный поиск отбрасывает половину списка. Поиск 60 в дереве 50, 30, 70, 20, 40, 60, 80 сравнивает с 50, затем с 70, затем с 60: 3 сравнения.
Вставка идёт тем же путём. Иди влево или вправо, пока нужный указатель не окажется пустым, и подвесь туда новый узел. Вставка 45 сравнивает с 50 (влево), 30 (вправо) и 40 (вправо), а у 40 нет правого потомка, поэтому им становится 45. Для удаления узла, который не является листом, нужна ещё одна идея: в конспектах MIT его элемент меняют местами со следующим или предыдущим ключом по порядку и удаляют уже оттуда. Правило счёта в лаборатории: одно сравнение на каждый узел пути.
Перетащи, чтобы повернуть. Колёсико или щипок для масштаба.
Всё решает высота
Сколько сравнений может занять поиск? Не больше одного на уровень, поэтому стоимость зависит от высоты дерева, числа рёбер на самом длинном пути от корня вниз до листа. В конспектах MIT сказано так: операции с деревом выполняются за время O(h). У дерева 50, 30, 70, 20, 40, 60, 80 высота 2, поэтому ни одному поиску не нужно больше 3 сравнений. Идеально сбалансированное дерево из 1023 узлов имеет высоту 9 и требует не больше 10.
Но форма зависит от порядка вставки. Вставь 10, 20, 30, 40, 50, 60, 70 по возрастанию, и каждый ключ окажется больше всех предыдущих, так что каждый новый узел встанет справа от последнего. Дерево превратится в цепочку высотой 6, и поиск 70 потребует 7 сравнений: связный список с лишними указателями. С 1023 отсортированными ключами худший поиск требует 1023 сравнений вместо 10.
Сбалансированные деревья решают это, перестраивая себя после каждой вставки или удаления. Первой такой схемой было АВЛ-дерево Георгия Адельсона-Вельского и Евгения Ландиса 1962 г., его разбирает лекция 7 курса MIT. В каждом узле оно держит высоты двух поддеревьев различающимися не больше чем на 1 и исправляет любое нарушение небольшими местными перестановками, которые называются поворотами. Так высота остаётся O(log n), и поиск, вставка и удаление остаются O(log n), в каком бы порядке ни приходили ключи.
Ключи по порядку даром
ДДП хранит больше, чем просто принадлежность. Посети левое поддерево, затем узел, затем правое поддерево, рекурсивно, и ключи выйдут в отсортированном порядке. Этот обход по порядку (в MIT его называют traversal order) позволяет ДДП отвечать на вопросы «наименьший ключ», «наибольший ключ» и «следующий ключ после 40», то есть выполнять операции порядка из интерфейса Set курса MIT, которые хеш-таблица быстро не умеет.
| Корень и лист | Корень является верхним узлом; у листа нет потомков. |
| Свойство ДДП | В каждом узле ключи левого поддерева меньше, а ключи правого поддерева больше. |
| Высота | Число рёбер на самом длинном пути от корня до листа. Поиск занимает не больше высоты + 1 сравнений. |
| АВЛ-дерево | Сбалансированное ДДП (1962 г.): высоты поддеревьев различаются не больше чем на 1, исправляется поворотами. |
| Обход по порядку | Слева, узел, справа: перечисляет ключи в отсортированном порядке. |
- Какое утверждение является свойством двоичного дерева поиска?
- У каждого узла ровно два потомка
- В каждом узле ключи левого поддерева меньше, а ключи правого поддерева больше
- Ключи хранятся в порядке вставки
- Корень является наименьшим ключом
- Дерево построено из 50, 30, 70, 20, 40, 60, 80. Сколько сравнений занимает поиск 60?
- То же дерево: сколько сравнений занимает поиск отсутствующего 45?
- Вставь 45 в это дерево. Куда оно попадёт?
- Левым потомком 50
- Правым потомком 40
- Левым потомком 60
- Правым потомком 30
- Какова высота дерева 50, 30, 70, 20, 40, 60, 80?
- Вставь 10, 20, 30, 40, 50, 60, 70 в этом порядке. Сколько сравнений занимает поиск 70?
- В идеально сбалансированном ДДП 1023 узла (высота 9). Сколько сравнений самое большее может занять поиск?
- Расставь ключи дерева 50, 30, 70, 20, 40 в порядке, в котором их посещает обход по порядку.
- Кто предложил первую схему сбалансированного дерева и когда?
- Адельсон-Вельский и Ландис, 1962 г.
- Лун, 1953 г.
- Бауэр и Замельзон, 1957 г.
- Кнут, 1998 г.
- На какой вопрос ДДП отвечает быстро, а обычная хеш-таблица нет?
- Хранится ли 40?
- Какой следующий ключ после 40?
- Сколько корзин?
- Чему равно 40 mod 7?
- В ДДП в каждом узле меньшие ключи идут влево, а большие вправо.
- Поиск и вставка идут по одному пути: не больше высоты + 1 сравнений.
- Отсортированные данные дают цепочку (7 ключей, высота 6); сбалансированные деревья вроде АВЛ (1962 г.) держат высоту O(log n).
- Обход по порядку перечисляет ключи в отсортированном порядке.
Источники курса (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
- 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
- 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
- Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262)
- 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
- Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
Проверено: 2026-10-18