Структура данных Java и дерево алгоритмов. оглавление

Структура данных Java и дерево алгоритмов. оглавление

1. 2-3-4 дерева введение

2. Поиск 2-3-4 дерева

3. Вставьте

1. Узел разделения

2. Раскол корня

4. Завершите реализацию исходного кода

5. 2-3-4 дерева и красное черное дерево

①, соответствующие правила

②, эквивалент операции

6. Продуктивность 2-3-4 дерева

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

1. 2-3-4 дерева введение

Каждый узел дерева 2-3-4 имеет максимум четыре байтовых точки и три элемента данных. Числовое значение 2, 3 и 4 в имени относится к числу дочерних узлов, которые может содержать узел. Существует три возможных сценария для неконечных узлов:

① узел с элементом данных всегда имеет два дочерних узла;

② узел с двумя элементами данных всегда имеет три дочерних узла;

③ узел с тремя элементами данных всегда имеет четыре дочерних узла;

Короче говоря, число дочерних узлов неконечного узла всегда на 1 больше, чем элементов данных, которые он содержит. Если количество дочерних узлов равно L, а количество элементов данных равно D, то: L = D + 1

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

Очень важным моментом в древовидной структуре является соотношение значения ключа между узлами. В двоичном дереве все узлы со значением ключа меньше определенного значения узла находятся в поддереве с корневым левым дочерним узлом этого узла, а все узлы со значением ключа больше определенного значения узла находятся в правом дочернем узле этого узла. Корень на поддереве. Правило дерева 2-3-4 такое же, и добавляются следующие пункты:

Для удобства описания используйте цифры от 0 до 2 для нумерации элементов данных и цифры от 0 до 3 для нумерации дочерних узлов, как показано ниже:

Value Значение ключа всех дочерних узлов поддерева, корнем которого является child0, меньше, чем key0;

Value Значение ключа всех дочерних узлов поддерева, корнем которого является child1, больше, чем key0, и меньше, чем key1;

Value Значение ключа всех дочерних узлов поддерева, корнем которого является child2, больше, чем key1, и меньше, чем key2;

The. Значение ключа всех дочерних узлов поддерева, корнем которого является child3, больше, чем key2.

Упрощенная взаимосвязь показана на следующем рисунке: поскольку дублированные значения ключей обычно не допускаются в дереве 2-3-4, нет необходимости рассматривать случай сравнения одинаковых значений ключей.

2. Поиск 2-3-4 дерева

Поиск элементов данных с определенными значениями ключевых слов аналогичен поиску в двоичном дереве. Начните поиск с корневого узла. Если значение ключа, которое вы ищете, не является корневым, выберите соответствующий диапазон для значения ключа и поворачивайте его в этом направлении, пока не найдете его.

Например, для следующей картинки нам нужно найти элемент данных со значением ключа 64.

Во-первых, начиная с корневого узла, корневой узел имеет только один элемент данных 50, который не найден, и, поскольку 64 больше 50, перейдите к дочернему узлу child1 корневого узла. 60 | 70 | 80 не найден, а 60

3. Вставьте

Новые элементы данных обычно вставляются в конечные узлы внизу дерева. Если вы вставите в узел, имеющий дочерние узлы, номер дочернего узла изменится, чтобы сохранить структуру дерева, потому что в дереве 2-3-4 число дочерних узлов на 1 больше, чем элементов данных.

Иногда операция вставки является относительно простой, но иногда она очень сложна.

Бинарные деревья примеры использования. Двоичное дерево

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

Для практических целей обычно используют два подвида двоичных деревьев — двоичное дерево поиска и двоичная куча .

Существует следующее рекурсивное определение двоичного дерева (см. БНФ ):

 ::= ( ) | null .

То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной) или конечным (терминальным) узлом.

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

(m 
 (e 
 (c 
 (a null null)
 null
 )
 (g 
 null
 (k null null)
 )
 )
 (s
 (p (o null null) (s null null) )
 (y null null)
 )
 )

Красно-черное дерево Java. Red Black Tree Java

Red Black Tree is a special type ofthat has self-balancing behavior. Each node of the Red-Black Tree has an extra bit, which is always interpreted as color. In order to maintain the balancing of the Red-Black Tree during insertion, updation, and deletion, these red and black colors are used. In Red Black Tree:

1. Each node should have either the color red or black.
2. The root node should always be black.
3. A red node should not have a parent and child having red color.
4. Each path from a node to any of its descendant's NULL nodes has the same number of black nodes.

