В.А. Антонюк, А.П. Иванов - Программирование и информатика (Краткий конспект лекций) (1109543), страница 10
Текст из файла (страница 10)
Желательно было бы построить контейнер, который будет обеспечивать в среднем логарифмическое время всех трёх операций: поиска элемента по значению,вставки нового элемента, удаления указанного элемента.Списки – даже отсортированные по значению – не обеспечат логарифмического временипоиска. Для решения этой задачи используется контейнер, представляющий из себя двоичное дерево (каждый его элемент содержит два указателя – на левое поддерево и на правоеподдерево):struct TreeNode {double val;struct TreeNode *left;struct TreeNode *right;};Как и в случае списков, корень дерева определяется отдельной структурой данных, хранящей указатель на корневой элемент и общее количество элементов в дереве.
Для того,чтобы можно было производить поиск элемента по значению, узлы дерева поддерживаютв определенном порядке, а именно, значения (их еще называют ключами поиска) всех узлов левого поддерева данного узла должны быть меньше, а значениях всех узлов правогоподдерева – больше значения, хранимого в данном узле.10524180712942176Рис.
18: Двоичное дерево поискаУзлы, не содержащие потомков, называют листьями дерева. Отсутствующий потомокмаркируется нулевым (NULL) указателем в родительском узле. Здесь приводится двоичноедерево, которое хранит уникальные, не повторяющиеся ключи, однако, его несложно обобщить и на случай повторяющихся ключей, например, можно считать, что в левом поддеревехранятся ключи строго меньшие текущего, а в правом – большие, либо равные ему.Поиск нужного значения в таком дереве будет несложным:while (t) {if (t->key == x) { break; /* Найдено! */ }else if (x < t->key) { t = t->left; }else { t = t->right; }}48Мы спускаемся от корня к листьям, в каждом узле выбираем направление движения либов левое, либо в правое поддерево.
Если искомое значение в дереве есть – мы его найдём,если же оно отсутствует – мы доберёмся до листа, причём, если нам надо будет вставитьискомое значение – то мы вставим его прямо в этот лист. Сама операция вставки в этомслучае не будет зависеть от количества узлов в нашем дереве, но она обязательно должнапредваряться процедурой поиска значения в дереве, а эта операция будет пропорциональнавысоте дерева.Более-менее очевидно, что если нам ключи для поиска и вставки поступают в случайномпорядке, то наше дерево будет достаточно плотно заполнено, и, следовательно, его высотане будет существенно отличаться от высоты идеально сбалансированного дерева.
Более того, это утверждение было строго доказано: высота спонтанно заполняемого дерева поискаотличается от высоты идеально сбалансированного дерева только множителем. А высотаидеально сбалансированного дерева равна, очевидно, двоичному логарифму от количестваего узлов.То есть, для двоичного дерева и поиск, и добавление нового элемента будут логарифмически зависеть от количества сохранённых данных, это очень хороший результат: например,если у нас сохранено 65 535 элементов, то высота такого дерева будет равна всего 16.Осталось выяснить, как будут удаляться элементы? Очевидно, чтобы удалить нужное значение, его необходимо сначала найти в нашем дереве.
Мы помним, что поиск занимаетлогарифмическое время.Далее, если мы попали в лист – то его удалить легко: нужно просто обнулить один указатель в родительском узле. Если нам нужно удалить узел с одним потомком – мы с этимтоже легко справимся, в этом случае надо заменить в родительском узле указатель, который указывает на удаляемый узел на указатель единственного потомка удаляемого узла.Понятно, что обе эти операции будут константными по времени.А что делать, если нужно удалить внутренний узел, у которого два потомка? Ведь у родителя удаляемого узла можно заменить только один указатель, а тут надо сохранить двауказателя. В этом случае задачу удаления внутреннего узла сводят к задаче удаления листа: давайте в правом поддереве удаляемого узла найдём самый левый лист и удалим его,но перед удалением – обменяем ключи найденного листа и удаляемого узла:10524180712942176Рис.
19: Удаление внутреннего узлаЛегко заметить, что такая операция сохранит главное свойство нашего дерева поиска:отношения порядка между левыми и правыми поддеревьями для любого узла, так каксамый левый узел в правом поддереве – меньше всех остальных ключей этого поддерева,но одновременно он больше любого ключа левого поддерева.49С точки зрения производительности единственное, что нам придётся сделать – это дойти долиста, то есть пройти всю высоту дерева. Удаление же листа – константная операция. Таким образом, мы приходим к выводу, что и время на удаление любого ключа из двоичногодерева будет пропорционально логарифму от общего количества хранимых элементов.Балансировка двоичного дереваТо, что тут было рассказано о двоичных деревьях, показывает их эффективность для случайно заполненного дерева.
Однако, если ключи поступают для заполнения не случайно (а,например, в порядке возрастания их значения), – наше дерево выродится в одну длиннуюлинейную ветвь и его высота будет пропорциональна общему количеству узлов, поэтомуни о какой логарифмической эффективности основных операций в таком случае речь идтине может.Для того, чтобы застраховаться от таких «неудачных» случаев, нужно при каждой операции вставки или удаления ключа предусмотреть специальную процедуру перестроениядерева для того, чтобы длины его ветвей были как-то сбалансированы.Отметим, что понятие идеально сбалансированного дерева – неэффективно с вычислительнойточки зрения: в идеально сбалансированном дереве количество узлов в левом и правом поддеревьях любого узла различается не более, чем на единицу. То есть, даже для того, чтобыпроверить в каждом узле идеальную сбалансированность, нам надо пересчитать все дочерние узлы.
В среднем мы будем находиться где-то в середине дерева, при этом количестводочерних узлов будет пропорционально общему количеству узлов дерева, что и показываетнеэффективность этого подхода.Но если наложить ограничение не на количество узлов в поддеревьях узла, а лишь на разностьвысот левого и правого поддерева (а ведь именно высота дерева влияет на время поискаэлемента!), то алгоритм можно получить гораздо более эффективный.Назовём дерево сбалансированным (пусть и неидеально) АВЛ-деревом (по первым буквамфамилий: Адельсон-Вельский и Ландис), если для любого его узла выполняется правило:высоты его левого и правого поддеревьев могут различаться не более, чем на единицу.Отечественные математики Адельсон-Вельский и Ландис строго доказали, что принципиально различных случаев разбалансированности двоичного дерева может быть всего два,остальные получаются из них отражением вокруг вертикальной оси.BABA331122Рис.
20: АВЛ-балансировка первого типа50Рассмотрим первый вариант разбалансированного дерева, который может возникнуть, например, при вставке нового узла в поддерево 1 (см. схему 5.3). Заметим следующее соотношениемежду ключами узлов и деревьев в этом случае: ключи дерева 1 меньше ключа узла A, ключузла A меньше ключей дерева 2, ключи дерева 2 меньше ключа узла B, ключ узла B меньшеключей дерева 3.В исходном состоянии дерево 2 является поддеревом узла A, но в силу приведённого соотношения дерево 2 имеет право быть и поддеревом узла B.
Поэтому поменяем в узле B левуюсвязь на указатель поддерева 2, а правую связь узла A – направим на узел B. Если послеэтого подтянуть узел А на одну позицию вверх, а узел B – опустить на одну позицию вниз, томы получим сбалансированное дерево, показанное на схеме 5.3 справа. То есть, мы устранилиразбалансировку этого типа.BCAAC44B112233Рис. 21: АВЛ-балансировка второго типаТак как вставка в двоичное дерево осуществляется в листья, то разбалансировка второго типане может возникнуть в результате обычной вставки — так как сверх допустимого опустилисьбы вниз сразу два поддерева, а уже единственная вставка привела бы к разбалансировке, которую мы устранили бы описанным выше способом.
Но такое разбалансированное дерево можетвозникнуть как результат удаления узла, например, в поддереве 4. И эту разбалансированность тоже предстоит устранить, пользуясь тем же свойством упорядоченности поддеревьев:ключи дерева 1 меньше ключа узла A, ключ узла A меньше ключей дерева 2, ключи дерева 2меньше ключа узла B, ключ узла B меньше ключей дерева 3, ключи дерева 3 меньше ключаузла С, ключ узла С меньше ключей дерева 4. Поэтому дерево 2 имеет право оказаться правым поддеревом узла B, а дерево 3 имеет право оказаться левым поддеревом узла C. В своюочередь, узел A может находиться на левой связи узла B, а узел C имеет право находитьсяна правой связи узла B.
Если после такого обмена связей подравнять получившуюся высотудерева, подтянув узел B на две позиции вверх, то мы опять придём к полностью сбалансированному дереву, показанному на схеме 5.4 справа – так как деревья 2 и 3 поднимутся на однупозицию, а дерево 4 – на одну позицию опустится.Алгоритмов балансировки двоичных деревьев разработано много, однако, почти все онитем или иным способом ограничивают высоты левого и правого поддеревьев любого узла. Так, алгоритм «красно-чёрных деревьев», лежащий в основе некоторых контейнеровстандартных библиотек, допускает, что высоты левого и правого поддеревьев могут отличаться не более, чем в два раза.
При этом деревья получаются более высокими, чемв описанном здесь случае, зато затраты времени на балансировку будут гораздо меньше,так как балансировку можно производить реже и сама она менее накладна. Говоря проще,красно-чёрные деревья проигрывают АВЛ-деревьям по времени поиска, но выигрывают51– по времени вставки и удаления элементов, оставаясь, тем не менее, логарифмическиэффективными по всем трём операциям.10.6.Ассоциативные контейнеры, B-деревья, хэш-таблицыАссоциативные контейнерыОписанная здесь структура данных эффективна для решения значения поиска значения(ключа) в данном контейнере и при этом поддерживаются столь же эффективные операции добавления и удаления элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
