Деревья являются одним из наиболее распространенных абстрактных типов данных в CS, особенно бинарные деревья поиска и алгоритмы, которые выполняются с их структурой. В основном это связано с тем, что правильно сбалансированное базовое бинарное дерево поиска должно давать O(log n) времени для самых основных операций, то есть добавления, поиска и удаления элементов из дерева. дерево.
Это потрясающе! Но…..есть предостережение. Все алгоритмы основаны на предположении, что данные будут поступать в случайном порядке. Это может быстро стать препятствием, если порядок поступления входных данных только увеличивается или уменьшается. Двоичные деревья поиска добавляют элементы к себе слева, если добавляемый элемент имеет значение меньше, чем предыдущее значение, и вниз справа, если элемент имеет значение, превышающее предыдущее значение. Если поступающие значения начинают напоминать отсортированные значения, это может эффективно превратить часть нашего хорошо сбалансированного дерева в то, что по сути равносильно связному списку, превращая наше хорошее O(log n) в O(n) и разрушая нашу эффективность.
Так как же нам решить эту проблему? Один из подходов заключается в использовании одного из элементов семейных структур данных, известных как самобалансирующиеся деревья, в данном случае мы сосредоточимся на красно-черных деревьях!
Как эти деревья работают и сохраняют свою структуру
Теория красно-черных деревьев связана с цветами и поворотами. Итак, давайте начнем с этого. В то время как базовое бинарное дерево предназначено только для хранения входных данных в виде прихода и , и надеется, что эти входные данные сохранят структуру, к которой стремится дерево, красно-черные деревья стремятся поддерживать сбалансированный порядок, не влияя на сложность методов, используемых для выполнения операций. в теме. В этой структуре данных это выполняется путем окрашивания каждого узла в дереве в черный или красный цвет и проверки того, что самый глубокий путь в дереве (высота дерева) не превышает в два раза путь к кратчайшему.
Давайте рассмотрим некоторые свойства красно-черных деревьев!
- Каждый узел имеет цвет: черный или красный.
- Каждый лист, не содержащий данных, но предназначенный для сохранения структуры дерева (узел со значением NULL), окрашен в черный цвет. Их иногда называют дозорными узлами.
- Если узел окрашен в красный цвет, то оба его дочерних узла окрашены в черный цвет.
- Каждый путь вниз от узла к листу-потомку должен содержать одинаковое количество черных узлов.
Эти свойства гарантируют, что операции с деревьями останутся постоянными 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;
Ссылка на код, показанный в этой статье:
