Преимущество потокового двоичного дерева поиска

Пояснение о деревьях потокового двоичного поиска (пропустите, если вы их знаете):

Мы знаем, что в двоичном дереве поиска с n узлами есть n + 1 левый и правый указатели, содержащие ноль. Чтобы использовать эту память, которая содержит нуль, мы меняем двоичное дерево следующим образом:

для каждого узла z в дереве:

если left [z] = NULL, мы помещаем в left [z] значение дерева-предшественника (z) (то есть указатель на узел, который содержит ключ предшественника),

если right [z] = NULL, мы помещаем в right [z] значение tree-successor (z) (опять же, это указатель на узел, который содержит ключ преемника).

Такое дерево называется многопоточным двоичным деревом поиска, а новые ссылки - потоками.

И мой вопрос: В чем основное преимущество потоковых двоичных деревьев поиска (по сравнению с "обычными" двоичными деревьями поиска). Быстрый поиск в сети показал мне, что это помогает реализовать обход по порядку итеративно, а не рекурсивно.

Это единственная разница? Есть ли другой способ использовать потоки?

Неужели это столь значимое преимущество? и если да, то почему? Рекурсивный обход тоже стоит O (n) времени, так что ..

Большое Вам спасибо.


algorithm data-structures binary-tree binary-search-tree asymptotic-complexity
person Programmer    schedule 05.01.2014    source источник
comment
Рекурсивный обход - это O(n) временная сложность, с O(logN) требованиями к пространству (средний случай) и O(N) требованиями к пространству в худшем случае. С другой стороны, многопоточное двоичное дерево требует O(1) пространства в худшем случае, если обход выполняется итеративно.   -  person amnn    schedule 05.01.2014

Ответы (2)


arrow_upward
5
arrow_downward

Безрекурсивное сканирование по порядку - огромное преимущество. Представьте, что кто-то просит вас найти значение «5» и четыре следующих за ним значения. Это сложно использовать рекурсию. Но если у вас есть многопоточное дерево, то это просто: выполните рекурсивный поиск по порядку, чтобы найти значение «5», а затем перейдите по многопоточным ссылкам, чтобы получить следующие четыре значения.

Точно так же что, если вы хотите, чтобы четыре значения предшествовали определенному значению? Это сложно при рекурсивном обходе, но тривиально, если вы найдете элемент, а затем перейдете по связанным ссылкам в обратном направлении.

person Jim Mischel    schedule 06.01.2014
comment
Да, СУБД делают то же самое со своими B-деревьями, чтобы поддерживать быстрое сканирование диапазона. - person usr; 13.01.2014
comment
Что произойдет, если 5 в дереве нет? В обычном BST мы прекращаем повторение и возвращаем ключ, не найденный в NULL-дочернем указателе, но многопоточное дерево не имеет NULL-указателей (кроме крайнего левого и крайнего правого узлов). Я полагаю, что нужно обнаружить обратный указатель, поскольку, скажем, на узле с node.key == 4 мы хотели бы пойти направо, но node->right->key > 5 и node->right->left == node. Это правильно? - person CiaPan; 11.06.2018
comment
@CiaPan Если 5 там нет, то рекурсивный поиск его не найдет. Многопоточное дерево не имеет указателей NULL в листьях, но у него есть флаги, которые сообщают вам, являются ли указатели связями с потоками или стандартными ссылками BST. Во время поиска вы обрабатываете ссылки на потоки как нулевые указатели. - person Jim Mischel; 11.06.2018
comment
@JimMischel Ага, я понял. Я никогда раньше не видел многопоточное дерево, поэтому я знал только то, что было сказано в вопросе, и флаги «это был нулевой указатель» там не упоминаются. Спасибо за объяснение. - person CiaPan; 11.06.2018

arrow_upward
0
arrow_downward

Основное преимущество потокового двоичного дерева поиска по сравнению с обычным заключается в том, что он имеет обходной характер, который более эффективен в случае первого дерева по сравнению с другим.

Рекурсивный обход означает, что вам не нужно реализовывать его с помощью стека или очереди. Каждый узел будет иметь указатель, который будет давать преемника порядка и предшественника более эффективным способом, при реализации обхода в обычном стеке потребностей BST, который исчерпывает память (как здесь язык программирования нужно учитывать реализацию стека).

person Manish Soni    schedule 10.11.2014