577
правок
Изменения
→Свойства
Из свойств красно-черного дерева понятно, почему "глубины любых двух листьев отличаются не более, чем в два раза", поэтому определения можно считать эквивалентными.
Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Тогда корень всегда может быть изменен с красного на чёрный с сохранением всех свойствОстанется ли оно после этого красно-черным? При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Но вот при изменении цвета корня с чёрного на красный дерево Из-за этого может перестать удовлетворять свойствам <tex>3</tex> и <tex>4</tex>возникнуть ситуация, в которой подряд будут идти две красные вершины. Тогда даже если Если мы перекрасим все вершины такпродолжим вставлять элементы подобным образом, чтобы у красного узла не было красных потомковсвойства дерева перестанут выполняться и оно перестанет быть сбалансированным. Таким образом, свойство <tex>4</tex> все равно может не выполнятьсявремя выполнения некоторых операций ухудшится.
== Высота красно-черного дерева ==
