Как бы вы реализовали сбалансированное дерево с отложенными удалениями?

Question

Более конкретно, дерево AVL. Является ли это возможным? Я хотел бы сделать это, но я думаю, что с удаленными узлами может быть проблематично управлять вращениями.

У меня есть один, который работает нормально, но я бы хотел использовать его с отложенным удалением для чего-то другого.

Answer 1

Что именно не удаляет означает в контексте дерева AVL?

Это может означать, что вы не работаете над удалением, то есть вы вообще не обновляете дерево.

Это приведет к неправильной перебалансировке дерева, так как сканирование коэффициентов баланса будет работать с неправильными коэффициентами баланса.

Это может означать обновление коэффициентов баланса, но не балансирование.

Это означает, что в конечном итоге вы решите удалить что-то с коэффициентами баланса больше 2 или меньше -2; что предполагает несколько поворотов, чтобы исправить. Проблема здесь заключается в том, что вы больше не можете знать при ротации, удалили ли вы глубину поддерева; потому что, хотя вы знаете, что, скажем, 3 глубины поддерева слишком много на одной стороне, вы больше не знаете, что это точно один элемент, вызывающий каждый уровень этой дополнительной глубины - то, что вы обычно знаете, потому что вы добавляете или удаляете отдельные элементы за раз - так что вы не знаете, сколько вращений вам нужно сделать. Вы можете сделать три поворота и потерять только одну глубину поддерева, потому что на этой глубине было два элемента. На самом деле, как бы вы могли знать , какие элементы вращать, чтобы получить необходимые элементы? они не обязательно все существуют в пути от выбранного вами элемента удаления и в точке, где коэффициент баланса равен 3.

Я не уверен, но я выйду на конечности и скажу, что ленивый удаляет разрывы AVL, как мы его знаем.

Почему вы хотите отложить, в любом случае? весь смысл AVL состоит в том, чтобы амортизировать стоимость перебалансировки по каждому добавлению / удалению, чтобы вы оставались в O (log n) - зачем наращивать долг перебалансировки для более крупной, менее частой перебалансировки?

Answer 2

Если вы хотите, чтобы он оставался «сбалансированным» по отношению ко всем узлам (включая помеченные как удаленные), вам не нужно ничего делать - вы уже там.

Если вы хотите, чтобы он оставался «сбалансированным» по отношению к набору неосуществленных узлов - вопрос состоит в том, почему? Весь смысл балансировки состоит в том, чтобы предотвратить побег (линейный наихудший случай) поиски и это зависит от узлов, а не от статуса их удаления.