577
правок
Изменения
→Оригинальные
Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Докажем, что при таком условии не будут выполняться и некоторые другие свойства красно-черных деревьев. При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Из-за этого может возникнуть ситуация, в которой подряд будут идти две красные вершины. То же самое может произойти из-за перекрашиваний возле корня. Если мы продолжим вставлять элементы подобным образом, свойства дерева перестанут выполняться, и оно перестанет быть сбалансированным. Таким образом, время выполнения некоторых операций ухудшится.
На примере можно видеть, что после добавления вершины с ключом <tex>F0</tex> и соответствующих перекрашиваний вершина с ключом <tex>B6</tex> становится красной с красным родителем. Дальше добавим вершину <tex>G5</tex>. Так как мы добавляем ее к черной вершине, все свойства дерева сохраняются без перекрашиваний. Но добавим после этого вершину <tex>H-3</tex>. Тогда вершина с ключом <tex>D4</tex> станет красной (<tex>F0</tex> и <tex>G5</tex> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
===Альтернативные===
