Эта статья является первой подписанной статьей сообщества Nuggets, и ее перепечатка без разрешения запрещена.
Структура данных - дерево, прибыл по расписанию, даже на несколько дней раньше, чем я думал, я редко хвалю то, что написал, но сегодня действительно полно галантереи, надеюсь, все могут лайкнуть и поддержать.
1. Основная концепция дерева
Дерево является особенно распространенной структурой данных, и древовидная структура данных часто используется в компьютерных файловых системах или системах компьютерных баз данных.
Например, в файловой системе древовидная структура данных используется в качестве уровня каталога файлов, а в системе базы данных древовидная структура данных используется в качестве индекса базы данных, особенно B-дерева.
Здесь я заимствовал определение из энциклопедии Baidu:
Деревоэтоструктура данных,это изп (п ≥ 1) конечные узлы образуют иерархическуюсобирать. Его называют «деревом», потому что оно выглядит как перевернутое дерево, что означает, что у него корни вверх, а листья вниз.
Я просто нарисовал рисунок, чтобы показать вам форму структуры данных дерева:
Каждый кружок на этом изображении представляет собой узел, а узел 1 в середине представляет собой корневой узел дерева.Вы можете видеть, что под узлом 1 есть три стрелки, указывающие на три узла соответственно.Эти три элемента являются тремя дочерними узлами. корневого узла, для дочерних узлов первый узел является их родительским узлом, каждый узел имеет свой собственный дочерний узел и родительский узел, и дочерние узлы разных узлов не будут перекрываться.
Каждый узел также может стать поддеревом независимо, например, узел 3 является поддеревом с 5 и 6 дочерними узлами под ним соответственно, а узлы 2 и 4 также можно назвать поддеревом, но у них нет дочерних узлов.
Далее есть несколько существительных о деревьях, которые нужно понять:
-
высота/глубина: Высота дерева — это длина от его корневого узла до самого глубокого узла.Например, высота дерева в моем примере выше равна 3, вы можете понимать это как 3 слоя.
-
листовой узел: узлы без подчиненных узлов называются листовыми узлами, такими как узлы 2, 4, 5 и 6.
-
нелистовой узел: Узлы с подчиненными узлами называются нелистовыми узлами, такими как узел 3.
-
степень узла: количество его непосредственных дочерних узлов. Например, узел 3 имеет только два дочерних узла, а его степень равна 2.
-
степень дерева: максимальная степень всех узлов в дереве. В приведенной диаграмме степень дерева равна 3. Поскольку узел 1 имеет три дочерних узла, никакой другой узел не имеет больше дочерних узлов, поэтому степень дерева равна 3.
После понимания основных концепций деревьев необходимо поговорить о том, как обычно строятся деревья.Поскольку количество прямых дочерних узлов дерева не фиксировано, мы можем использовать связанный список для построения дочернего узла, например:
public class DiyTree<T extends Comparable> {
private Node<T> root;
private static class Node<T extends Comparable> {
private LinkedList<Node<T>> item;
}
}
Это эквивалентно содержанию связанного списка под каждым узлом.Если это выражается в способе рисования, это выглядит так:
На картинке выше я использую прямоугольник вместо связанного списка, круг вместо элементов внутри, и каждый элемент может быть расширен в связанный список.
Выше деревья, которые я представил,N树, помимо дерева N, есть дерево, называемое бинарным деревом, давайте взглянем на его введение:
-
N-дерево: То есть дочернему узлу разрешено иметь дочерних узлов N. Дерево на картинке примера — это дерево N, а известное дерево B — разновидность дерева N.
-
бинарное дерево: То есть дочернему узлу разрешено иметь только 2 дочерних узла, и эти два дочерних узла часто называют левым узлом и правым узлом.
На приведенном выше рисунке показано двоичное дерево Структуру кода двоичного дерева также легче понять, чем дерево N, поскольку оно имеет только два дочерних узла:
public class DiyTree<T extends Comparable> {
private Node<T> root;
private static class Node<T extends Comparable> {
private T item;
private Node<T> left;
private Node<T> right;
public Node(T t) {
item = t;
}
}
}
Самая большая разница между деревом N и двоичным деревом заключается в том, что количество разрешенных дочерних узлов различно, а еще одним уровнем различия, вызванным числом, является высота дерева.
Например, у меня 7 узлов, и чтобы разместить их на бинарном дереве, нужно 3 слоя.В дереве N достаточно двух слоев.Чем больше узлов, тем больше высота дерева нужна бинарному дереву, а дерево N может быть очень низкая. Высота дерева поддерживает десятки миллионов данных (высота дерева индекса B+ в MySQL составляет 3 слоя), что очень полезно в программах, которым требуется доступ к дискам. Конечно, в центре внимания этой статьи сегодня будет по-прежнему находиться вокруг бинарного дерева.Дерево N временно не говорите.
2. Бинарное дерево поиска
В предыдущем разделе было кратко упомянуто понятие бинарного дерева, так для чего же оно используется?
Введение вещи должно иметь свою роль.Двоичное дерево часто используется в бинарном дереве поиска.Двоичное дерево поиска является деформацией бинарного дерева.Он выполняет поиск данных с временной сложностью O(logN).2,1 миллиарда ), для поиска любого элемента требуется всего 31 поиск.
Несмотря на то, что это так быстро, вы можете легко превратиться в бинарное дерево поиска с помощью бинарного дерева, потому что требуемые условия очень просты:
-
Бинарное дерево.
-
Левый узел меньше своего родительского узла, а правый узел больше своего родительского узла.
На приведенном выше рисунке дерево с белым фоном не является бинарным деревом поиска, а дерево с синим фоном — это бинарное дерево поиска, потому что дерево с белым фоном не удовлетворяет второму условию, упомянутому выше.
С помощью бинарного дерева поиска вы можете убедиться, что ваше дерево упорядочено, поэтому в процессе поиска элемента каждое сравнение может сократить диапазон поиска вдвое, поэтому его временная сложность составляет O(logN).
Например, если мы хотим найти элемент 1, нам нужно только сравнить корневой узел на приведенном выше рисунке, чтобы легко узнать, что 1 находится в ссылке слева от дерева, поэтому нам не нужно переходить к ссылку справа, чтобы найти его. , повторяя это действие рекурсивно, чтобы мы могли быстро найти нужный нам элемент.
Конечно, у бинарного дерева поиска есть и недостатки, типа вставляем по очереди1，0，2，3，4Вы обнаружите, что эти пять элементов образуют связанный список, и ваша скорость поиска станетO(N):
Есть ли способ решить эту проблему?
Да, то есть, когда его ссылка немного длинная, она один раз перенастраивается.Это самобалансирующееся бинарное дерево поиска называется бинарным сбалансированным деревом.
3. Двоичное сбалансированное дерево (AVL)
Этот раздел является самой важной и самой сложной частью этой статьи, и читатели должны обратить на него внимание.
В предыдущем разделе упоминалось, что бинарное сбалансированное дерево может решить проблему, заключающуюся в том, что бинарное дерево поиска слишком длинное за один проход.В этом разделе мы реализуем бинарное сбалансированное дерево.Метод реализации будет использовать самый классический AVL , что является более требовательным. Требуется, чтобы разница высот между двумя подузлами дерева не превышала 1, что также является довольно проблематичным решением.Красно-черное дерево, которое чаще используется в промышленности, не имеет таких строгих требований к балансу.
Причина, по которой эта схема выбрана для объяснения, состоит в том, что одна из них является классической, а другая — классической книгой по алгоритмам.Алгоритмы Четвертое изданиеНет упоминания об этой реализации AVL, поэтому я хотел бы добавить ее.
Давайте сначала посмотрим на изображение выше. Это изображение на самом деле представляет собой относительно обычное бинарное дерево. Левый слой корневого узла имеет высоту 1, а правый слой имеет высоту 2. Разница между ними не превышает 1, но равно 1.
Что, если я вставлю 4 в этот момент?
Хорошо видно, что две стороны дерева не сбалансированы, высота левого слоя корневого узла равна 1, а высота правого слоя равна 3. Разница больше 1.
Но мы не можем настроить корневой узел таким образом, мы должны продолжать искать несбалансированную точку от точки вставки и выполнять операцию балансировки в первом несбалансированном месте.
Новая точка вставки на рисунке равна 4, ее родительский узел равен 3, левый узел родительского узла не имеет элементов, его можно рассматривать как высоту слоя 0, а правый узел имеет 4, что можно рассматривать поскольку высота слоя равна 1, поэтому разница между ними равна 1, корректировка не требуется.
Затем перейдите к 2 в Интернете, левый узел 2 не имеет элементов, так как высота слоя равна 0, высота слоя правого узла равна 2, разница равна 2, поэтому узел, который действительно вызывает дисбаланс, — это узел 2, вы нужно настроить здесь, чтобы сбалансировать это дерево.
Итак, как его настроить?
Причина, по которой классика остается классикой, в том, что ее придумали некоторые мастера, которые испытали крещение временем и терпят долгое время.
В AVL предшественники суммировали дисбаланс четырех видов деревьев и с помощью метода, называемого旋转способ сбалансировать дерево.
Для более интуитивного понимания я не буду перечислять эти четыре ситуации напрямую, а объясню их одну за другой с помощью картинок.
3.1 Левое вращение
Как показано выше, правая ссылка в узле 2 длиннее левой, поэтому нам нужно выполнить поворот влево:
Сделайте его похожим на тот, что справа на изображении выше, чтобы все дерево вернулось в баланс, а левое вращение выглядело очень просто:
Это поместить несбалансированный узел на левый узел его дочерних узлов.
Поскольку узел 2 меньше узла 3, он размещается справа слева от узла 3.
Конечно, у некоторых людей могут возникнуть сомнения, что, если левый узел узла 3 имеет значение?
Этого не происходит в исходном примере, но если вы добавите еще один узел 5 к правому дереву на изображении выше, это произойдет:
Хорошо видно, что корневой узел 1 имеет дисбаланс, и мы используем левое вращение, чтобы исправить его, как обычно:
Мы помещаем корневой узел на левый узел узла 3, как обычно,И поместите левый узел исходного узла 3 на правый узел корневого узла., потому что все узлы под узлом 3 больше, чем корневой узел.
Таким образом, левое вращение, вероятно, состоит из следующих двух шагов:
-
Поместите несбалансированный узел слева от его дочерних элементов.
-
Поместите исходный левый узел его дочернего узла в правый узел несбалансированного узла.
3.2 Повернуть вправо
Правое вращение — это проблема зеркального отражения левого вращения:
Левое дерево явно несбалансировано в узле 9 и становится правой стороной после настройки правого вращения.
Его шаги и левое вращение также соответствуют:
-
Поместите несбалансированный узел справа от его дочерних узлов.
-
Поместите исходный правый узел его дочернего узла в левый узел несбалансированного узла.
Поймите левое вращение и, естественно, поймите правое вращение.Если здесь есть небольшая путаница, вы можете снова прочитать левое вращение, а затем вывести его самостоятельно.
3.3 Двойное вращение
Двойное вращение означает, что в определенной ситуации одно вращение не может решить проблему, поэтому для решения проблемы требуется два вращения.Двойное вращение можно разделить на два типа:
-
Повернуть влево и вправо: Поверните влево, а затем вправо.
-
Повернуть вправо и влево: Поверните вправо, а затем влево.
Давайте посмотрим на этот пример:
В этом примере очевидно, что узел 9 несбалансирован, и уровень его левого поддерева отличается от уровня его правого поддерева на 2, но если мы повернём его прямо вправо согласно нашему опыту выше, это не сработает:
Прямое правое вращение станет таким, все дерево все еще несбалансировано.
Потому что его несбалансированная форма на самом деле несколько отличается от примера с правым вращением, который я привел выше:
Левое дерево — это несбалансированная ситуация, которую мы можем решить правым вращением, тогда как правое дерево отличается, его узел 5 состоит в том, что высота правого слоя выше левого, а не левого слоя выше правого.
Можно видеть, что когда все дочерние узлы несбалансированного узла смещены в одну сторону, это можно решить только с помощью вращения.
Например, узлы 9 и 5 левого дерева на приведенном выше рисунке на самом деле смещены влево, поэтому их можно решить, повернув вправо.
И узел 2, и узел 3 на приведенном выше рисунке смещены вправо, поэтому их можно решить, используя левое вращение.
Однако на приведенном выше рисунке тот, который не весь смещен в одну сторону, требует двух поворотов.Неуравновешенный узел на приведенном выше рисунке — это узел 5, который смещен влево, а затем вправо, поэтому его необходимо повернуть. влево, а затем повернут вправо:
Однако при первом вращении влево дочерние узлы несбалансированного узла необходимо повернуть влево, а затем несбалансированный узел необходимо повернуть вправо.
На этой картинке я отметил узел первого поворота красным, а узел второго поворота желтым, вы легко можете увидеть его бегущие шаги.
Соответственно, есть и его проблема зеркального отображения, которую нужно решить вращением вправо-влево.
3.4 Реализация кода
AVL не сложен в теории, но при его реализации возникло много проблем.Прочитав код в книге несколько раз, он был реализован.Читатели могут копировать и запускать его напрямую.
Базовая структура АВЛ:
public class DiyTree<T extends Comparable> {
private Node<T> root;
private static class Node<T extends Comparable> {
private T item;
private Node<T> left;
private Node<T> right;
private Integer height = 0;
public Node(T t) {
item = t;
}
}
}
Базовая структура AVL на одну высоту больше, чем структура бинарного дерева поиска выше.
Затем выполните вставку данных:
public void add(T t) {
Node<T> node = new Node<>(t);
root = insertTree(root, node);
}
private Node<T> insertTree(Node<T> root, Node<T> node) {
if (root == null) {
return node;
}
int i = node.item.compareTo(root.item);
if (i > 0) {
root.right = insertTree(root.right, node);
} else if (i < 0){
root.left = insertTree(root.left, node);
} else {
// 节点相同暂不处理
}
// 插入之后进行平衡 会平衡从根节点往下的所有节点
return balance(root);
}
Вставка данных — это обычный поиск, затем вставка и балансировка после вставки:
private Node<T> balance(Node<T> root) {
// 平衡条件是计算左右子节点是否相差大于1
if (height(root.left) - height(root.right) > 1) {
if (height(root.left.left) >= height(root.left.right)) {
// 左左 - 使用右旋转
root = rightRotate(root);
} else {
// 左右 - 使用左右双旋转 - 先对root.left进行左旋转，再对root进行右旋转
root = leftRightRotate(root);
}
}
if (height(root.right) - height(root.left) > 1) {
if (height(root.right.right) >= height(root.right.left)) {
// 右右 - 使用左旋转
root = leftRotate(root);
} else {
// 右左 - 使用右左双旋转 - 先对root.right进行右旋转，再对root进行左旋转
root = rightLeftRotate(root);
}
}
root.height = Math.max(height(root.left), height(root.right)) + 1;
return root;
}
При балансировке балансировка выполняется от самого глубокого узла вверх, потому что метод вставки является рекурсивным методом, и при вставке есть четыре ситуации, которые решаются четырьмя поворотами соответственно.
Существует также вспомогательный метод для нахождения высоты:
private int height(Node<T> node) {
return node == null ? -1 : node.height;
}
Метод правого вращения:
private Node<T> rightRotate(Node<T> node) {
// 先拿到节点的左边
Node<T> newNode = node.left;
// 去掉这个新节点的右边
node.left = newNode.right;
// 新节点的右边给予原来的root
newNode.right = node;
// 处理高度
node.height = Math.max(height(node.left), height(node.right)) + 1;
newNode.height = Math.max(height(newNode.left), height(newNode.right)) + 1;
return newNode;
}
Поворот вправо и влево:
private Node<T> rightLeftRotate(Node<T> node) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
Наконец, вы можете вывести методы левого и левого вращения из моего метода правого вращения и метода вращения вправо влево. После того, как код написан, яvisualgoЭтот веб-сайт использует те же данные, что и мой локальный тестовый пример, чтобы проверить правильность кода.
Я протестировал два набора данных:1, 2, 3, 4, 5, 6, 7, 8, 9 и50, 45, 40, 55, 60, 47, 57, 35, 38 , эти два набора данных относятся ко всем ротациям, а результаты локального тестирования и результаты выполнения веб-сайта в Интернете совпадают.
4. Обход АВЛ
После разговора о вставке и балансе AVL, давайте поговорим о его обходе.Обход бинарного дерева можно разделить на следующие категории:
-
обход предварительного заказа: Сначала напечатайте корневой узел.
-
Неупорядоченный обход: После печати левого узла напечатайте корневой узел.
-
пост-порядковый обход: После печати левого и правого узлов, наконец, напечатайте корневой узел.
-
обход по уровням: Начиная с корня, печатать слой за слоем слева направо.
из первых трех обходов先、中、后Все они относятся к корневому узлу.Поняв это, вы можете легко преобразовать любой код обхода в другие коды обхода.
4.1 Обход предварительного заказа
Возьмите это изображение в качестве примера, если обход предварительного заказа, его результат должен быть:3, 1, 0, 2, 4, 5.
Код тоже очень простой:
public void preorder() {
if (root == null) {
return;
}
order(root);
}
public void order(Node<T> root) {
if (root == null) {
return;
}
System.out.println(root.item);
order(root.left);
order(root.right);
}
4.2 Непоследовательный обход
Возьмите это изображение в качестве примера, если обход по порядку, его результат должен быть:0, 1, 2, 3, 4, 5.
Код тоже очень простой:
public void preorder() {
if (root == null) {
return;
}
order(root);
}
public void order(Node<T> root) {
if (root == null) {
return;
}
order(root.left);
System.out.println(root.item);
order(root.right);
}
4.3 Обход после заказа
Возьмите это изображение в качестве примера, если обход после заказа, его результат должен быть:0, 2, 1, 5, 4, 3.
Код тоже очень простой:
public void preorder() {
if (root == null) {
return;
}
order(root);
}
public void order(Node<T> root) {
if (root == null) {
return;
}
order(root.left);
order(root.right);
System.out.println(root.item);
}
Видно, что коды этих трех методов обхода практически одинаковы, а что касается последнего одноуровневого обхода порядка, то тут каждый сам понимает~
5. Заключение
На этом очки знаний, связанные с деревьями, заканчиваются.
Сегодня я рассказал об основных концепциях деревьев, реализации бинарных деревьев поиска и AVL После изучения этой главы вы должны хорошо понимать структуру данных деревьев.
Двоичное сбалансированное дерево также является встроенным типом данных в современных языках программирования, таких как Java.TreeMapЭто типичный представитель бинарного дерева, а в JavaHashMapОн также будет преобразован, когда будет слишком много конфликтов.TreeMap, все они являются чрезвычайно важными инструментальными классами в Java.
В этой статье я говорил в общей сложности о пяти структурах данных, из которых бинарное сбалансированное дерево является самой быстрой структурой данных, а скорость его поиска и вставки достигла экспоненциального уровня, но есть также структура данных, которая может выполнять поиск. и вставить.Когда скорость достигает постоянного уровня, это Хэш.
Хэш, также известный как хеш-таблица, представляет собой структуру данных с постоянным уровнем поиска и вставки.Я подробно расскажу об этом в следующей статье, пожалуйста, подождите и посмотрите.