Сложность вложенного двоичного дерева поиска

Question

Кто-нибудь знает, как вычислить сложность вложенного бинарного дерева поиска?Я реализовал вложенное двоичное дерево поиска на глубину 3 BST.

РЕДАКТИРОВАТЬ: Я прошу прощения за путаницу, я имел в виду, что каждый узел BST будет указывать на корневой узел другого BST.Сложность, о которой я просил, заключалась во временной сложности поиска, обновления и удаления (основные операции).Я предполагал, что поскольку временная сложность BST была O (log (n)), временная сложность вложенного BST с точки зрения поиска, обновления и удаления не будет сильно отличаться.

Answer 1

Я предполагаю, что под "вложенным" вы подразумеваете, что каждый узел определенного дерева указывает на корень другого дерева, глубиной до 3 уровней.

Что ж, бинарное дерево поиска обычнобыть O (log n) время поиска.Так как вы делаете 3 поиска, это O (log a * log b * log c).Конечно, это предполагает, что они хорошо сбалансированы и все такое.Наихудший случай для бинарного дерева поиска - O (n) (представьте себе дерево, в котором это в основном прямая линия).Тогда время наихудшего случая будет O (a * b * c).

А для записи ab и c - количество элементов в первом дереве, втором вложенном дереве и третьем дереве с двойным вложениемсоответственно.