Всем привет, сегодня я хочу поговорить с вами о новой структуре данных под названием Treap.
Treap — это, по сути, BST (сбалансированное двоичное дерево поиска), то же самое, что и SBT, который мы представили ранее. Однако метод поддержания равновесия Трепа отличается от метода СБТ, есть некоторые отличия.Принцип Treap еще проще, поэтому, когда раньше STL не допускали к соревнованиям, вместо этого мы обычно писали Treap от руки.
Основы Treap
Поскольку это сбалансированное двоичное дерево поиска, ключевым моментом является баланс, поэтому основное внимание, естественно, уделяется тому, как поддерживать баланс дерева.
В Treap поддерживать баланс очень просто, есть всего одно предложение, т.е.Сохраняйте баланс дерева, сохраняя форму небольшой верхней кучи. Treap также назван в честь этого, потому что это комбинация Tree и Heap.
Давайте посмотрим на структуру узлов в Treap:
class TreapNode(TreeNode):
"""
TreeNode: The node class of treap tree.
Paramters:
key: The key of node, can be treated as the key of dictionary
value: The value of node, can be treated as the value of dictionary
priority: The priority of node, specially for treap structure, describe the priority of the node in the treap.
lchild: The left child of node
rchild: The right child of node
father: The parent of node, incase that we need to remove or rotate the node in the treap, so we need father parameter to mark the address of the parent
"""
def __init__(self, key=None, value=None, lchild=None, rchild=None, father=None, priority=None):
super().__init__(key, value, lchild, rchild, father)
self._priority = priority
@property
def priority(self):
return self._priority
@priority.setter
def priority(self, priority):
self._priority = priority
def __str__(self):
return 'key={}, value={}'.format(self.key, self.value)
TreeNode здесь является общим узлом древовидной структуры, которую я абстрагировал, которая включает в себя ключ, значение, lchild, rchild и отца. На этом основании TreapNode фактически добавляет атрибут приоритета.
Причина, по которой добавляется этот атрибут приоритета, состоит в том, чтобы поддерживать свойства его кучи и поддерживать баланс дерева, поддерживая свойства этой кучи. Для конкретного метода работы см. ниже.
CRUD Трепа
вставлять
Прежде всего, поговорим об операции вставки элементов Treap, на самом деле операция вставки элементов очень проста, то есть операция вставки элементов в обычном BST. Единственная проблема заключается в том, как сохранить баланс дерева.
Как мы уже говорили ранее, мы поддерживаем баланс, сохраняя свойства кучи, поэтому, естественно, возникнет новая проблема. Почему сохранение свойств кучи обеспечивает баланс?
Ответ очень прост, потому что когда мы вставляем, нам нужно вставить каждый NodeСлучайно прикрепить приоритет. Куча используется для поддержания этого приоритета, гарантируя, что корень дерева должен иметь наименьший приоритет. Именно потому, что этот приоритет является случайным, мыЭто может гарантировать, что вероятность того, что все дерево выродится в линейность, бесконечно мала..
Когда мы вставляем элементы и обнаруживаем, что природа кучи разрушена, нам нужно поддерживать ее с помощью операций ротации. В качестве простого примера на рисунке ниже, если приоритет узла B меньше, чем у D, для обеспечения характера кучи необходимо поменять местами B и D. Поскольку прямой обмен разрушил бы природу BST, мы используем операцию вращения.
После поворота мы обнаружили, что B и D поменялись местами, а приоритет A и E после поворота больше, чем D, поэтому все наше дерево все еще сохраняет свойства после поворота.
То же самое справедливо и для правостороннего вращения.На самом деле мы заметим, чтоЧтобы поменять местами левого ребенка и отца, требуется правое вращение, если нужно поменять местами правого ребенка и отца, необходимо левое вращение..
Вся операция вставки на самом деле представляет собой базовый процесс вставки BST, плюс оценка вращения.
def _insert(self, node, father, new_node, left_or_right='left'):
"""
Inside implement of insert node.
Implement in recursion.
Since the parameter passed in Python is reference, so when we add node, we need to assign the node to its father, otherwise the reference will lose outside the function.
When we add node, we need to compare its key with its father's key to make sure it's the lchild or rchild of its father.
"""
if node is None:
if new_node.key < father.key:
father.lchild = new_node
else:
father.rchild = new_node
new_node.father = father
return
if new_node.key < node.key:
self._insert(node.lchild, node, new_node, 'left')
# maintain
if node.lchild.priority < node.priority:
self.rotate_right(node, father, left_or_right)
else:
self._insert(node.rchild, node, new_node, 'right')
# maintain
if node.rchild.priority < node.priority:
self.rotate_left(node, father, left_or_right)
Предыдущая логика — это вставка BST, то есть размера текущего узла, который определяет, будет ли вставка слева или справа. Обратите внимание, что здесь мы добавляем логику обслуживания после завершения вставки, по сути, это сравнение того, разрушает ли только что выполненная вставка природу кучи. Может быть, кто-то из моих одноклассников хочет спросить меня,Зачем поддерживать только один раз здесь? Возможно, что приоритет вставки очень мал, и его нужно прокрутить до самого корня дерева, не так ли?
Это правда, но не забывайте, что наша логика обслуживания вызывается не один раз. Поскольку вся рекурсия возвращается назад, она фактически выполняет логику обслуживания один раз на каждом уровне дерева. Следовательно, можно гарантировать, что он сохраняется от места вставки до корня дерева.
Запрос
Запрос очень прост.Излишне говорить, что это операция запроса BST, и никаких изменений.
def _query(self, node, key, backup=None):
if node is None:
return backup
if key < node.key:
return self._query(node.lchild, key, backup)
elif key > node.key:
return self._query(node.rchild, key, backup)
return node
def query(self, key, backup=None):
"""
Return the result of query a specific node, if not exists return None
"""
return self._query(self.root, key, backup)
Удалить
Операция удаления немного более хлопотная, потому что включает приоритетное обслуживание, но логику понять несложно, просто имейте в виду необходимость обеспечения природы кучи.
Прежде всего, есть два очень простых случая, один из которыхУдаляемый узел является конечным узлом., это легко понять, его удаление не повлияет на другие узлы, просто удалите его напрямую. Второй случай — узел цепи,То есть у него есть только один дочерний элемент, поэтому его удаление не приведет к изменениям., просто примите его дочерний элемент к его родителю, и свойства всей кучи и BST не будут затронуты.
Помимо этих двух случаев, у нас нет возможности удалить его напрямую, потому что это неизбежно повлияет на природу кучи. Вот очень умный способ сделать этоСначала поверните удаляемый узел, поверните его в конечный узел или узел цепочки, а затем удалите его..
Во время этого процесса нам нужно сравнить приоритеты двух его дочерних элементов, чтобы убедиться, что природа кучи не повреждена.
def _delete_node(self, node, father, key, child='left'):
"""
Implement function of delete node.
Defined as a private function that only can be called inside.
"""
if node is None:
return
if key < node.key:
self._delete_node(node.lchild, node, key)
elif key > node.key:
self._delete_node(node.rchild, node, key, 'right')
else:
# 如果是链节点,叶子节点的情况也包括了
if node.lchild is None:
self.reset_child(father, node.rchild, child)
elif node.rchild is None:
self.reset_child(father, node.lchild, child)
else:
# 根据两个孩子的priority决定是左旋还是右旋
if node.lchild.priority < node.rchild.priority:
node = self.rotate_right(node, father, child)
self._delete_node(node.rchild, node, key, 'right')
else:
node = self.rotate_left(node, father, child)
self._delete_node(node.lchild, node, key)
def delete(self, key):
"""
Interface of delete method face outside.
"""
self._delete_node(self.root, None, key, 'left')
Исправлять
Операция модификации также очень проста: мы можем напрямую найти соответствующий узел и изменить его значение.
вращать
Давайте также вставим код операции вращения, на самом деле логика здесь такая же, как и операция вращения, представленная в предыдущем SBT, и код в основном такой же:
def reset_child(self, node, child, left_or_right='left'):
"""
Reset the child of father, since in Python all the instances passed by reference, so we need to set the node as a child of its father node.
"""
if node is None:
self.root = child
self.root.father = None
return
if left_or_right == 'left':
node.lchild = child
else:
node.rchild = child
if child is not None:
child.father = node
def rotate_left(self, node, father, left_or_right):
"""
Left rotate operation of Treap.
Example:
D
/ \
A B
/ \
E C
After rotate:
B
/ \
D C
/ \
A E
"""
rchild = node.rchild
node.rchild = rchild.lchild
if rchild.lchild is not None:
rchild.lchild.father = node
rchild.lchild = node
node.father = rchild
self.reset_child(father, rchild, left_or_right)
return rchild
def rotate_right(self, node, father, left_or_right):
"""
Right rotate operation of Treap.
Example:
D
/ \
A B
/ \
E C
After rotate:
A
/ \
E D
/ \
C B
"""
lchild = node.lchild
node.lchild = lchild.rchild
if lchild.rchild is not None:
lchild.rchild.father = node
lchild.rchild = node
node.father = lchild
self.reset_child(father, lchild, left_or_right)
return lchild
Единственное, что здесь следует отметить, это то, что, поскольку Python хранит все ссылки, мы должны перезаписать значение в родительском узле после того, как операция поворота вступила в силу. Мы обязаны изменить ссылку узла, но старый адрес все еще хранится в отце и не вступает в силу.
постскриптум
По сути, здесь представлен принцип всего Treap.Конечно, кроме основных операций, которые мы только что представили, в Treap есть и некоторые другие операции. НапримерЕго можно разделить на два Treap или объединить два Treap в один.. Вы также можете найти K-й самый большой элемент и так далее. Я не использую многие из этих дополнительных операций, поэтому я не буду их описывать, если вам интересно, вы можете узнать о них.
TREAP Эта структура данных также мало используется на практике, в целом или на главной сцене соревнований, мы узнаем, что в основном это в основном для повышения нашей структуры данных и способности осуществлять способность реализовывать код. TREAP Его самое большое преимущество просто, не слишком много сложных операций, но мы также сказали, что это контролировать баланс дерева случайным приоритетом, то этоОчевидно, что идеального баланса не существует, есть только наихудший сценарий., но нет гарантии, что вы попадете в лучший сценарий. Однако для бинарного дерева разница в глубине дерева не сильно отличается. Поэтому производительность Treap не так уж плоха, и это очень экономичная структура данных.
Наконец, это старое правило, я помещаю полный код в пасту, вы можете нажать, если вам интересночитать оригиналПроверяйте, в коде есть подробные комментарии, всем должно быть понятно.
Вот и все, что касается сегодняшней статьи, и я искренне желаю вам удачи каждый день. Если вам все еще нравится сегодняшний контент, пожалуйста, зайдите на одинТройная поддержкабар~(Нравится, подписывайтесь, делайте репост)