二叉搜索树和偏序树在什么情况下可以等价？

Question

这是我在这里的第一个问题，可能不是最后一个。

我目前正在研究不同种类的树，特别是二叉搜索树，还有其他一些树，例如 AVL 或偏序树。

我一直在考虑二叉搜索树和偏序树在某些情况下是等价的可能性，但我不太确定这是否真的可能。

有人可以帮我吗？

谢谢！

Answer 1

二叉搜索树是一棵二叉树，其中每个节点都大于其左子树的任何节点且小于其右子树的任何节点。

偏序树是一棵树，其中每个节点都大于（或等于）它的任何子节点。

除了任何只有一个（根）节点的树的基本情况，如果恰好通过插入越来越小的元素来构建二叉搜索树，例如：

                      20
                     /
                   15
                  /
                 7
                /
               2

因此导致 BST 的所有节点都只有左子树，那么它也是一棵偏序树，因为它也满足其不变量。