BST. Binary Search Tree. Порядковый номер. Не понятна суть того, что по методичке просят сделать. (У автора нет возможности спросить)
Мне нужно реализовать на С++ "Определение порядкового номера для элемента с заданным ключом. Трудоёмкость операции – O (log n)." для BSTree (Дерева бинарного поиска).
Вопрос: Что значит "порядковый номер элемента" для дерева BST?
Может есть какое-то конкретное определения что это? Порядковый номер при обходе?(+обходить по разному можно) при вставке? или это номер того на какой высоте узел в дереве находится?
Ответы (2 шт):
Автор решения: artamon98
→ Ссылка
Порядковый номер элемента для BST это его индекс) Ну или глубина(высота).
Автор решения: MBo
→ Ссылка
Вам нужен порядковый номер в сортированном массиве ключей, он совпадает с порядком вывода узла при центрированном обходе (left - node- right), однако сам обход вам выполнять не нужно, т.к. указано время O(log n)