Что такое дерево в отношении компьютерных наук?
Когда большинство людей слышат слово «дерево», они могут представить себе хвойное дерево или пальму, может быть, осину или клен. На самом деле все зависит от региона, из которого вы приехали. Но когда ученые-компьютерщики говорят о деревьях, они имеют в виду определенный тип структуры данных. Это потому, что когда вы думаете о том, как организована древовидная структура данных, она напоминает органическое дерево.
Каковы основные компоненты дерева?
Основными компонентами дерева являются его узлы. Каждое дерево имеет узел, из которого вы можете найти все остальные узлы, он называется корневым узлом, для каждого дерева может быть только один из них. Это похоже на то, как с настоящими деревьями вы можете проследить путь от ствола дерева к каждому его листу. Узлы дерева могут быть одной из этих трех вещей: корнем, ветвью или листом. Корневой узел особенный, это место, откуда вы начинаете обход дерева. Узел ответвления — это узел, который имеет левый или правый дочерний узел. Листовой узел не имеет левого или правого дочернего узла.
Как связаны эти компоненты?
Все эти узлы связаны между собой указателями. Корневой узел может содержать 2 или более указателей на большее количество узлов. Каждый узел под ним также может указывать на 2 или более узлов и так далее и тому подобное. В этой статье мы в основном сосредоточимся на бинарных деревьях поиска, у которых есть только два потомка для каждого узла. Но даже в этом случае дерево быстро делится на множество отдельных путей, которые можно проследить от корневого узла до конечного узла. В качестве примечания, как и в реальных деревьях, у вас не может быть двух отдельных узлов в дереве, указывающих на один и тот же узел. Это было бы похоже на две ветки настоящего дерева, сросшиеся вместе, чтобы образовать одну ветвь. Вы также не можете иметь узел, указывающий на себя в одном из своих левых или правых указателей. Реальные деревья не растут кругами. Пожалуйста, полностью игнорируйте то, что вы видите слева, это не настоящая жизнь. Наверное, это был фотошоп, да? Посмотрите ниже изображение, подробно описывающее, что является деревом компьютерных наук, а что нет.
Чем они похожи на другие структуры данных, такие как списки или хеш-таблицы?
Как организованы деревья по сравнению с другими структурами данных?
Двоичные деревья поиска — это структуры данных, которые по своей природе упорядочены. Они имеют иерархическую структуру узлов, в которой у каждого узла есть возможность иметь дочерний узел, значение которого меньше или больше его самого. Сами деревья не хранятся в памяти непрерывно, а представляют собой систему узлов, которые соединяются друг с другом с помощью указателей. Левый указатель указывает на узел с данными, которые меньше нашего текущего узла, а правый указатель — на узел с данными, превышающими.
Деревья очень похожи на связанные списки тем, что они оба используют узлы и указатели, чтобы знать, где находится следующая часть информации. Ключевое различие между связанным списком и деревом заключается в том, что дерево имеет два или более указателя на новый узел для каждого имеющегося узла.
Если вы слышали о деревьях раньше, вы, возможно, слышали, что их особенно быстро обыскивают. В этом отношении это похоже на хеш-таблицу. Давайте поговорим о структуре хеш-таблицы. Хеш-таблица обычно реализуется с помощью массива, поэтому вы можете легко найти индекс любого заданного ключа и значения, которое вы вставляете. Чтобы найти индекс любого заданного ключа, вы создаете детерминированную хеш-функцию, то есть всякий раз, когда вы вводите один и тот же ключ, вы получаете одно и то же значение, а большинство ключей имеют разные значения. Эта функция возвращает число, представляющее ключ, затем вы находите индекс корзины, к которой принадлежит этот ключ, путем определения остатка хеш-значения ключей, деленного на длину массива, который вы используете для хеш-таблицы. Есть и другие вещи, которые делают хеш-таблицы, но мы не будем их сейчас обсуждать. Так что, если вы хотите узнать больше, посетите этот замечательный пост здесь.
Каковы преимущества использования деревьев по сравнению с другими конструкциями?
Достаточно сказать, что хеш-таблицы используют массив для отслеживания местоположения всех своих элементов, а также алгоритм для вставки и поиска элемента, который работает очень быстро. Это по сравнению с массивом, который вы можете использовать для очень быстрого поиска элементов путем индексации, если вы знаете, где они находятся. Если нет, вам нужно перебирать массив, пока не найдете искомый элемент. Это можно сравнить со связанным списком, где вам всегда нужно перебирать список, чтобы найти то, что вы ищете. Деревья вам также нужно перебирать вниз, но преимущество в том, что с каждым шагом вы избавляетесь от половины оставшихся вариантов вместо связанного списка, который избавляется от одного варианта. Это делает бинарные деревья поиска намного быстрее, чем связанные списки, но не так быстро, как хеш-таблицы в идеальных условиях.
Подробнее о бинарных деревьях поиска.
Как вы ищете информацию в дереве и какова его временная сложность?
Самый быстрый способ получить информацию в двоичном дереве поиска — пройти вниз от корня, сравнивая искомый элемент с данными текущего узла, если элемент меньше, идите влево, если он больше, идите вправо. Если ваше дерево разумно сбалансировано, то есть на одной стороне его узлов не намного больше, чем на другой, то время, необходимое для поиска элемента в нем, будет занимать O (log (n)), где n - количество элементов. в дереве. Это связано с тем, что вы должны вдвое сокращать объем информации, которую вам нужно искать, с каждым узлом, к которому вы переходите.
# Pseudo Code
Find this item, given a root_node and an item to look for.
Set current_node equal to root_node.
Create a loop that will run until the current nodes data is equal to the item we are looking for or current_node is not equal to anything.
If the item is less than the current nodes data.
Then current_node is set to current_nodes.left pointer.
Else if the item is greater than the current nodes data.
Then current_node is set to current_nodes.right pointer.
Once the loop breaks if current_node is not anything.
Then we return 'Could not find this node'
Else if the current_node is equal to the item.
Then we return 'Found this item'
Какова временная сложность добавления информации в дерево?
Чтобы добавить новый узел в дерево, вам нужно сделать узел постоянным, O (1). Затем вам нужно пройти по дереву до того места, куда пошли бы эти данные, если бы они были в дереве, это займет столько же времени, сколько поиск по дереву, O (log (n)). Затем, когда вы найдете место, которому он принадлежит, вы делаете узел выше, где он принадлежит, указывая на новый узел, который вы сделали.
Как сломать дерево, чтобы достичь наихудшей временной сложности?
Этот процесс добавления к дереву может иногда давать нам неожиданные результаты. В большинстве случаев мы не ожидаем, что данные будут добавляться в каком-либо определенном порядке, что хорошо и означает, что наши данные должны быть примерно равномерно распределены по нашему дереву. Но если мы начинаем с упорядоченного списка, произносим буквы а, б, в, г, е, е, г и добавляем их по порядку; каждое буквенное значение больше, чем последнее, поэтому каждое из них будет располагаться справа от своего родителя. Это дает нам дерево высотой 6 вместо возможной высоты 2. Это также означает, что при поиске по дереву нам придется перебирать каждый элемент в дереве, чтобы увидеть, есть что-то или нет. , точно так же, как связанный список. Эта временная сложность будет O(n), а это не то, что нам нужно.
Как можно оптимизировать деревья?
Одним из способов оптимизации времени поиска было бы удаление элементов из дерева и вставка их обратно в оптимальном порядке поиска. Оптимальным порядком поиска будет порядок, в котором вы будете выполнять двоичный поиск по заданным элементам, если они будут отсортированы. Это потребует, чтобы вы скопировали все содержимое вашего дерева в другое место, затем отсортировали его в правильном порядке, затем создали новое дерево, а затем поместили элементы обратно. должны были делать это каждый раз, когда вы хотели добавить элемент в свое дерево. К счастью, были разработаны другие более эффективные способы.
Представляем деревья AVL.
АВЛ означает имена изобретателей Адельсона-Вельского и Лэндиса (http://people.cs.ksu.edu/). Это бинарная древовидная структура, которая самобалансируется за счет вращения дерева при добавлении новых узлов. Если дерево всегда сбалансировано, то у вас всегда есть оптимальное время поиска для нахождения любого заданного узла.
Какие дополнительные функции необходимо реализовать для создания дерева AVL?
Чтобы реализовать дерево AVL, вам необходимо реализовать функцию поворота дерева как для левого, так и для правого поворота. Их можно использовать в комбинации для создания поворотов вправо-влево и влево-вправо.
# Pseudo Code A given nodes balance is eqal to its left height minus its right In a right rotation you set the parent's left node's right pointer to the parent and the parent's left pointer equal to the left nodes right pointer. in a left rotation you set the parent's right node's left pointer to the parent, and the parent's right pointer equal to the right nodes, left pointer. if balance is greater than one and the item is less than the parents.left nodes data preform a left rotation. if balance is less than negative one and the item is greater than the parents.right nodes data preform a left rotation. if balance is greater than one and the item is greater than the parents.left nodes data preform a left rotation then a right rotation on the same sub tree. if balance is less than negative one and the item is greater than the parents.right nodes data preform a right rotation then a left rotation on the same sub tree.
В заключении:
Бинарные деревья позволяют эффективно хранить и искать данные. Хотя их эффективность снижается по мере того, как они становятся более неуравновешенными. Хороший способ предотвратить этот дисбаланс — реализовать самобалансирующееся дерево. Дерево AVL - отличный способ сделать это, хотя, вероятно, есть много других.
