577
правок
Изменения
→Оригинальные
[[Файл:konsp.jpg|350px|thumb|Ослабленное красно-чёрное дерево.]]
Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Останется ли оно после этого Докажем, что при таком условии не будут выполняться и некоторые другие свойства красно-черным? черных деревьев. При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Из-за этого может возникнуть ситуация, в которой подряд будут идти две красные вершины. То же самое может произойти из-за перекрашиваний возле корня. Если мы продолжим вставлять элементы подобным образом, свойства дерева перестанут выполняться, и оно перестанет быть сбалансированным. Таким образом, время выполнения некоторых операций ухудшится.
На примере можно видеть, что после добавления вершины <tex>F</tex> и соответствующих перекрашиваний вершина <tex>B</tex> становится красной с красным родителем. Дальше добавим вершину <tex>G</tex>. Так как мы добавляем ее к черной вершине, все свойства дерева сохраняются без перекрашиваний. Но добавим после этого вершину <tex>H</tex>. Тогда вершина <tex>D</tex> станет красной (<tex>F</tex> и <tex>G</tex> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