Algorithm to insert an element in Red Black Tree

When we insert a node in the Red-Black Tree, it always inserts with color bit 0, i.e., Red. In case when the Red-Black Tree violates its property after inserting a node, we should have to perform the following two operation.

1. Maintaining the colors of the node.

The algorithm of inserting a node in the Red-Black Tree is given below.

1. Let x and y are the root and leaf node of the Red-Black Tree.
2. Check whether the root node is empty or not. If the root node is not empty, the inserting node will be added as a root node with color bit 1, i.e., black.
3. Else, we will compare the root node element with the inserting node element. If it is greater than the root node element, traverse through the right subtree else, traverse the left subtree.
4. Repeat steps 3 until the leaf node is not reached.
5. Make leaf node's parent as a parent of inserting node.
6. If the leaf node element is lesser than the inserting node element, make inserting node as leftChild.
7. Else, make inserting node as rightChild.
8. For the right and left children of that inserting node, we assign NULL to both of them.
9. Set bit 0, i.e., Red color to that newly inserted node.

Algorithm to maintain Red Black Tree after insertion

1. Perform the following steps until the parent p of the inserted node become RED.
2. If the parent of the inserted node is the left child of the grandparent node of z, perform the following steps:
   1. Case-1:
      1. When the color of the right child of z's grandparent is RED, make both the grandparent node's children BLACK and make the grandparent as RED.
      2. Assign the grandparent node to the newly inserted node
   2. Case-2:
      1. Else if the newly inserted node is the right child of the parent node p, assign p to the newly inserted node.
      2. Perform the left-rotation for the newly inserted node.
   3. Case-3:
      1. Make parent node p as BLACK and grandparent node as RED.
      2. Performs the right-rotation for that newly inserted node.
3. Else, perform the following steps.
   1. If the left child of z's grandparent node is RED, make both the grandparent node's children BLACK and the grandparent node RED.
   2. Assign grandparent node to the newly inserted node.
   3. Else if the newly inserted node is the left child of the parent p, assign the parent node to the newly inserted node and perform the right rotation for that new node.
   4. Make parent node p as BLACK and grandparent node as RED.
   5. Perform the left rotation for the grandparent node.
4. Make the root node BLACK.

Бинарное дерево поиска python. Insertion of a node in Binary Search Tree

While inserting a node in a binary search tree, three conditions may arise.

1. The Binary search tree can be empty. i.e. Root itself will be a value None.
2. The Value to be inserted is less than the root.
3. The value to be inserted is greater than the root.

To implement the first condition, we just make a new node and declare it as root. To implement second and third condition, We follow the following approach.

From the properties of a binary search tree, we can see that each sub tree is a binary search tree in itself. Thus we can consider each node as a root of another binary tree.

While inserting a new node, if the value of the new data is less than the value of the current node, we will add it to the left child of the binary search tree, otherwise, we will add it to the right child.

Proceeding recursively, we will always reach the first condition and then we will declare a new node and add the node to the binary search tree.

Following is the implementation of above approach.

Бинарное дерево поиска. Дерево поиска, наивная реализация

Бинарное дерево поиска обладает следующим свойством: если $x$ — узел бинарного дерева с ключом $k$ , то все узлы в левом поддереве должны иметь ключи, меньшие $k$ , а в правом поддереве большие $k$ .

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

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

Обход дерева поиска

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:

$\backslash mathrm\{inorderTraversal\}$ — обход узлов в отсортированном порядке, $\backslash mathrm\{preorderTraversal\}$ — обход узлов в порядке: вершина, левое поддерево, правое поддерево, $\backslash mathrm\{postorderTraversal\}$ — обход узлов в порядке: левое поддерево, правое поддерево, вершина.

 func inorderTraversal(x : Node ): if x != null inorderTraversal(x.left) print x.key
 inorderTraversal(x.right)

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 3 4 6 7 8 10 13 14 .

 func preorderTraversal(x : Node ) if x != null print x.key
 preorderTraversal(x.left)
 preorderTraversal(x.right)

При выполнении данного обхода вершины будут выведены в следующем порядке: 8 3 1 6 4 7 10 14 13 .

 func postorderTraversal(x : Node ) if x != null postorderTraversal(x.left)
 postorderTraversal(x.right) print x.key

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 4 7 6 3 13 14 10 8 .

