При каких обстоятельствах бинарное дерево поиска и частично упорядоченное дерево могут быть эквивалентны?

Question

Это мой первый вопрос здесь, и, вероятно, не последний.

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

Я думал о возможности того, чтобы двоичное дерево поиска и частично упорядоченное дерево были эквивалентны при некоторых обстоятельствах, но я не совсем уверен, возможно ли это на самом деле.

Может ли кто-нибудь помочь мне?

Спасибо!

Answer 1

Двоичное дерево поиска - это двоичное дерево, где каждый узел больше любого узла его левого поддерева и меньше любого узла его правого поддерева.

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

Кроме базового случая любого дерева, имеющего только один (root) узел, также если двоичное дерево поиска было построено вставляя все меньшие и меньшие элементы, например:

                      20
                     /
                   15
                  /
                 7
                /
               2

и, таким образом, получая в результате BST с только левыми поддеревьями для всех его узлов, это также является частично упорядоченным деревом, поскольку оно также удовлетворяет своему инварианту.