Как пример Википедии несбалансированного дерева AVL действительно несбалансированный?
Я узнал, что случилось. У меня был
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))
somewhere. This messed up with something in the common.h
Defining this after the include of the common.h solved the problem.
I dont know why this only happens on XCode 9+
3 ответа
Чтобы быть сбалансированным, каждый узел в дереве должен, также,
- не имейте никаких детей, (быть "листовым" узлом)
- Имейте двух детей.
Или, если это имеет только одного ребенка, тот ребенок должен быть листом.
В диаграмме Вы отправили, 9, 54 и 76 нарушают последнее правило.
Правильно сбалансированный, дерево было бы похоже:
Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76
ОБНОВЛЕНИЕ: (после того, как почти 9 лет, я составил прохладную таблицу онлайн для графика в draw.io),
Узел 76 является несбалансированным, например, потому что его правильное поддерево имеет высоту 0, и левый имеет высоту 3.
Интуитивно, это - потому что это не как можно меньше. например, 12 должен быть родитель 9 и 14. Как это, 9 не имеет никакого левого поддерева, таким образом, это вне баланса. Дерево является иерархической структурой данных, таким образом, правилу нравится "балансируемый", часто относятся к каждому узлу и не только корневому узлу.
Вы корректны, корневой узел сбалансирован, но не все узлы дерева.