二叉搜索树/采摘根

Question

我不太清楚如何选择一个根二叉搜索树（我想没有任何的代码来执行）：

5,9，2,1， 4，8，3，7，6

如何挑选根？

这个步骤让我很困惑这个算法。

Answer 1

如何挑选根？

以无论你想要的方式。任何数量的数据都可以成为根。

---

您想选择虽然中位数，在这种情况下，5.具有这样的选择，你的树应该得到，因为它得到平衡，在右子树上的5左侧的四个节点和四个节点的

请注意，任何元素可能是rood（即使是一个随机的选择，或在你的例子中的第一个数字）。

---

嗯，那我为什么要担心找到的中位数，而不是老是挑的第一个数字（最容易的选择）？

因为您希望您的二进制搜索树（BST）尽可能为平衡。

如果您选择最小或最大数字作为根，那么您的树将达到其最大深度（最坏的情况），并将模拟单个链表，这将导致搜索的最坏情况算法。然而，正如米歇尔所说的那样，选择根的最小或最大项目不一定会导致退化树。例如，如果您为根选取最小项目，但包含其余项目的右分支平衡，则树的高度仅比最佳值高一级。如果您按照升序或降序选择节点，则只会得到退化树。

请记住，在BST，这个规则必须得到尊重：

留守儿童小于父节点和 没事的孩子比父节点大。

---

欲了解更多，请阅读How binary search tree is created?？

Answer 2

具有相同值的BST可以有多种形式。例如，含有1,2-树可以是：

1 <- root 
\ 
    2 <-- right son 

或

2 <- root 
/
    1 <-- left son 

所以可以有一个树，其中1是根和它进入1-> 2-> 3 ..没有离开的儿子。你可以有5个作为根，4和6分别作为左右儿子，你可以有许多其他树具有相同的值，但排序不同（也可能不同）

Answer 3

中位数是一个更好的选择，因为你想要更少的深度。 这里是一个例子中，根是找到中值下一个还发现平均

    5 
      3    8 
    2   4  7 9 
1     6   

5是由（1 + 9）/ 2获得。 3从天花板上获得（1 + 4）/ 2（您也可以选择中位数作为选择中间根的角色）

Answer 4

您可以初始化一个空的BST（二叉搜索树），然后遍历列表并插入每个项目。

你不需要选择一个根，只需构建树。但是也许你想平衡树，你可以插入第一个元素作为列表的中间值，但正确的答案是使用平衡二叉搜索树（AVL树）。