Алгоритм красно черного дерева сложность

Давайте раскрасим город в красный (или черный) цвет! Простое введение в красно-черные деревья в Python

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

Это потрясающе! Но…..есть предостережение. Все алгоритмы основаны на предположении, что данные будут поступать в случайном порядке. Это может быстро стать препятствием, если порядок поступления входных данных только увеличивается или уменьшается. Двоичные деревья поиска добавляют элементы к себе слева, если добавляемый элемент имеет значение меньше, чем предыдущее значение, и вниз справа, если элемент имеет значение, превышающее предыдущее значение. Если поступающие значения начинают напоминать отсортированные значения, это может эффективно превратить часть нашего хорошо сбалансированного дерева в то, что по сути равносильно связному списку, превращая наше хорошее O(log n) в O(n) и разрушая нашу эффективность.

Так как же нам решить эту проблему? Один из подходов заключается в использовании одного из элементов семейных структур данных, известных как самобалансирующиеся деревья, в данном случае мы сосредоточимся на красно-черных деревьях!

Как эти деревья работают и сохраняют свою структуру

Теория красно-черных деревьев связана с цветами и поворотами. Итак, давайте начнем с этого. В то время как базовое бинарное дерево предназначено только для хранения входных данных в виде прихода и , и надеется, что эти входные данные сохранят структуру, к которой стремится дерево, красно-черные деревья стремятся поддерживать сбалансированный порядок, не влияя на сложность методов, используемых для выполнения операций. в теме. В этой структуре данных это выполняется путем окрашивания каждого узла в дереве в черный или красный цвет и проверки того, что самый глубокий путь в дереве (высота дерева) не превышает в два раза путь к кратчайшему.

Давайте рассмотрим некоторые свойства красно-черных деревьев!

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

Эти свойства гарантируют, что операции с деревьями останутся постоянными O (log n) независимо от порядка поступления входных данных, что делает этот алгоритм очень эффективным для хранения, поиска, вставки и удаления. Имея это в виду, давайте взглянем на некоторые из методов!

Методы красно-черного дерева со сложностью

метод is_red

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

метод is_black(необязательно)

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

метод поиска

добавить метод

• O(log n) то же, что и обычное бинарное дерево
• Когда узел добавляется и является листом, его дочерние элементы автоматически создаются с нулевыми значениями и окрашиваются в черный цвет.
• Что отличает этот метод от обычного добавления в двоичном дереве поиска, так это то, что если какое-либо из свойств дерева (перечисленных в разделе выше) нарушается, необходимо будет выполнить вращение для повторной балансировки дерева, и, следовательно, сохранить все операции в O (log n). Вращения рассматриваются в следующих трех методах ниже, и это может быть либо левое, либо правое вращение.

метод fix_tree_after_add

• Этот метод всегда будет работать в (O)n из-за необходимости рекурсивно вызывать эту функцию для проверки состояния узлов в дереве до тех пор, пока они не будут исправлены и дерево не будет удовлетворять всем требуемым свойствам красно-черного дерева, как указано в предыдущий раздел. Эта работа также включает в себя обновление ссылок на узлы в данном дереве с помощью поворотов, описанных ниже.
• Это то, что делает и сохраняет красно-черное дерево и его структуру в целости!
• После добавления этот метод проверяет цвет родительского узла узла и родительских родителей noes, чтобы убедиться, что цвет деревьев узла в порядке правильный, это означает, что если узел прочитан, то его дочерние элементы должны быть черными, и что корневой узел красный. Это может включать перекрашивание узлов, чтобы убедиться, что дерево по-прежнему сбалансировано. Это может также включать ротацию узлов, чтобы убедиться, что все узлы находятся на одном уровне и что все узлы NIL имеют одинаковое количество родителей до корневого узла. Вращение описано ниже.

Вращения — это основа того, почему любое хорошее самобалансирующееся дерево остается сбалансированным. потому что дерево может быстро стать несбалансированным из-за нерандомизированных входных данных, которые либо по существу превращают часть этого дерева в связанный список, либо что определенные узлы NIL после вставки могут не иметь одинакового количества родительских узлов, ведущих к тому же корню. Вращения, если необходимо, выполняются после каждого добавления (или удаления), чтобы убедиться, что работа никогда не «нагромождается». Поскольку мы обновляем только ссылки на узлы, этот шаг выполняется в (O)1 для любого необходимого количества поворотов.

