Являются ли деревья AVL всегда подмножеством красно-черных деревьев?

Question

Я ищу доказательство того, что все деревья AVL могут быть окрашены как красно-черное дерево? Кто-нибудь может дать доказательство?

Answer 1

По определению R / B деревья могут быть немного менее сбалансированными, чем AVL-s, так как | maxPath - minPath | должно быть <= 1 для AVL и maxPath <= 2 * minPath для R / B, так что не каждый R / B является AVL, но с другой стороны, для AVL не нужно иметь пустые поддеревья, поэтому </p>

     4
    / \
   3   6
  /\   /\
 1  E 5  8

- это совершенно законный AVL, и он не является R / B, потому что R / B не может содержать листья и должен заканчиваться пустыми деревьями, которые всегда окрашены в черный цвет, так что вы не можете раскрасить дерево выше. Чтобы сделать это R / B, вам разрешено конвертировать каждый лист x в узел E x E и затем следуйте этим правилам: Дерево R / B: Должен быть BST должен содержать только узлы и пустые деревья, которые окрашены в черный или красный цвет Каждый красный узел имеет черных детей Все пустые деревья черные Для данного узла все пути к пустым деревьям должны иметь одинаковое количество черных узлов. Любой лист можно заменить узлом, левые и правые поддеревья которого пусты Макс. Путь T ≤ 2 * Мин. Путь T

Кстати, только что понял, что это покрасило мои узлы и листья в красный - это не было предназначено. Karol

Answer 2

Я подозреваю, что ответ - нет.

Деревья AVL балансируют лучше, чем деревья RB, что означает, что они балансируют по-разному, а это скорее означает, что вы не можете раскрасить каждое дерево AVL как действительное дерево RB.

Answer 3

Ответ - да, каждое дерево AVL может быть окрашено в красно-черный цвет, и обратное утверждение не выполняется.

Я точно не понял, КАК это сделать, и также ищу доказательства.

Answer 4

Хорошо, я дам вам подсказку

Посмотрите: Дерево AVL и Красно-черное дерево , если вы понимаете это, доказательство должно быть тривиальным.