Дерево AVL: разница между глубинами листьев?

Question

Вопрос из теста:

Пусть T - дерево AVL, а x,y - два листа в дереве (x != y). Какое максимальное значение depth(x) - depth(y)?

A. 0
B. 1
C. 2
D. None of the above

Правильный (?) Ответ - D. Может ли кто-нибудь объяснить, почему это не B, поскольку одно из свойств AVL заключается в том, что height(a.left) - height(a.right) <= 1 для каждого узла a?

Answer 1

Общее объяснение требует больше времени, чем показ контрпримеров. Итак, рассмотрим следующее дерево Фибоначчи 8-го порядка, которое является деревом AVL:

Принимая глубину за количество ребер от корня до узлов, лист 0 имеет глубину 7, а лист 52 имеет глубину 4. Разница составляет 3. При других и более крупных деревьях AVL разница может быть больше.

Помните, что для дерева AVL характерно то, что различия между высотами левого и правого поддеревьев для каждого узла меньше или равны 1. Глубина - это другое.

Если честно, это сложный вопрос.

Answer 2

Дерево AVL гарантирует, что время поиска «наихудшего» случая равно O (log (n)). И это гарантирует, что самое большее разность высот любых двух поддеревьев - самое большее 1. Но это не гарантирует, что разность высот между самым низким и самым высоким узлом всего дерева будет 1. В большом дереве можно получить большое Перепад высот для дерева в целом.

Ключом к пониманию дерева AVL является понимание его определения «поддерева». Для любого данного узла есть 2 поддерева, которые иногда называют левым и правым поддеревьями. Разница высот между этими двумя поддеревьями не больше 1. Теперь представьте, что оба этих поддерева могут быть присоединены к узлу и стать одним поддеревом в еще большем дереве. Это новое поддерево, назовите его, левое поддерево узла будет иметь максимальную разность высот 1 с правым поддеревом на том же узле. Но это также означает, что максимальная разница высот между любыми двумя листьями во всем этом дереве будет равна 2. Этот процесс может быть повторен, и у деревьев AVL может быть большая разность высот между любыми листьями, но при этом сохраняется большое время O.