Saved searches
Use saved searches to filter your results more quickly
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.
Бинарное дерево и Декартово дерево
JohnnyP0T/BinaryTree_Treap
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Sign In Required
Please sign in to use Codespaces.
Launching GitHub Desktop
If nothing happens, download GitHub Desktop and try again.
Launching GitHub Desktop
If nothing happens, download GitHub Desktop and try again.
Launching Xcode
If nothing happens, download Xcode and try again.
Launching Visual Studio Code
Your codespace will open once ready.
There was a problem preparing your codespace, please try again.
Latest commit
Git stats
Files
Failed to load latest commit information.
README.md
Бинарное дерево и Декартово дерево
Дерево (свободное) – непустая коллекция вершин и ребер, удовлетворяющих определяющему свойству дерева. Вершина (узел) – простой объект, который может содержать некоторую информацию. Ребро – связь между двумя вершинами. Путь в дереве – список отдельных вершин, в котором следующие друг за другом вершины соединяются ребрами дерева Определяющее свойство дерева – существование только одного пути, соединяющего два узла. Дерево (свободное) – неориентированный связный граф без циклов Дерево с корнем – дерево, в котором один узел выделен и назначен корнем дерева. Существует только один путь между корнем и каждым из других узлов дерева. Высота (глубина) дерева с корнем – количество вершин в самом длинном пути от корня Каждый узел (за исключением корня) имеет только один узел, расположенный над ним. Такой узел называется родительским. Узлы, расположенные непосредственно под данным узлом, называются его дочерними узлами. Узлы, не имеющие дочерних узлов называются листьями.
Двоичное (бинарное) дерево – это дерево, в котором степени вершин не превосходят 3. Двоичное (бинарное) дерево с корнем – это дерево, в котором каждая вершина имеет не более двух дочерних вершин.
Двоичное дерево поиска – это двоичное дерево, с каждым узлом которого связан ключ, и выполняется следующее дополнительное условие: ключ в любом узле X больше или равен ключам во всех узлах левого поддерева X и меньше или равен ключам во всех узлах правого поддерева X.
Поиск по ключу Проверить есть ли узел с ключом K в дереве с корнем X, и если да, то вернуть указатель на этот узел Если дерево пусто сообщить, что узел не найден и остановиться, иначе:
- Если К=Х, вернуть указатель на этот узел и остановиться
- Если К>Х, искать ключ К в правом поддереве
- Если К
Поиск минимального ключа бинарного дерева
Найти узел с минимальным значением ключа K в дереве с корнем X Переходить в левый дочерний узел, пока такой существует
Время работы: О(h), где h – глубина дерева Добавление узла бинарного дерева
Вставить узел с ключом K в дерево с корнем X (возможно появление дубликатов) Если дерево пусто, заменить его на дерево с одним корневым узлом и остановиться, иначе сравнить К с ключом корневого узла Х. Если К < Х, рекурсивно добавить К в левое поддерево Х, иначе рекурсивно вставить в левое поддерево Х.
Время работы: О(h), где h – глубина дерева Удаление узла бинарного дерева
Удалить узел с ключом K из дерева с корнем X Если дерево пусто, остановиться, иначе сравнить К с ключом корневого узла Х:
- Если К < Х, рекурсивно удалить К из левого поддерева Х
- Если К > Х, рекурсивно удалить К из правого поддерева Х
- Если К == Х, то:
- Дочерних узлов нет – удаляем узел Х
- Один дочерний узел – переносим дочерний узел в Х
- Оба дочерних узла есть
Удаление узла. Оба дочерних узла есть. Бинарного дерева
Заменяем ключ удаляемого узла на ключ минимального узла из правого поддерева, удаляя последний.
Время работы: О(h), где h – глубина дереваДекартово дерево (eng. Treap) – структура данных, объединяющая в себе двоичное дерево поиска и двоичную кучу (tree+heap = treap). Декартово дерево – двоичное дерево, в узлах которого хранятся пары , где x – ключ, а y – это приоритет. Все х и все у являются различными. Если некоторый элемент дерева содержит (х0, у0), то у всех элементов в левом поддереве хx0, а также в левом и правом поддереве y
В компьютерных науках ку́ча (heap) — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B).В декартовом дереве из n узлов, приоритеты которого являются случайными величинами с равномерным распределением, средняя глубина дерева O(log n). Операции:
Операция разрезания позволяет разрезать декартово дерево Т по ключу К и получить 2 других дерева: Т1 и Т2, причем в Т1 находятся все ключи дерева Т, не большие К, а в Т2 – большие К.
Операция слияния позволяет слить 2 декартовых дерева в одно. Причем все ключи в левом дереве должны быть меньше, чем ключи в правом. В результате получается дерево, в котором есть все ключи из первого и второго деревьев.
Добавляется элемент , где x – ключ, а y – это приоритет. Элемент — дерево из одного элемента. Для того, чтобы добавить его в декартово дерево Т, их нужно слить. Но Т может содержать ключи как меньше, так и больше ключа х, поэтому сначала нужно разрезать Т по ключу х. Реализация 1
- Разрезаем Т по ключу х на L и R
- Сливаем первое дерево L с новым элементом.
- Сливаем получившееся дерево с деревом R.
- Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по х), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше у.
- Разрезаем поддерево данного элемента на L и R
- Полученные деревья записываем в качестве левого и правого сына добавляемого элемента
- Полученное дерево вставляем на место элемента, найденного в первом пункте.
Merge вообще не используется.Удаляется элемент с ключом х Реализация 1
- Разобьем дерево по ключу х на L и R
- Теперь отделяем от первого дерева L элемент х разбивая по ключу (х – е) (x-1)
- Сливаем измененное дерево L со вторым R
- Спускаемся по дереву (как в обычном бинарном дереве поиска по х), ища удаляемый элемент
- Вызываем слияние его левого и правого сыновей
- Результат ставим на место удаляемого элемента
При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить этот минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма — O(h).
В современных C++ в большинстве случаев предпочтительным способом сообщить и обрабатывались как логические ошибки, так и ошибки времени выполнения — использовать исключения. Особенно это касается того, что стек может содержать несколько вызовов функций между функцией, которая обнаруживает ошибку, и функцией, которая имеет контекст для ее устранения. Исключения предоставляют формальный, четко определенный способ для кода, который обнаруживает ошибки для передачи информации вверх по стеку вызовов.
Источник
Удаление из BST (бинарного дерева поиска)
Имея BST, напишите эффективную функцию для удаления заданного ключа в нем.
Существует три возможных случая удаления узла из BST:
Случай 1: Удаление узла без потомков: удалить узел из дерева.
Случай 2: Удаление узла с двумя дочерними элементами: вызовите удаляемый узел N . Не удалять N . Вместо этого выберите либо его в целях преемник узел или его порядок предшественник узел, R . Скопируйте значение R к N , затем рекурсивно вызовите delete на R до достижения одного из первых двух случаев. Если мы выберем неупорядоченного преемника узла, поскольку правое поддерево не равно NULL (наш текущий случай — это узел с двумя дочерними элементами), то его неупорядоченный преемник — это узел с наименьшим значением в его правом поддереве, который будет иметь в максимум 1 поддерево, поэтому его удаление попадет в один из первых 2-х случаев.
Случай 3: Удаление узла с одним дочерним элементом: удалите узел и замените его своим дочерним элементом.
Вообще говоря, узлы с дочерними элементами удалить сложнее. Как и во всех бинарных деревьях, неупорядоченный преемник узла является самым левым дочерним элементом его правого поддерева, а неупорядоченный предшественник узла является самым правым дочерним элементом левого поддерева. В любом случае у этого узла будет ноль или один дочерний элемент. Удалите его в соответствии с одним из двух более простых случаев выше.
Алгоритм может быть реализован следующим образом на C++, Java и Python:
Источник
