Я работаю над проблемой LeetCode 230: K-й наименьший элемент в BST. Мой код Python использует рекурсивный обход по порядку, и хотя он не имеет прямого отношения к этому вопросу, он приведен ниже для справки. В худшем случае это займет линейное время (O(n)
), если мы в конечном итоге посетим все узлы (k = n
).
def kth_smallest(root: Optional[TreeNode], k: int) -> int:
def dfs(node: TreeNode, count: int) -> tuple[int, int]:
"""
:param node: Current node
:param count: Number of nodes visited so far
:returns: a 2-tuple consisting of the number of nodes visited, and the value of the last visited node.
If the kth node is found, immediately returns the value of the kth node
"""
if node.left is not None:
# count is the number of nodes in the left subtree.
count, val = dfs(node.left, count)
if count == k:
return k, val
# count the current node.
count += 1
if count == k or node.right is None:
return count, node.val
return dfs(node.right, count)
assert root is not None
return dfs(root, 0)[1]
Далее следует следующий вопрос:
Если BST часто изменяется (т. е. мы можем выполнять операции вставки и удаления), и вам нужно найти k-ю наименьшую частоту, как бы вы оптимизировали?
Я думаю B+Дерево . Операции поиска/вставки/удаления выполняются за O(log n)
время. Запрос диапазона с элементами k
, встречающимися в диапазоне, требует O(k + log n)
времени.
Но можем ли мы найти k-й наименьший элемент в B+-дереве быстрее, чем O(n)
? Обратите внимание, что я упоминаю здесь дерево B+ в связи с моим комментарием «Я думаю о дереве B+». Другая структура данных, которая соответствует описанию проблемы, но не упоминается в вопросе, будет работать нормально.
@greybeard Я думаю, что BST должен быть сбалансирован, иначе пострадают другие операции. Итак, я предполагаю, что B-дерево, размер каждого поддерева которого хранится в каждом узле, должно обеспечивать O (log n) для всех операций.
«Можем ли мы найти k-й наименьший элемент в дереве B+ быстрее, чем O(n)»: B+дерево и BST — это разные структуры, а структура LeetCode предоставила определение класса узлов BST и спрашивает, когда «BST часто модифицируется», поэтому я не думаю, что намерение состоит в том, чтобы переключиться на другую структуру данных, например B+дерево. Короче говоря: действительно ли ваш вопрос - это последняя строка вашего поста?
@trincot «действительно ли ваш вопрос в последней строке вашего сообщения?» Да, это так, но если бы я не установил контекст, мой вопрос был бы отклонен и закрыт в кратчайшие сроки. Что касается вашего комментария, я не думаю, что последующие действия обязательно ограничивают или навязывают какую-то конкретную структуру. Структура узла, которую вы видели, была для исходного вопроса.
Конечно, но там все равно написано «Если BST часто модифицируется». Не «если выбранная вами структура данных часто изменяется». Но ладно, я понимаю, что вам нужен ответ не о BST, а о B+tree. Но тогда вам действительно нужно изменить название вашего вопроса.
@trincot Я хочу получить ответ на свой вопрос, и мне все равно, какое B*-дерево оно использует. Если бы у меня были предпочтения, я бы вообще не задавал этот вопрос :)
Извините, что настаиваю, но вы спрашиваете: «А можем ли мы найти k-й наименьший элемент в дереве B+ быстрее, чем O(n)?». Это специфично для B+дерева, а не для какой-либо структуры данных? Читая ваш комментарий, я теперь не понимаю, о чем вы здесь спрашиваете.
Справедливо, пожалуйста, посмотрите мое обновление. Надеюсь, это разрешит путаницу.
Хорошо, это проясняет ситуацию.
Дерево AVL/красно-черное дерево с размером поддерева, хранящимся в каждом узле, обеспечивает O(log n)
для всех операций.
Это превращает дерево в дерево статистики заказов.
Вы можете сделать это с помощью B+tree, B-tree, AVL, Red-Black, Skip List или другого эффективного отсортированного контейнера по вашему выбору.
Идея состоит в том, чтобы расширить узлы атрибутом size
, чтобы вы могли жадно решать, как перемещаться вниз по структуре к значению kth.
Поскольку вы начали с BST, вы можете превратить свой BST в дерево AVL (дополнив узлы атрибутом коэффициента баланса) и превратить его в дерево статистики заказов (дополнив узлы атрибутом размера).
В отличие от того, как LeetCode представляет свой BST, хорошей практикой является хранить корень в отдельном классе, чтобы вы могли определять в нем методы вставки/удаления и поддерживать концепцию пустого дерева.
Этот второй класс может выглядеть так:
class AugmentedAvl:
def __init__(self):
self.root = None
def insert(self, value):
self.root = AugmentedAvlNode.insert(self.root, value)
def delete(self, value):
self.root = AugmentedAvlNode.delete(self.root, value)
def kth_smallest(self, k):
if self.root and self.root.size >= k:
return self.root.kth_smallest(k)
def size(self):
return AugmentedAvlNode.sizeof(self.root)
Расширенный класс Node будет иметь большую часть логики:
class AugmentedAvlNode:
def __init__(self, val):
self.val = val
self.children = [None, None] # Can access through left,right getters/setters
self.bf = 0 # Balance factor should be -1, 0 or 1.
self.size = 1 # Number of nodes in the tree rooted by this node
@property
def left(self):
return self.children[0]
@left.setter
def left(self, value):
self.children[0] = value
@property
def right(self):
return self.children[1]
@right.setter
def right(self, value):
self.children[1] = value
@staticmethod
def sizeof(node):
return node.size if node else 0
def min(self):
return self.left.min() if self.left else self.val
def attach(self, side, child): # Does not take care of balance factors
self.children[side] = child
self.size = sum(map(self.sizeof, self.children)) + 1
return self
def adjust_balance(self, add_bf):
if self.bf != add_bf: # The balance factor update will stay in range
self.bf += add_bf
return self
# Imbalance would occur. Prepare for rotation:
side = (1 - self.bf) // 2
lifting = self.children[1-side]
if lifting.bf == -self.bf: # Inner grandchild is heavy: start double rotation
child, lifting = lifting, lifting.children[side]
self.bf, child.bf = (+(lifting.bf < 0), -(lifting.bf > 0))[::-self.bf]
lifting.bf = 0
lifting.children[1-side] = child.attach(side, lifting.children[1-side])
else: # Prepare simple rotation:
self.bf *= not lifting.bf
lifting.bf = -self.bf
# Finish rotation
return lifting.attach(side, self.attach(1-side, lifting.children[side]))
@classmethod
def insert(cls, node, value):
if not node: # Found the spot where to insert
return cls(value)
if node.val == value:
raise ValueError("insert({value}): tree already has this value")
side = value >= node.val
child = node.children[side]
orig_bf = child and child.bf
node.children[side] = cls.insert(child, value)
node.size += 1
if child and (orig_bf or child.bf == 0): # Height didn't change
return node
return node.adjust_balance((-1, 1)[side])
@classmethod
def delete(cls, node, value):
if not node:
raise ValueError("delete({value}): value not found in tree")
if node.val == value: # Found the node to delete
if not node.left or not node.right: # Simple case
return node.left or node.right
value = node.val = node.right.min() # Delete successor node instead
side = value >= node.val
child = node.children[side]
orig_bf = child and child.bf
child = node.children[side] = cls.delete(child, value)
node.size -= 1
if child and (child.bf or orig_bf == 0): # Height didn't change
return node
return node.adjust_balance((1, -1)[side])
def kth_smallest(self, k):
left_size = self.sizeof(self.left)
if k <= left_size:
return self.left.kth_smallest(k)
k -= left_size + 1
if k == 0:
return self.val
return self.right.kth_smallest(k)
Вот код, который тестирует приведенную выше реализацию:
class TestableAvl(AugmentedAvl):
def inorder(self, node=None):
node = node or self.root
if node:
if node.left:
yield from self.inorder(node.left)
yield node.val
if node.right:
yield from self.inorder(node.right)
def verify(self):
# inorder sequence must be sorted
values = list(self.inorder())
if values != sorted(values):
raise ValueError(f"Tree does not have a correct inorder sequence {values}")
self.verify_node(self.root)
def verify_node(self, node):
# balance factors and sizes must be correct
if not node:
return -1, 0 # height, size
left_height, left_size = self.verify_node(node.left)
right_height, right_size = self.verify_node(node.right)
height = max(left_height, right_height) + 1
bf = right_height - left_height
size = 1 + left_size + right_size
if node.size != size:
ValueError("Size inconsistent at node {self.val}")
if node.bf != bf or abs(bf) > 1:
ValueError("Balance factor inconsistent at node {self.val}")
return height, size
from random import shuffle
def main():
for i in range(30):
print(f"Running random test {i}")
lst = list(range(130))
shuffle(lst)
tree = TestableAvl()
for value in lst:
tree.insert(value)
tree.verify()
if tree.size() != len(lst):
raise ValueError("Tree does not have the expected size")
for k in lst:
if tree.kth_smallest(k + 1) != k:
raise ValueError("kth_smallest({k}) returns wrong value")
shuffle(lst)
for value in lst:
tree.delete(value)
tree.verify()
print("done")
main()
Конечно, существуют библиотеки, которые могут предложить эту функциональность. Существует SortedList , часть SortedContainers, который реализует __getitem__
, поэтому вы можете получить элемент kth с синтаксисом lst[k-1]
.
См. также: Есть ли в стандартной библиотеке Python модуль для сбалансированного двоичного дерева?
Спасибо, что нашли время. Хоть я и не изучал код критически построчно (и никто не сможет этого придумать во время собеседования, для чего и существует LeetCode), общая идея имеет смысл и согласуется с тем, что обсуждалось. пока в комментариях.
BST можно превратить в дерево статистики заказов . (Чтобы это было преимуществом, «запросы ранга/порядка» также должны быть достаточно частыми.)