Вы знаете, что такое двоичное дерево поиска и понятие набор в математике? В этой статье мы собираемся построить самобалансированное двоичное дерево с заданными свойствами (AVL), которое сможет нести любой тип данных (из встроенных -in к вашим собственным объектам) с помощью суперфункции в шаблонах C ++.
Деревья могут быть сложными структурами данных, большинство функций, которые могут выполняться с деревьями, требуют рекурсивных вызовов. Это упражнение поможет нам научить наш мозг мыслить рекурсивно, понять, как строится класс двоичного дерева, как дерево AVL является самоуравновешенным, а также различные причины для использования двоичного дерева поверх других структур данных, включая простой анализ сложности.
Дерево считается двоичным деревом, когда каждый узел имеет не более двух подузлов (дочерних узлов) во всем дереве, так что один подузел, который не существует, обычно указывается на NULL. Полное двоичное дерево - это когда все уровни дерева полностью заполнены, а последний уровень - нет. Некоторые термины Деревьев: Край (связь между двумя узлами), Дочерний и Родительский узел, Корневой (самый верхний узел и родитель всех дочерних узлов) и Leaf (узел без дочернего узла).
Для начала мы собираемся определить класс DoublyNode для двоичного дерева поиска, это означает, что каждый узел может иметь не более 2 дочерних элементов, другими словами, каждый узел дерева состоит из 2 указателей (left: предыдущая или правая: следующая) и данные значение ‹Type›, а также его переменные-члены и определения функций.
В классе DoublyNode файл заголовка DoublyNode.h будет содержать #pragma один раз и шаблон, чтобы сделать узел гибким для переноса различных типов данных template ‹ class Type ›, определение класса с частной переменной-членом Type data и двумя общедоступными указателями Type (left и right), которые будут инициализированы значением NULL ( nullptr для C ++ 11) в совокупной форме C ++ 11 Тип * left {nullptr}, * right {nullptr}; .
Зачем использовать #pragma один раз или #ifndef DOUBLYNODE_H #def DOUBLYNODE_H #endif? это добавляется для однократного включения файла в одну компиляцию. Все функции-члены являются общедоступными, два конструктора (один без параметров и один с параметром Type value), setter для установки значения для узла и получатель значения ключа узла в соответствии с концепцией инкапсуляции ООП.
Класс DoublyNode и файл .cpp в строках 5–13 содержат два конструктора, в данном случае у нас есть только конструктор с определением параметра (const Type & data), в котором передается значение данных. в качестве аргумента присваивается ключ узла, а затем указатели справа и слева присваиваются {nullptr}.
В определении класса (файл DoublyNode.cpp) определения функций-членов очень просты и понятны, это следующие методы: геттеры, сеттеры и, наконец, деструктор, который присваивает как левому, так и правому указателям значение NULL, чтобы избежать зависания указателя.
Древовидный набор реализует двоичное дерево поиска (BST). Почему двоичное дерево поиска? BST - это коллекции, которые поддерживают динамически изменяющийся набор данных в отсортированном порядке, в отличие от отсортированного массива, в котором его элементы не могут быть эффективно вставлены и удалены, BST полезен для многих задач, поскольку он позволяет двоичному поиску эффективно находить элементы и вставлять элементы в отсортированном порядке. BST имеют сложность выполнения в худшем случае O (h), где «h» - высота дерева.
Высота (h) дерева - это количество ребер между корнем дерева и его самым дальним листом. Для случая на изображении выше сложность выполнения поиска, вставки и удаления составляет O (log n) log base 2 (двоичный) [log 7 = 2].
BST имеет четыре свойства: каждый узел дерева содержит один и только один ключ, значения ключей левого поддерева меньше его общего родительского значения ключа и значения ключей правого поддерева больше, чем значение его общего родительского ключа (определено рекурсивно), и, в конечном итоге, повторяющиеся значения ключей не допускаются в соответствии с математическим определением SET {}.
Объявление класса нашего дерева находится в файле TreeSet.h, где мы можем найти сначала объявление файла прекомпилятора #pragma once, объявление template ‹class Type›. , методы-члены и, наконец, объявления переменных-членов. Для начала переменные-члены являются частными (строки 9 и 10): int length (хранит количество узлов в дереве), DoublyNode ‹Type› Root (глава дерево).
В методах общедоступных членов мы можем найти методы базовой структуры данных для выполнения основных операций (вставка, удаление, поиск и очистка). Методы закрытых членов - это рекурсивные методы, которые выполняются внутри Дерева. Зачем нам нужна рекурсия в древовидном наборе? дерево - это рекурсивная структура данных, это означает, что дерево частично состоит из меньших или более простых экземпляров одной и той же структуры данных.
Первая функция, которую нужно определить, - это INSERTION. Метод «void insert (const Type & data)» или «void insert (const DoublyNode ‹Type› & newNode)» вставляет новый узел в дерево и является общедоступным, другими словами, он доступен извне класса, параметр может быть значением Type TreeSet ‹Type› или уже созданным узлом. Внутри метода есть вызов частного рекурсивного метода (insertRecursively), этот метод выполняет итерацию по дереву, сравнивая значение данных с узлами и перемещаясь в соответствии со свойством BST для распределение (меньше, чем перемещение влево, больше, чем перемещение вправо), пока не попадет в листовой узел, а затем новый узел добавляется как дочерний узел листового узла.
На изображении выше, чтобы вставить 40, он должен пересечь Дерево, сравнивая его значение с другими узлами: 1) 40 меньше 100, переместите влево, 2) 40 больше, чем 20, перемещение вправо, 3) 40 больше, чем 30, а 30 - листовой узел, добавить 40 вправо. Обратите внимание, что все значения в левой части корня меньше 100.
Этот процесс выполняется рекурсивно с передачей узла и данных для сравнения и повторным вызовом метода в зависимости от того, меньше или больше, чем нужно перемещать по дереву. Наихудшая временная сложность операций поиска и вставки составляет O (h), где h - высота двоичного дерева поиска.
На изображении выше мы можем найти рекурсивный метод для вставки нового узла, базовый случай - это когда текущая позиция узла равна NULL, и добавляется новый узел, если нет, есть еще два рекурсивных вызова, используя это вызывает, что мы пересекаем дерево, сравнивая текущий узел с новым узлом, и продвигаемся вперед согласно свойствам BST.
Метод вставки в двоичное дерево поиска может иметь наихудшую сложность поиска, вставки и удаления O (n), это происходит, когда BST не сбалансирован и называется вырожденным двоичным деревом поиска.
На изображении выше все эти двоичные деревья поиска неэффективны, потому что они не являются полным двоичным деревом, другими словами, каждый узел или большинство из них имеют только одного дочернего элемента, чтобы доказать это, мы выбираем первую BTS на изображении, чтобы вставьте 5, это займет O (h), а высота равна 5 одинаковому количеству узлов, что означает, что процесс вставки, удаления и поиска для этого случая составляет O (n) (аналогично связному списку).
Основная причина наличия BST заключается в том, что каждая операция выполняется с временной сложностью не более O (log n), для этого мы должны определить и реализовать идею сбалансированного двоичного дерева поиска.
Сбалансированно-двоичное дерево поиска - это дерево, в котором разница высот его правого дочернего элемента (-ов) и левого дочернего элемента (-ов) не превышает 1. Как я упоминал ранее, дерево представляет собой рекурсивную структуру данных, а баланс BST концепция применяется к каждому узлу и подузлу в дереве. сбалансированный BST сохраняет свою высоту небольшой, и каждый путь к корневому листу выполняется за log (n) шагов.
В качестве последнего подхода к созданию нашей структуры данных Tree-Set (AVL) нам необходимо сбалансировать наше дерево и реализовать концепцию деревьев AVL.
Дерево AVL (Адельсон-Вельский и Е.М. Ландис) - это простые самобалансирующиеся бинарные деревья, для которых требуется, чтобы высота левого и правого поддеревьев каждый узел может отличаться не более чем на 1.
Деревья AVL выполняют вращения каждый раз, когда дерево не сбалансировано из-за вставки или удаления узла.
Есть два типа вращения: левое и правое. Поворот влево и вправо выполняется рекурсивно, от базового случая до корня Дерева.
Важно рассчитать высоту каждого поддерева и Дерева, чтобы сравнить высоту поддеревьев, а затем выполнить вращения, этот метод depthRecursively (const DoublyNode ‹Type› * node) вычисляет высоту заданного узла рекурсивно и сравнивая левое и правое поддеревья, его базовый случай, когда текущий узел равен NULL, возвращает 0.
Другой метод используется для сравнения левой и правой высоты поддеревьев, вызывая метод: depthRecursively (const DoublyNode ‹Type› * узел). этот сопоставимый метод возвращает разницу между высотами и называется getBalance (const DoublyNode ‹Type› * node).
Операции вращения занимают постоянное время, потому что изменяется несколько указателей, поэтому временная сложность вставки AVL остается как сбалансированный BST O (log n).
Чтобы убедиться, что BST реализует концепцию AVL после каждой модификации дерева, необходимо выполнить некоторую повторную балансировку. Этот процесс состоит из четырех различных случаев: регистр слева-слева, регистр слева-направо, регистр справа-справа и регистр справа-слева.
В первом случае дерево поворачивается вправо один раз, в приведенном выше примере узел 50 назначается как новый корень дерева, а его правый указатель влево теперь указывает на узел 100, с другой стороны, левый указатель узел 100 теперь указывает на узел 65.
Случай Right-Right аналогичен случаю Left-Left, дерево поворачивается влево после получения нового корня и перемещения указателей с постоянной временной сложностью.
Приведенный выше случай более сложен, но если мы посмотрим на него поближе, это просто левое вращение в поддереве, а затем правое вращение в дереве с получением нового корня. То же самое происходит практически в случае с правым-левым.
Идея этих случаев состоит в том, чтобы реализовать их в нашем рекурсивном методе вставки.
Следующая операция - ПОИСК в дереве, эта довольно простая, объявление метода в заголовке класса TreeSet isInSet (const Type & data) вызывает рекурсивный частный метод searchRecursively (узел DoublyNode ‹Type› *, тип const и данные), этот метод работает так же, как и вставка, но возвращает логическое значение независимо от того, найдены ли данные в дереве или нет.
базовый случай поиска - когда текущий узел равен NULL, он возвращает false. если значение, которое ищется, найдено, оно возвращает истину и присваивается другим вызовам.
Обратите внимание, что если вы загружаете код с GitHub, оба метода находятся в разных местах в файле TreeSet.cpp.
