Как мне эффективно добраться до листьев дерева двоичного поиска?

Question

Я хочу суммировать все значения в листах BST. Очевидно, я не могу добраться до листьев, не пройдя все дерево. Это правда? Могу ли я добраться до листьев, не потратив O (N) времени?

Answer 1

Вы понимаете, что сами листья в любом случае будут составлять не менее 1/2 от O (n)?

Answer 2

Чтобы получить доступ ко всем конечным узлам BST, вам придется пройти по всем узлам BST, и это будет порядка O (n).

Одной из альтернатив является использование дерева B +, где вы можете перейти к конечному узлу за O (log n), и после этого все конечные узлы могут быть доступны последовательно для вычисления суммы. Таким образом, в вашем случае это будет O (log n + k), где k - количество листовых узлов, а n - общее количество узлов в дереве B +.

ура

Answer 3

Нет способа получить листья дерева, не пройдя по всему дереву (особенно если вы хотите каждый лист), который, к сожалению, будет работать за O (n) раз. Вы уверены, что дерево - лучший способ хранить ваши данные, если вы хотите получить доступ ко всем этим листьям? Существуют и другие структуры данных, которые обеспечат более эффективный доступ к вашим данным.

Answer 4

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