Сводка древовидной структуры данных один (куча, тройка и набор поиска)

Древовидная структура является очень важной структурой данных. Мы можем решить проблему сортировки, сбалансировав двоичное дерево, используя древовидную структуру для представления грамматической структуры исходной программы, а также дерево может представлять базу данных или файловую систему. А нижний слой многих контейнеров представляет собой древовидную структуру.

Давайте сначала разберемся, что собой представляют существительные о древовидной структуре:

Узел: представляет элемент данных в дереве, A, B...H является узлом.
Степень узлов: количество подчиненных узлов, принадлежащих узлу, и степень B равна 2.
Степень дерева: максимальная степень каждого узла в дереве, где степень дерева равна 2.
Листовой узел: узел со степенью 0. Узлы D, H, F, G являются листовыми узлами.
Дочерний (Child): Node левый и правый узлы. На графике узлы D и E являются дочерними узлами узла B.
Родитель: Верхний узел узла называется родителем узла. Узел B является родителем узлов D и E.
Предок: все узлы на ветке от корня до этого узла. A является предком всех остальных узлов.
Потомок: любой узел в поддереве с корнем в узле. Все узлы, кроме A, являются потомками A.
Брат: Ребенок тех же родителей. Узлы B и C — братья друг другу, узлы D и F — братья друг другу, а узлы F и G — братья друг другу.
Кузены (Sibling): Узлы с разными родителями на одном уровне. E и F являются двоюродными братьями друг другу.
Уровень узла: количество ветвей на пути от корневого узла к узлу в дереве называется уровнем узла. Уровень А равен 4.
Глубина дерева: максимальное количество уровней узлов в дереве. Здесь глубина дерева равна 4.

Здесь объясняется только бинарное дерево (у узла есть только два левых и правых дочерних элемента), конечно, дерево не обязательно имеет только двух дочерних элементов, таких как объединение и тройное дерево, которые появятся ниже, но мы можем преобразовать большинство деревьев в бинарные деревья, чтобы нам было удобнее понимать концепцию.

Прежде чем приступить к бинарному дереву, давайте рассмотрим концепции бинарного дерева:

Полный двоичный двоичный: K и имеет глубину 2 ^ k - 1 узлы в двоичном дереве называется полным двоичным деревом

Полное двоичное дерево: полное двоичное дерево удовлетворяет идеальному бинарному дереву из корневого узла в предпоследний слой, а последний слой может быть не полностью заполнен, а его узлы листьев выровнены влево.

Бинарное дерево баланса: Глубина левого и правого подстроек на узел не превышает 1

Абсолютно сбалансированное дерево: только последний слой является листовым узлом и соответствует характеристикам бинарного дерева поиска.

бинарное дерево поиска

Если сейчас есть массив, задано число (это число есть в массиве), и требуется найти позицию индекса этого числа в этом массиве, мы можем пройти только по одному, а временная сложность в это время равно O(n) , чтобы ускорить скорость поиска, если массив, который мы получаем, отсортирован, мы можем использовать метод половинного поиска, поэтому временная сложность составляет O(logn), а скорость будет очень быстрой. Идея половинного поиска заключается в использовании идеи бинарного поиска.

Давайте сначала посмотрим на структуру узлов бинарного дерева поиска:

class Node{
    int data;//节点值
    Node left;//左孩子
    Node right;//右孩子
}

определение бинарного дерева поиска

Все узлы в левом поддереве узла меньше, чем этот узел, и все узлы в правом поддереве узла больше, чем этот узел.

Операции над бинарными деревьями поиска

вставлять

Операция вставки бинарного дерева поиска очень проста:

Определить, есть ли корневой узел, и нет ли текущего узла в качестве корневого узла
Если есть узел, сравните его с правым узлом, если он больше текущего узла, и сравните его с левым узлом, если он меньше текущего узла.
Если сравнение достигает конечного узла, вставьте
Повторяйте 2 шага до конца 3 шага

Средняя временная сложность вставки составляет O(logn)

Удалить

Операция удаления немного сложнее, и удаляемые узлы делятся на три случая.

Нет детей: переход непосредственно к удалению узла
Есть дочерний узел: удалить узел, пусть дочерний узел этого узла переместится на позицию этого узла
Есть два дочерних элемента: удалите узел и переместите крайний левый узел X заднего дочернего элемента этого узла (крайний правый узел левого дочернего элемента также можно переместить) в эту позицию.В настоящее время у X может быть только правый дочерний элемент , а затем измените положение исходного X. Вы можете удалить его, если есть только один дочерний элемент.

