Как красно-черные деревья изоморфны 2-3-4 деревьям?

У меня есть базовое представление о красно-черных деревьях и 2-3-4 деревьях, а также о том, как они поддерживают баланс высот, чтобы гарантировать, что в худшем случае операции будут O (n logn ).

Но я не могу понять этот текст из Википедии

2-3-4 деревья являются изометрией красно-черных деревьев, что означает, что они являются эквивалентными структурами данных. Другими словами, для каждого 2-3-4 дерева существует как минимум одно красно-черное дерево с элементами данных в том же порядке. Более того, операции вставки и удаления на 2-3-4 деревьях, которые вызывают расширение, разбиение и слияние узлов, эквивалентны переворачиванию цвета и повороту в красно-черных деревьях.

Я не понимаю, насколько операции эквивалентны. Верна ли эта цитата в Википедии? Как можно увидеть, что операции эквивалентны?

5
задан Lazer 5 March 2012 в 08:30
поделиться