Бинарное дерево и Декартово дерево
Дерево (свободное) – непустая коллекция вершин и ребер, удовлетворяющих определяющему свойству дерева. Вершина (узел) – простой объект, который может содержать некоторую информацию. Ребро – связь между двумя вершинами. Путь в дереве – список отдельных вершин, в котором следующие друг за другом вершины соединяются ребрами дерева Определяющее свойство дерева – существование только одного пути, соединяющего два узла. Дерево (свободное) – неориентированный связный граф без циклов Дерево с корнем – дерево, в котором один узел выделен и назначен корнем дерева. Существует только один путь между корнем и каждым из других узлов дерева. Высота (глубина) дерева с корнем – количество вершин в самом длинном пути от корня Каждый узел (за исключением корня) имеет только один узел, расположенный над ним. Такой узел называется родительским. Узлы, расположенные непосредственно под данным узлом, называются его дочерними узлами. Узлы, не имеющие дочерних узлов называются листьями.
Двоичное (бинарное) дерево – это дерево, в котором
степени вершин не превосходят 3.
Двоичное (бинарное) дерево с корнем – это дерево, в
котором каждая вершина имеет не более двух дочерних
вершин.
Двоичное дерево поиска – это двоичное дерево, с каждым узлом которого связан ключ, и выполняется следующее дополнительное условие: ключ в любом узле X больше или равен ключам во всех узлах левого поддерева X и меньше или равен ключам во всех узлах правого поддерева X.
Поиск по ключу Проверить есть ли узел с ключом K в дереве с корнем X, и если да, то вернуть указатель на этот узел Если дерево пусто сообщить, что узел не найден и остановиться, иначе:
- Если К=Х, вернуть указатель на этот узел и остановиться
- Если К>Х, искать ключ К в правом поддереве
- Если К<Х, искать ключ К в левом поддереве Время работы: О(h), где h – глубина дерева
Найти узел с минимальным значением ключа K в дереве с корнем X Переходить в левый дочерний узел, пока такой существует
Время работы: О(h), где h – глубина дерева
Вставить узел с ключом K в дерево с корнем X (возможно появление дубликатов) Если дерево пусто, заменить его на дерево с одним корневым узлом и остановиться, иначе сравнить К с ключом корневого узла Х. Если К < Х, рекурсивно добавить К в левое поддерево Х, иначе рекурсивно вставить в левое поддерево Х.
Время работы: О(h), где h – глубина дерева
Удалить узел с ключом K из дерева с корнем X Если дерево пусто, остановиться, иначе сравнить К с ключом корневого узла Х:
- Если К < Х, рекурсивно удалить К из левого поддерева Х
- Если К > Х, рекурсивно удалить К из правого поддерева Х
- Если К == Х, то:
- Дочерних узлов нет – удаляем узел Х
- Один дочерний узел – переносим дочерний узел в Х
- Оба дочерних узла есть
Заменяем ключ удаляемого узла на ключ минимального узла из правого поддерева, удаляя последний.
Время работы: О(h), где h – глубина дерева
Декартово дерево (eng. Treap) – структура данных, объединяющая в себе двоичное дерево поиска и двоичную кучу (tree+heap = treap). Декартово дерево – двоичное дерево, в узлах которого хранятся пары <x,y>, где x – ключ, а y – это приоритет. Все х и все у являются различными. Если некоторый элемент дерева содержит (х0, у0), то у всех элементов в левом поддереве х<x0, у всех элементов в правом поддереве x>x0, а также в левом и правом поддереве y<y0. Таким образом, декартово дерево является двоичным деревом поиска по х и кучей по у.
В компьютерных науках ку́ча (heap) — это
специализированная структура данных типа дерево,
которая удовлетворяет свойству кучи: если B является
узлом-потомком узла A, то ключ(A) ≥ ключ(B).
В декартовом дереве из n узлов, приоритеты которого являются случайными величинами с равномерным распределением, средняя глубина дерева O(log n). Операции:
- Разрезание – Split
- Слияние – Merge На их основе:
- Вставка
- Удаление
Операция разрезания позволяет разрезать декартово дерево Т по ключу К и получить 2 других дерева: Т1 и Т2, причем в Т1 находятся все ключи дерева Т, не большие К, а в Т2 – большие К.
Операция слияния позволяет слить 2 декартовых дерева в одно. Причем все ключи в левом дереве должны быть меньше, чем ключи в правом. В результате получается дерево, в котором есть все ключи из первого и второго деревьев.
Добавляется элемент <x,y>, где x – ключ, а y – это приоритет. Элемент <x,y> - дерево из одного элемента. Для того, чтобы добавить его в декартово дерево Т, их нужно слить. Но Т может содержать ключи как меньше, так и больше ключа х, поэтому сначала нужно разрезать Т по ключу х. Реализация 1
- Разрезаем Т по ключу х на L и R
- Сливаем первое дерево L с новым элементом.
- Сливаем получившееся дерево с деревом R.
Реализация 2
- Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по х), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше у.
- Разрезаем поддерево данного элемента на L и R
- Полученные деревья записываем в качестве левого и правого сына добавляемого элемента
- Полученное дерево вставляем на место элемента, найденного в первом пункте.
Merge вообще не используется.
Удаляется элемент с ключом х Реализация 1
- Разобьем дерево по ключу х на L и R
- Теперь отделяем от первого дерева L элемент х разбивая по ключу (х – е) (x-1)
- Сливаем измененное дерево L со вторым R
Реализация 2
- Спускаемся по дереву (как в обычном бинарном дереве поиска по х), ища удаляемый элемент
- Вызываем слияние его левого и правого сыновей
- Результат ставим на место удаляемого элемента
Split не используется
При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить этот минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма — O(h).
В современных C++ в большинстве случаев предпочтительным способом сообщить и обрабатывались как логические ошибки, так и ошибки времени выполнения — использовать исключения. Особенно это касается того, что стек может содержать несколько вызовов функций между функцией, которая обнаруживает ошибку, и функцией, которая имеет контекст для ее устранения. Исключения предоставляют формальный, четко определенный способ для кода, который обнаруживает ошибки для передачи информации вверх по стеку вызовов.
указатель на указатель