Данные алгоритмы выполняют обход за время $O(n)$ , поскольку процедура вызывается ровно два раза для каждого узла дерева.

Поиск элемента

Поиск элемента 4

Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы $O(h)$ , где $h$ — высота дерева.

Поиск минимума и максимума

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

Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время $O(h)$ .

Поиск следующего и предыдущего элемента

Реализация с использованием информации о родителе

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

Обе операции выполняются за время $O(h)$ .

Реализация без использования информации о родителе

Рассмотрим поиск следующего элемента для некоторого ключа $x$ . Поиск будем начинать с корня дерева, храня текущий узел $current$ и узел $successor$ , последний посещенный узел, ключ которого больше $x$ .
Спускаемся вниз по дереву, как в алгоритме поиска узла. Рассмотрим ключ текущего узла $current$ . Если $current.key\; \backslash leqslant\; x$ , значит следующий за $x$ узел находится в правом поддереве (в левом поддереве все ключи меньше $current.key$ ). Если же $x\; \backslash lt\; current.key$ , то $x\; \backslash lt\; next(x)\; \backslash leqslant\; current.key$ , поэтому может быть следующим для ключа , либо следующий узел содержится в левом поддереве . Перейдем к нужному поддереву и повторим те же самые действия.
Аналогично реализуется операция поиска предыдущего элемента.

Вставка

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

Реализация с использованием информации о родителе

 func insert(x : Node , z : Node ):// x — корень поддерева, z — вставляемый элемент while x != z.key > x.key x.right != x = x.right z.parent = x
 x.right = z z.key 
 Реализация без использования информации о родителе 
Время работы алгоритма для обеих реализаций — $O(h)$ .

Виды деревьев Java. Концепция одного дерева и сценарии применения

Дерево - это абстрактный тип данных (ADT) или структура данных, реализующая этот абстрактный тип данных, и используется для моделирования сбора данных с природой древовидной структуры. Это иерархический набор, состоящий из n (n> 0) конечных узлов. Ставить
Его называют «деревом», потому что оно выглядит как перевернутое дерево, что означает, что его корни обращены вверх, а листья обращены вниз.

Дерево имеет следующие характеристики:

• Каждый узел имеет ноль или более дочерних узлов;
• Узел без родительского узла называется корневым узлом;
• Каждый некорневой узел имеет один и только один родительский узел;
• За исключением корневого узла, каждый дочерний узел можно разделить на несколько непересекающихся поддеревьев;

Понятия, связанные с деревьями

• Степень узла: количество поддеревьев, содержащихся в узле, называется степенью узла;
• Степень дерева: степень самого большого узла в дереве называется степенью дерева;
• Конечный узел или конечный узел: узел с нулевой степенью;
• Нетерминальные узлы или узлы ветвления: узлы, степень которых не равна нулю;
• Родительский узел или родительский узел: если узел содержит дочерние узлы, этот узел называется родительским узлом его дочернего узла;
• Дочерний узел или дочерний узел: корневой узел поддерева, содержащегося в узле, называется дочерним узлом узла;
• Родственные узлы: узлы с одним и тем же родительским узлом называются родственными узлами;
• Уровень узла: начиная с определения корня, корень является первым уровнем, дочерние узлы корня - вторым уровнем и так далее;
• Глубина: для любого узла n глубина n - это единственная длина пути от корня до n, а глубина корня равна 0;
• Высота: для любого узла n высота n является наибольшей длиной пути от n до листа, а высота всех листьев равна 0;
• Двоюродный узел: Узлы, родительский узел которых находится на том же уровне, являются двоюродными братьями;
• Предки узла: все узлы на ветви от корня до узла;
• Потомки: любой узел в поддереве с корнем на узле называется потомком этого узла.

Структура дерева программирование. Деревья поиска

Связанные определения:

• Родитель вершины $v$ — вершина, из которой есть прямая ссылка в $v$.
• Дети (дочерние элементы, сын, дочь) вершины $v$ — вершины, в которые из $v$ есть прямая ссылка.
• Предки — родители родителей, их родители, и так далее.
• Потомки — дети детей, их дети, и так далее.
• Лист (терминальная вершина) — вершина, не имеющая детей.
• Поддерево — вершина дерева вместе со всеми её потомками.
• Степень вершины — количество её детей.
• Глубина вершины — расстояние от корня до неё.
• Высота дерева — максимальная из глубин всех вершин.

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

Деревья также используются в.

