Изменения

===Оригинальные===Красно-чёрным называется бинарное поисковое дерево, у которого каждому узлу сопоставлен дополнительный атрибут {{---}} цвет и для которого выполняются следующие свойства (англ. ''red-black properties''):

Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Останется ли оно после этого красно-черным? При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Из-за этого может возникнуть ситуация, в которой подряд будут идти две красные вершины. Если мы продолжим вставлять элементы подобным образом, свойства дерева перестанут выполняться и оно перестанет быть сбалансированным. Таким образом, время выполнения некоторых операций ухудшится. ===Альтернативные===В книге Кормена "Алгоритмы: построение и анализ" дается немного иное определение красно-черного дерева, а именно: '''красно-чёрное дерево''' {{---}} это двоичное дерево поиска, вершины которого разделены на красные и черные. Таким образом, каждая вершина хранит один дополнительный бит {{---}} её цвет. При этом должны выполняться определенные требования, которые гарантируют, что глубины любых двух листьев отличаются не более, чем в два раза, поэтому дерево можно назвать сбалансированным (англ. ''balanced'').

По Кормену двоичное Двоичное дерево поиска является красно-чёрным, если обладает следующими свойствами:

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