История изменений
Исправление Arrest, (текущая версия) :
Мне этот текст ничего не дал.
Очень жаль, в нем говорится насколько сильно и почему они расслабляют балансировку.
Можно ли записать математически, когда вершина красная?
Ну, на самом деле, цвета это иллюзия.
Самыми первыми появились B-деревья с вполне приятными свойствами и удобное балансировкой. Их простейший подвид, наиболее удобный для работы в оперативной памяти – двоичное B-дерево, в вершинах которого либо указатель-значение-указатель, либо у-з-у-з-у (понятно как отсортированные). Логично что одновременно хочется и хранить все узлы одинаково, и не тратить два слова на нули: для этого можно хранить все узлы как у-з-у, а для больших вершин завести еще один фиктивный узел и повесить его в правый указатель настоящего.
Дополнительный бит появляется ровно тут, когда нужно научиться отличать расширение этого узла от настоящего указателя вниз.
Осталось два шага: во-первых, разрешить расширять узлы не только направо, но и налево, получая мега-узлы с тремя значениями и 4 указателями вниз; а во-вторых покрасить настоящие узлы в черный, а расширения в красный.
Книгу Сэджвика можно и не читать, но хотя бы его статью, где он первый (окей, как соавтор) придумывает красить 2-3-4 деревья в красные и черные цвета, стоило.
Исходная версия Arrest, :
Мне этот текст ничего не дал.
Очень жаль, в нем говорится насколько сильно и почему они расслабляют балансировку.
Можно ли записать математически, когда вершина красная?
Ну, на самом деле, цвета это иллюзия.
Самыми первыми появились B-деревья с вполне приятными свойствами и удобное балансировкой. Их простейший подвид, наиболее удобный для работы в оперативной памяти – двоичное B-дерево, в вершинах которого либо указатель-значение-указатель, либо у-з-у-з-у (понятно как отсортированные). Логично что одновременно хочется и хранить все узлы одинаково, и не тратить два слова на нули: для этого можно хранить все узлы как у-з-у, а для больших вершин завести еще один фиктивный узел и повесить его в правый указатель настоящего.
Дополнительный бит появляется ровно тут, когда нужно научиться отличать расширение этого узла от настоящего указателя вниз.
Осталось два шага: во-первых, разрешить расширять узлы не только направо, но и налево, получая мега-узлы с тремя значениями и 4 указателями вниз; а во-вторых покрасить настоящие узлы в черный, а расширения в красный.
Книгу Сэджвика можно и не читать, но хотя бы его статью, где он первый (окей. с соавтором) придумывает красить 2-3-4 деревья в красные и черные цвета, стоило.