• повернуть_влево
• Это превращает левое поддерево брата в правое поддерево узла.
• На рисунках ниже показано движение влево ссылок узлов из одного поддерева в родительское другое поддерево.

• повернуть_вправо
• Это превращает правое поддерево брата в левое поддерево узла. ,
• На рисунках ниже показано движение вправо ссылок узлов из одного поддерева в родительское другое поддерево.

ПОЛНЫЙ РАЗДЕЛ РЕАЛИЗАЦИИ КОДА

**Обратите внимание, что некоторые комментарии были удалены из-за форматирования среды, для получения полных комментариев, пожалуйста, обратитесь к моему github внизу)**

#!/usr/bin/python class NilNode(object): """ The nil class is specifically for balancing a tree by giving all traditional leaf noes tw children that are null and waiting to be filled """ def __init__(self): self.red = False NIL = NilNode() # Nil is the sentinel value for nodes class RBNode(object): """ Class for implementing the nodes that the tree will use For self.color: red == False black == True If the node is a leaf it will either """ def __init__(self,data): self.red = False self.parent = None self.data = data self.left = None self.right = None class RedBlackTree(object): """ Class for implementing a standard red-black trees """ def __init__(self): self.root = None def add(self,data,curr = None): """ :param data: an int, float, or any other comparable value :param curr: :return: None but midifies tree to have an additional node """ new_node = RBNode(data) # Base Case - Nothing in the tree if self.root == None: new_node.red = False self.root = new_node return # Search to find the node's correct place currentNode = self.root while currentNode != None: potentialParent = currentNode if new_node.data < currentNode.data: currentNode = currentNode.left else: currentNode = currentNode.right # Assign parents and siblings to the new node new_node.parent = potentialParent if new_node.data < new_node.parent.data: new_node.parent.left = new_node else: new_node.parent.right = new_node self.fix_tree_after_add(new_node) def contains(self,data, curr=None): """ :return: """ if curr == None: curr = self.root while curr != NIL and data != curr.key: if data < curr.data: curr = curr.left else: curr = curr.right return curr def fix_tree_after_add(self,new_node): """ This method is meant to check and rebalnce a tree back to satisfying all of the red-black properties :return: None, but modifies tree """ while new_node.parent.red == True and new_node != self.root: if new_node.parent == new_node.parent.parent.left: uncle = new_node.parent.parent.right if uncle.red: new_node.parent.red = False uncle.red = False new_node.parent.parent.red = True new_node = new_node.parent.parent else: if new_node == new_node.parent.right: new_node = new_node.parent self.left_rotate(new_node) new_node.parent.red = False new_node.parent.parent.red = True self.right_rotate(new_node.parent.parent) else: uncle = new_node.parent.parent.left if uncle.red: new_node.parent.red = False uncle.red = False new_node.parent.parent.red = True new_node = new_node.parent.parent else: if new_node == new_node.parent.left: new_node = new_node.parent self.right_rotate(new_node) new_node.parent.red = False new_node.parent.parent.red = True self.left_rotate(new_node.parent.parent) self.root.red = False def rotate_left(self,new_node): """ :return: """ print("Rotating left!") sibling = new_node.right new_node.right = sibling.left # Turn sibling's left subtree into node's right subtree if sibling.left != None: sibling.left.parent = new_node sibling.parent = new_node.parent if new_node.parent == None: self.root = sibling else: if new_node == new_node.parent.left: new_node.parent.left = sibling else: new_node.parent.right = sibling sibling.left = new_node new_node.parent = sibling def rotate_right(self,new_node): """ :return: """ print("Rotating right!") sibling = new_node.left new_node.right = sibling.right # Turn sibling's left subtree into node's right subtree if sibling.right != None: sibling.right.parent = new_node sibling.parent = new_node.parent if new_node.parent == None: self.root = sibling else: if new_node == new_node.parent.right: new_node.parent.right = sibling else: new_node.parent.left = sibling sibling.right = new_node new_node.parent = sibling def get_all_nodes(self): """ :return: """ pass def is_red(self): """ This is the class that usually decides that a node is wither red or black, some implementations take the extra bit and will implement an is_black method for additional clarity. Generally, True == Red and False == Black :return: """ return self.root != None and self.root.red == 1; def is_black(self): """ Note that this method is not necessary as some implementations only check is the is_red class method is True or False :return: True if the node is black or is a leaf """ return self.root != None and self.root.black == 1;

Ссылка на код, показанный в этой статье:

Источник