Средняя временная сложность удаления составляет O(logn)

найти

Методы поиска и вставки аналогичны, поэтому я не буду их здесь повторять.

Средняя временная сложность поиска составляет O(logn).

ДФС, БФС

Если вы хотите пройти по бинарному дереву, есть два способа: обход в глубину и обход в ширину, а обход в глубину можно разделить на обход в прямом, последовательном и обратном порядке.

Обход в глубину (DFS): идея обхода в глубину состоит в том, чтобы сначала пройти узлы из каждой ветви.
- Предварительный обход: узел - левый дочерний элемент - правый дочерний элемент
- Неупорядоченный обход: левый дочерний элемент - узел - правый дочерний элемент
- Обход в обратном порядке: левый дочерний элемент - правый дочерний элемент - узел
Обход в ширину (BFS): обход с каждого слоя

Давайте посмотрим на картинку, чтобы увидеть, как выглядит конкретный обход:

Обход предварительного заказа: ABCDEF
Обход по порядку: CBDAEF
Почтовый заказ: CDBFEA
Обход в ширину: ABECDF

Роль бинарного дерева поиска

Для массивов требуется O(n) времени для добавления и удаления и O(n) времени для поиска.
Для бинарного дерева поиска его добавление, удаление и время поиска равны O(logn).

куча

Определение кучи

куча - этополное бинарное дерево,иУзел больше (меньше) своих левого и правого потомков

Посмотрите на структуру узла кучи

class Node{
    int data;//节点值
    Node left;//左孩子
    Node right;//右孩子
}

операции с кучей

Для кучи он уделяет больше внимания размещению наибольшего на первом месте и сохранению природы кучи. Здесь, поскольку куча представляет собой полное двоичное дерево, для хранения элементов в куче можно использовать массив.

Как показано на рисунке (В следующем используется мини-куча, т. е. каждый узел меньше своих дочерних элементов):

Тогда для узла мы можем легко найти родительский узел, а также левый и правый узлы этого узла.

//获得双亲结点的下标
int getParent(int index){
    return (index + 1) / 2 - 1;
}
//获得左孩子
int getLeftChild(int index){
    return index * 2 + 1;
}
//获得右孩子
int getRightChild(int index){
    return index * 2 + 2;
}

Вставка, этот шаг называется просеиванием кучи
- Сначала поместите элемент в конец массива
- Сравните размер этого элемента с его родительским узлом, и если этот узел меньше, чем его родительский узел, поменяйте позиции с этим узлом.
- Повторите шаг 2, если головной узел или родительский узел больше, чем при сравнении с конечным узлом.
Удалить (удаление здесь относится к удалению головного элемента и головного узла), этот шаг называется просеиванием кучи.
- Удалите элемент с индексом 0 из массива и поместите последний элемент в массив с индексом 0.
- Пометить узел, текущая позиция которого равна 0, как x, найти координаты меньшего элемента в левом и правом потомках x и пометить его как y, сравнить x с y, если x меньше y, то x и y меняются позициями
- Повторяйте шаг 2, пока конечный узел или конец не превысит y.

Роль кучи

Куча может реализовывать приоритетные очереди, и в реальной жизни также есть приложения приоритетных очередей, например, при очередях пожилые люди и дети будут идти в начало очереди первыми.

расширять

d вилка куча

Полное d-ичное дерево с наименьшим корнем. Можно представить, что наша куча — это бинарная куча, и это d может быть 2, 3, 4

куча индексов

Куча, которую мы обсуждали выше, предназначена для сравнения данных каждого узла.Если эти данные представляют собой очень большую структуру данных, это займет очень много времени. В это время мы можем использовать кучу индексов и использовать массив индексов для хранения позиции элемента данных на основе исходной кучи, то есть куча индексов содержит два массива

Биномиальная куча

Биномиальная куча — это набор биномиальных деревьев. Биномиальное дерево также является древовидной структурой, K-е дерево биномиального дерева имеет 2k узлов, а высота равна k, узлы с глубиной d имеют всего 1 узел. Биномиальная куча состоит из набора биномиальных деревьев.

Есть также кучи Фибоначчи, кучи сопряжения и многое другое.

дерево сегментов

