LINUX.ORG.RU

История изменений

Исправление Arrest, (текущая версия) :

Мне этот текст ничего не дал.

Очень жаль, в нем говорится насколько сильно и почему они расслабляют балансировку.

Можно ли записать математически, когда вершина красная?

Ну, на самом деле, цвета это иллюзия.

Самыми первыми появились B-деревья с вполне приятными свойствами и удобное балансировкой. Их простейший подвид, наиболее удобный для работы в оперативной памяти – двоичное B-дерево, в вершинах которого либо указатель-значение-указатель, либо у-з-у-з-у (понятно как отсортированные). Логично что одновременно хочется и хранить все узлы одинаково, и не тратить два слова на нули: для этого можно хранить все узлы как у-з-у, а для больших вершин завести еще один фиктивный узел и повесить его в правый указатель настоящего.

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

Осталось два шага: во-первых, разрешить расширять узлы не только направо, но и налево, получая мега-узлы с тремя значениями и 4 указателями вниз; а во-вторых покрасить настоящие узлы в черный, а расширения в красный.

Книгу Сэджвика можно и не читать, но хотя бы его статью, где он первый (окей, как соавтор) придумывает красить 2-3-4 деревья в красные и черные цвета, стоило.

Исходная версия Arrest, :

Мне этот текст ничего не дал.

Очень жаль, в нем говорится насколько сильно и почему они расслабляют балансировку.

Можно ли записать математически, когда вершина красная?

Ну, на самом деле, цвета это иллюзия.

Самыми первыми появились B-деревья с вполне приятными свойствами и удобное балансировкой. Их простейший подвид, наиболее удобный для работы в оперативной памяти – двоичное B-дерево, в вершинах которого либо указатель-значение-указатель, либо у-з-у-з-у (понятно как отсортированные). Логично что одновременно хочется и хранить все узлы одинаково, и не тратить два слова на нули: для этого можно хранить все узлы как у-з-у, а для больших вершин завести еще один фиктивный узел и повесить его в правый указатель настоящего.

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

Осталось два шага: во-первых, разрешить расширять узлы не только направо, но и налево, получая мега-узлы с тремя значениями и 4 указателями вниз; а во-вторых покрасить настоящие узлы в черный, а расширения в красный.

Книгу Сэджвика можно и не читать, но хотя бы его статью, где он первый (окей. с соавтором) придумывает красить 2-3-4 деревья в красные и черные цвета, стоило.