java二进制搜索树混乱（bestcase）

Question

我目前正在备考，其中一个让我困惑的问题是：

给出密钥A X C S E R H的5个顺序，当插入初始值为空的BST时，生成最佳案例树。假设按字典顺序/字母顺序排列

答案如下：

以下是一些可能的命令

H C A E S R X

H C A E S X R

H C E A S R X

H C E A S X R

H C E S A R X

我想知道是否有人能给我一些关于“H”如何在根节点上的澄清？根据我目前的理解，我认为“A”是根。我想我需要一些关于如何获得BST最佳案例树的说明。如果有人能帮助我理解这一点，我将不胜感激

Answer 1

你的第一个条目将是你的根。在那之后，在你的根之前的任何东西（在本例中按字母顺序）都将转到左边；之后我会去右边

每一个都会生成一棵树，可以按照字母顺序从左下角到右下角进行追踪

如您所见，这会生成一棵树，它可以从左下角向上读取到根（在继续向上之前，从父级中搜索每个分支），以创建字母序列

Answer 2

如果A是根节点，那么所有的节点都在它的右边，这样你就不会有树的优势，你会有更类似于链表的东西。为了使树成为最佳情况树，您希望根节点左右的节点数相似，这样树的深度将更小，并且您将获得更好的性能