Дерево отрезков также является сбалансированным бинарным деревом, но его узлы несколько отличаются от узлов сбалансированного бинарного дерева.Каждый его узел можно рассматривать как составленный из массива. Если массив узла равен [l, r ] и его левый дочерний элемент, а его правый дочерний элемент значением является значение массива space [l, mid] и [mid+1, r] (значение здесь означает дерево, полученное [left, right] в соответствии с вашими пожеланиями, вы можете ввести лево*право или можно лево+право), середина обычно принимается как l+(rl)/2

Взгляните на ключевые поля дерева сегментов:

    //tree表示线段树中的所有节点，和层次遍历的顺序一样，和堆的物理结构一样
    //上图中tree[0]就是0-7的值，tree[3]就是0-1的值
    private int[] tree;

Роль дерева отрезков

Деревья сегментов могут решать некоторые алгоритмические задачи, такие как

Окрашивая диапазон (который может покрыть исходный цвет), M timester окрашивается, спрашивая, сколько цветов можно увидеть в интервале [i, j]
Найдите общее количество небесных тел в определенном интервале пространства
Даны n чисел, n

Если используется структура дерева отрезков, есть удобная идея для решения вышеуказанных проблем.

Предположим здесь, что мы хотим решить значение [1,7], мы можем напрямую получить дерево[8]+дерево[4]+дерево[2]+, то есть [1,1]+[2,3] +[4,7 ], чтобы получить значение [1,7]. Если вы используете метод двоичного дерева поиска для 0-7 и добавляете его от 1 до 7, это будет сложностью 7 * O (logn).

Операции над деревьями сегментов

Дерево сегментов в основном предназначено для запроса и модификации, и мы не обсуждаем добавление и удаление.

Запрос

Вот прямой взгляд на то, как работать, если вам нужно запросить интервал (запрос с одним элементом будет проще после понимания запроса интервала)

Вот пример, чтобы было легче понять Например, теперь я хочу запросить значение [1,7] и пусть искомое значение возвращает x:

Сначала выясните, является ли корневой узел [0,7] тем, что вы хотите найти, [1,7] не равен [0,7], левый интервал, который нужно найти, больше, чем левый интервал узла, сначала из левого поддерева [0, 3] Начните искать и разделите [1,7] на [1,3] и [4,7]
Начиная с левого поддерева [0,3], [1,3] и [0,3] не равны, левый интервал для поиска больше левого интервала узла, а затем поиск с левого интервала [ 0,1] узла, И разделить [1,3] на [1,1] и [2,3]
Начните поиск с левого поддерева как [0,1], так как это левое поддерево, [1,1] и [0,1] не равны, и делятся на [1,1] и [2,3 ] как указано выше, поэтому [0,1] нужно найти правильное поддерево [1,1]
В это время [1, 1] и [1, 1] равны, возврат [1, 1], соответствующий значению
Затем добавьте ранее возвращенные значения к [2, 3], [4, 7], оставшимся на предыдущих шагах, чтобы получить окончательное значение (поскольку [2, 3], [4, 7] находятся в узле It можно найти напрямую, поэтому нет необходимости снова делить его)

Значением [2,3] является дерево[4], значением [4,7] является дерево[2], а значением [1,1] является дерево[8].

Вероятно, процесс такой же, как описан выше, поначалу он может быть немного непонятным, но вполне понятно использовать рекурсию в сочетании с кодом.

Исправлять

Операция модификации такая же, как и идея запроса, но необходимо изменить пройденные узлы, поэтому я не буду здесь вдаваться в подробности.

Фактически, это может быть решено деревом отрезков.

TRIE TRIE.

Дерево словаря не является бинарным деревом, как и его имя, сначала посмотрите на структуру его узлов (Корневой узел не содержит символов, а c корневого узла пуст.)

class Node{
    char c;//当前节点的字符
    Node[] next;//当前节点的下一个节点
    boolean end;//判断这个字母是不是一个结尾
}

Мы можем обнаружить, что каждый узел словарного дерева состоит из нескольких указателей на следующий узел.Структура всего словарного дерева выглядит следующим образом:

Роль словарных деревьев

Можно видеть, что если вышеуказанный граф проходится в глубину в порядке, каждый листовой узел, который он проходит, является словом, таким как и, as, at, cn, com.

