Максим Фатин | про IT

Что не так с деревьями?

В чём вообще суть любой алгоритмической задачи? Найти оптимальное решение, которое будет эффективно работать на больших данных.

И это правило везде одно: решил не оптимально с точки зрения Big O — НА ВЫХОД!

Но почему-то это правило обошло деревья стороной...

Окей, окей — вот условие задачи прямо с собеса:

Дан корень правильного бинарного дерева поиска и число k. Нужно вернуть k-й наименьший элемент в дереве (отсчёт начинается с 1).

Бинарное дерево — значит, у каждой вершины не более двух детей.

Дерево поиска — значит, все элементы в левом поддереве меньше текущего, а в правом — больше.

Короче, вот пример дерева — и всё сразу станет ясно:


      4  
    /   \  
   2     6  
  / \   / \  
 1   3 5   7

Пусть k = 3. Тогда третий наименьший элемент — это 3, именно её и нужно вернуть по условию.

Чтобы решать задачи на деревья, нужно знать три обхода: preorder, inorder, postorder.
Они позволяют обойти все вершины дерева в определённом порядке.

Для примера выше:


preorder: 4, 2, 1, 3, 6, 5, 7  
inorder: 1, 2, 3, 4, 5, 6, 7  
postorder: 1, 3, 2, 5, 7, 6, 4

Заметил? inorder выдал отсортированный порядок — и это не совпадение!

Если дерево — правильное бинарное дерево поиска, то inorder всегда выдаёт отсортированную последовательность.

Реализация inorder-обхода:


from typing import *  
class TreeNode:  
    def __init__(self, val=0, left=None, right=None):  
        self.val = val  
        self.left = left  
        self.right = right  

def traversal(node: Optional[TreeNode], result: List[int]) -> None:  
    if node is None:  
        return  
    traversal(node.left, result)  
    result.append(node.val)  
    traversal(node.right, result)  

def inorder_traversal(root: Optional[TreeNode]) -> List[int]:  
    result = []  
    traversal(root, result)  
    return result

Простое решение задачи:
1. Запускаем inorder и получаем отсортированный список.
2. Возвращаем k-й элемент (с индексом k - 1).

Оценка: время — O(n), память — O(n).

Но! Такое решение на собеседовании часто не принимают. Слишком много дополнительной памяти — хочется оптимальнее.

Какое решение ждут: нужно прямо во время обхода считать, какой элемент мы посещаем, и если он k-й — вернуть его сразу, не сохраняя все значения вершин дерева.


from typing import *  
class TreeNode:  
    def __init__(self, val=0, left=None, right=None):  
        self.val = val  
        self.left = left  
        self.right = right  

def smallest_bst_element(root: TreeNode, k: int) -> int:  
    def inorder(node: TreeNode) -> int:  
        if node is None:  
            return None  
        result = inorder(node.left)  
        if result is not None:  
            return result  
        nonlocal k  
        k -= 1  
        if k == 0:  
            return node.val  
        return inorder(node.right)  
    return inorder(root)

Оценка: время — O(n), память — O(n).

WTF? Почему такие же оценки, если вроде оптимизировали?

Пусть k = 1, а дерево выглядит вот так — «бамбук» с уклоном влево:

Видишь? Нам всё равно придётся спуститься в самый низ, чтобы достать единицу — самый минимальный элемент.

А память откуда O(n)? Из-за рекурсии, брат! Каждый рекурсивный вызов занимает место в стеке.

В худшем случае это O(h), где h — высота дерева, а если дерево вытянутое, то просто h = n.

P.S. продолжение через минуты

🌭7🍓4

3.36K views06:11