Бинарные деревья поиска

Бинарное дерево поиска (англ. binary search tree , BST) — дерево, для которого выполняются следующие свойства:

• У каждой вершины не более двух детей.
• Все вершины обладают ключами , на которых определена операция сравнения (например, целые числа или строки).
• У всех вершин левого поддерева вершины $v$ ключи не больше , чем ключ $v$.
• У всех вершин правого поддерева вершины $v$ ключи больше , чем ключ $v$.
• Оба поддерева — левое и правое — являются двоичными деревьями поиска.

Более общим понятием являются обычные (не бинарные) деревья поиска — в них количество детей может быть больше двух, и при этом в «более левых» поддеревьях ключи должны быть меньше, чем «более правых». Пока что мы сконцентрируемся только на двоичных, потому что они проще.

Чаще всего бинарные деревья поиска хранят в виде структур — по одной на каждую вершину — в которых записаны ссылки (возможно, пустые) на правого и левого сына, ключ и, возможно, какие-то дополнительные данные.

Сбалансированное дерево Java. Объяснение принципа вставки

Давайте сначала посмотрим на первую ситуацию:

Узел c, который является желтым узлом, является вновь вставленным узлом. В это время дерево не сбалансировано и нуждается в управлении. Согласно оценке коэффициента баланса каждого узла (см. Код), нам нужно повернуть направо и затем налево. Здесь каждый узел был помечен соответствующим образом, соответствующим шагом является порядок выполнения кода.

Я делаю интерпретацию кода только один раз, и соответствующие картинки сзади смотрят на себя.

Сначала мы входимinsert()Метод, на этот раз должен быть новый узел c. Выполнение до начала тела метода

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

 // При возврате из процесса вставки вычисляем коэффициент баланса
 root.balance = calcBalance(root); 

Рассчитайте остаток узла b, который равен 1. Следующие два, если суждения пропущены, а баланс узла b рассчитывается как 1, а глубина - 2.

Что случилось в это время?

Мы из узлаinsert()Начало метода

если ветвь выпрыгнула (потому что когда мы вставили, у a есть правильное поддерево b, таким образом это вошло в узел b в то времяinsert()метод).
Затем вычислите баланс узла a, который равен -2, и введите вторую ветвь if

А баланс узла b равен 1, что соответствует условиям и запускает праворукую операцию. Метод вводаright_rotate()в.
В это время p является узлом b, поэтому, как показано на рисунке выше, выполните эту правую операцию в порядке кода.

 // правая рука private void right_rotate(AVLNode p){ // Узлы, вовлеченные в одну ротацию, включают деда, отца, правого сына AVLNode pParent = p . parent ;
 AVLNode pLeftSon = p . left;
 AVLNode pRightGrandSon = pLeftSon . right; // Левый сын становится отцом pLeftSon . parent = pParent; // осталось 1 на картинке if (pParent != ){ (p pParent left){
 pParent left pLeftSon; } (p pParent right){
 pParent right pLeftSon; 
 }
 }

 pLeftSon right p; p pLeftSon; p left pRightGrandSon; (pRightGrandSon ){
 pRightGrandSon p;
 }

 p depth calcDepth(p);
 p balance calcBalance(p);

 pLeftSon depth calcDepth(pLeftSon);
 pLeftSon balance calcBalance(pLeftSon);
 }

Далее введите левый методleft_rotate()Обратите внимание, что p-узел в это время является a-узлом.
Как отмечено на правой стороне рисунка выше, еще раз посмотрите на последовательность выполнения кода:

 private void left_rotate(AVLNode p){ // Узлы, участвующие в выборе, включают деда, отца и левого сына AVLNode pParent = p . parent ;
 AVLNode pRightSon = p . right;
 AVLNode pLeftGrandSon = pRightSon . left; // правильный сын становится отцом pRightSon . parent = pParent; // справа 1 на картинке if (pParent ){ (p pParent right){
 pParent right pRightSon;
 } (p pParent left){
 pParent right pRightSon;
 }
 }

 pRightSon left p; p pRightSon; p right pLeftGrandSon; (pLeftGrandSon ){
 pLeftGrandSon p;
 }

 p depth calcDepth(p);
 p balance calcBalance(p);

 pRightSon depth calcDepth(pRightSon);
 pRightSon balance calcBalance(pRightSon);
 }

На этом этапе весь процесс вставки завершен.

Далее мы рассмотрим две ситуации.

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

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