В предыдущей системе телефонной книги, если мы используем двоичное дерево поиска для сохранения информации о каждом контакте, предполагая, что наша адресная книга содержит 10 миллионов контактной информации, то мы можем запросить информацию об этом контакте по имени, что занимает очень много времени O (логин). И если мы используем дерево словаря, например, мы хотим запросить контакт с именем и, мы находим a в следующем через корневой узел, n в узле, а затем b в узле n (если здесь есть все английские буквы Тогда для следующего случая всего 26. В настоящее время наша временная сложность связана только с длиной слова O (K), а K — это длина слова. Тогда видно, что преимущества словарных деревьев в этом случае весьма очевидны. Конечно, такой дизайн словарного дерева также является типичной идеей обмена пространства на время.

Словарное дерево

Операции словарного дерева в основном сводятся к добавлению, удалению, проверке

Прежде чем начать, объясните функцию end.Например, у нас есть as и ass (smile.jpg), как мы определяем, имеет ли слово ass только ass или слово as? Нам нужно идентифицировать каждый узел, чтобы определить, является ли слово здесь полным словом. Например, ass, end in the last s должно быть истинным, потому что последнее s of ass — это конец ass. И если есть слово as, то первое s должно быть истинным, чтобы представлять, что слово as оканчивается на s.

Увеличивать

Добавленная логика очень проста, например, добавление гика

Найдите головной узел, определите, есть ли g в следующем, если нет, сначала создайте узел g (конец всех вновь построенных узлов равен false), затем добавьте его к следующему текущему узлу, а затем перейдите к узлу g.
Таким же образом оцените e, постройте и найдите следующий узел, затем e, затем k.
Когда мобильный узел k вставляется в конец типичного слова, мы устанавливаем значение true end

Удалить

Например, на изображении выше мы хотим удалить слово an

Достичь a через головной узел, и когда n будет достигнуто, если следующее из n не пусто, то изменить конец n на false.
Если следующий из n пуст, удалите n, вернитесь к предыдущему узлу и удалите значение n в следующем, а затем оцените, пуст ли следующий, и завершите, если он не пуст. Если он пуст, удалите a и конец.

найти

Например, теперь мы хотим найти и

Найти A, существование, текущий узел транспонирования узла A через NEXT корневого узла
Определите следующий узел узла, чтобы найти n, если он существует, текущий узел переносится на узел n
Судят, что следующий узел n узла находит d, существует, и текущий узел переносится на узел d. В это время искомое слово достигло конца, а затем судят, является ли конец d истинным Если оно истинно, значит, оно найдено, иначе не найдено.

и проверить

Набор поиска объединения представляет собой древовидную структуру, также известную как «непересекающийся набор», которая поддерживает набор непересекающихся динамических наборов, каждый набор идентифицируется представителем, представитель является членом набора, обычно корень выбирается как этот представитель.

Роль конкатенации

Он может решить проблемы с подключением, состояние подключения узла в сети и проблемы с путями.

Например, например, у нас есть несколько городов, и между разными городами могут быть соединенные дороги, эти города рассматриваются как узлы, а потом какие города могут быть связаны друг с другом.

Структура Союза

Как показано на рисунке, мы рассматриваем каждый узел как город.

Сначала посмотрите на картинку слева, которая является картинкой перед слиянием Мы можем сказать, что d и c связаны, g и e связаны, а c и f не связаны.

Если мы хотим соединиться между городом b и городом f в это время, мы не можем напрямую соединить b и f, мы должны добавить корневой узел f к корневому узлу d, тогда корневым узлом f здесь будет e, корень узел b — это a, то есть пусть a будет непосредственно родительским узлом e, как показано на рисунке.

Мы видим, что логическая структура объединения представляет собой древовидную структуру, но каждый узел имеет только свой родительский узел.

И проверить работу

Поскольку поиск профсоюза в основном для решения проблемы нахождения пути, поиск соответствующего профсоюза требует операции ISConnect, чтобы определить, подключены два узла. Если два узла могут быть подключены позже, то операция Union требуется для подключения двух узлов

Определить, связаны ли узлы

boolean isConnect(Node p, Node q)

Благодаря приведенному выше анализу мы знаем, что основным сравнением для определения того, связаны ли узлы, является корневой узел, поэтому, пока мы получаем корневой узел p и корневой узел q, мы можем судить, являются ли эти два узла такой же.

Слияние узлов

void unionElements(Node p, Node q)

Как и в начальном анализе, мы можем сначала получить корневой узел p-узла, а затем получить корневой узел q-узла, так что родительский узел корневого узла q-узла указывает на корневой узел p-узла. узел.

расширять

сжатие пути

Там могут быть все узлы в цепочке, и мы можем сделать все дерево в два слоя. Как показано

В следующей главе будут обобщены AVL, красно-черное дерево, дерево B+.