#java #tree #binary-tree #avl-tree #red-black-tree
#java #дерево #двоичное дерево #avl-дерево #красно-черное дерево
Вопрос:
У меня простой вопрос, в основном из-за того, что мой мозг перестал работать на меня. Можно ли считать это деревом AVL? Также можно ли считать это красно-черным деревом?
Я считаю, что это не было бы деревом AVL, потому что оно не выглядит должным образом сбалансированным, но я не уверен, правильно ли это.
Я также не уверен, является ли это красно-черным деревом по тем же причинам.
Ответ №1:
Согласно википедии, деревья AVL представляют собой тип самобалансирующегося бинарного дерева поиска, где разница в высоте от корня до любых двух листьев составляет не более одного. В вашем случае разница между высотой листа «f» и высотой листа «m» равна 2. Следовательно, это не AVL-дерево.
Красно-черные деревья хранят в каждом из своих листьев информацию о цвете, красном или черном — я не вижу такой информации в вашем прикрепленном дереве, так что это тоже не дерево RB.
Редактировать:
Согласно комментарию sprinter, дерево может быть деревом RB с не отображаемыми цветами, поскольку расстояние до самого глубокого листа не более чем в два раза превышает расстояние до самого мелкого листа.
Комментарии:
1. Я бы добавил небольшое предостережение ко второму пункту в ответе: ключевым свойством дерева RB является то, что расстояние от корня до самого глубокого листа не более чем в два раза превышает расстояние до самого мелкого листа. Это верно для этого дерева, поэтому оно потенциально может быть RB-деревом с не показанными цветами.
2. Спасибо, я смотрел на это, и кажется, что оно действительно соответствует параметрам красно-черного дерева
3. Хорошая точка @sprinter, я обновил ответ, чтобы отразить его.