Как найти k-й наименьший элемент в BST, если дерево может часто изменяться?

Я работаю над проблемой 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+». Другая структура данных, которая соответствует описанию проблемы, но не упоминается в вопросе, будет работать нормально.

BST можно превратить в дерево статистики заказов . (Чтобы это было преимуществом, «запросы ранга/порядка» также должны быть достаточно частыми.)

greybeard 13.09.2023 10:01

@greybeard Я думаю, что BST должен быть сбалансирован, иначе пострадают другие операции. Итак, я предполагаю, что B-дерево, размер каждого поддерева которого хранится в каждом узле, должно обеспечивать O (log n) для всех операций.

Abhijit Sarkar 13.09.2023 10:06

«Можем ли мы найти k-й наименьший элемент в дереве B+ быстрее, чем O(n)»: B+дерево и BST — это разные структуры, а структура LeetCode предоставила определение класса узлов BST и спрашивает, когда «BST часто модифицируется», поэтому я не думаю, что намерение состоит в том, чтобы переключиться на другую структуру данных, например B+дерево. Короче говоря: действительно ли ваш вопрос - это последняя строка вашего поста?

trincot 13.09.2023 10:21

@trincot «действительно ли ваш вопрос в последней строке вашего сообщения?» Да, это так, но если бы я не установил контекст, мой вопрос был бы отклонен и закрыт в кратчайшие сроки. Что касается вашего комментария, я не думаю, что последующие действия обязательно ограничивают или навязывают какую-то конкретную структуру. Структура узла, которую вы видели, была для исходного вопроса.

Abhijit Sarkar 13.09.2023 10:27

Конечно, но там все равно написано «Если BST часто модифицируется». Не «если выбранная вами структура данных часто изменяется». Но ладно, я понимаю, что вам нужен ответ не о BST, а о B+tree. Но тогда вам действительно нужно изменить название вашего вопроса.

trincot 13.09.2023 10:32

@trincot Я хочу получить ответ на свой вопрос, и мне все равно, какое B*-дерево оно использует. Если бы у меня были предпочтения, я бы вообще не задавал этот вопрос :)

Abhijit Sarkar 13.09.2023 10:33

Извините, что настаиваю, но вы спрашиваете: «А можем ли мы найти k-й наименьший элемент в дереве B+ быстрее, чем O(n)?». Это специфично для B+дерева, а не для какой-либо структуры данных? Читая ваш комментарий, я теперь не понимаю, о чем вы здесь спрашиваете.

trincot 13.09.2023 10:33

Справедливо, пожалуйста, посмотрите мое обновление. Надеюсь, это разрешит путаницу.

Abhijit Sarkar 13.09.2023 10:35

Хорошо, это проясняет ситуацию.

trincot 13.09.2023 10:39
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
9
63
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Дерево AVL/красно-черное дерево с размером поддерева, хранящимся в каждом узле, обеспечивает O(log n) для всех операций. Это превращает дерево в дерево статистики заказов.

https://en.m.wikipedia.org/wiki/Order_statistic_tree

https://www.baeldung.com/cs/red-black-tree-vs-avl-tree

Ответ принят как подходящий

Вы можете сделать это с помощью 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), общая идея имеет смысл и согласуется с тем, что обсуждалось. пока в комментариях.

Abhijit Sarkar 13.09.2023 20:39

Другие вопросы по теме