Является ли дерево, созданное сбалансированным деревом tsearch()?

Question

Я создаю двоичный код с помощью tsearch(). Является ли созданное дерево сбалансированным автоматически. Как я могу проверить, что дерево сбалансировано или несбалансировано.

Answer 1

Вы можете проверить, позвонив tsearch на упорядоченный список значений, а затем, вызывая twalk, поставляя действие, который печатает глубину дерева. Если никакого упорядочения дерева не происходит, то упорядоченные вставки создавали бы список, а не дерево, и вы будете выводить значения возрастающей глубины.

void print_depth(const void *nodep, const VISIT which, const int depth) 
{ 
    if(which == preorder || which == leaf) printf("%d\n", depth); 
} 

twalk(root, print_depth); 

Answer 2

ответ Пэдди объясняет, как проверить дерево должно быть сбалансировано, но не дает ответа на вопрос, является ли дерево сбалансировано или нет.

Я сделал то, что предложил Пэдди, и ответ для меня да, это сбалансированный (я запускаю GCC 5.1.1 на Fedora, Glibc 2,21)

(я не уверен, если это также применяется для разных комбинаций операционной системы, компилятора и стандартной библиотеки. Если кто-то экспериментирует с другими ответами на свои системы, добавьте здесь ответ!)

Answer 3

Я изучил это некоторое время назад, работая над my own implementation of tsearch(). Для этого API имеет смысл использовать дерево AVL, чем дерево Red-Black, поскольку выполнение сравнений с помощью функции обратного вызова имеет довольно высокие накладные расходы. Деревья AVL более оптимально сбалансированы, что означает, что обратный вызов вызывается реже.

Похоже, что определение tsearch() в POSIX не требует балансировки, поэтому, к сожалению, вы не можете предположить, что эти функции работают хорошо. То, что я наблюдал при рассмотрении некоторых существующих реализаций:

• glibc реализует его как дерево Red-Black.
• musl реализует его как дерево AVL, но до 2015-12-08 он содержит ошибку, которая вызвала tdelete(), чтобы сделать дерево неуравновешенным.
• Solaris и BSD все, похоже, используют ту же реализацию, которая вообще не использует балансировку.
• FreeBSD 11.0 больше не будет использовать несбалансированную реализацию, так как теперь использует реализацию, которую я написал. FreeBSD 11.0 должен быть выпущен позднее в этом году.