algorithm - 如何创建左规范二叉搜索树？

Question

我正在学习数据结构，我必须构建左规范二叉搜索树，也称为左平衡二叉搜索树。

例子:

我不知道从哪里以及如何开始构建那棵树。谁能告诉我该怎么做。也许在一个简单的例子中，元素从 1、2、3……到 10。

Answer 1

在实践中，我们首先找到两个 M = 2^n 的最大幂，使得 M ≤ N 其中 N 是我们要计算的元素数想插入。这棵树将在除最底层之外的所有级别上包含 M-1 个元素。最底层本身将包含 M 个元素，分为左子树中的 M/2 和右子树中的 M/2。

我们计算余数 R = N − (M − 1) 然后如果 R ≤ M/2

LT = (M − 2)/2 + R
RT = (M − 2)/2

否则如果 R > M/2

LT = (M − 2)/2 + M/2
RT = (M − 2)/2 + R − M/2

---

示例:

在示例 (2, 3, 7, 9, 11) 中，我们有 N=5 个元素，M=4，因此 R=5-(4-1)=2。因此LT为3，RT为1。因此，9成为用作根节点的中值元素，2、3、7被放入左子树，而11成为右树。我们递归计算整棵树。

来源: http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/2535/pdf/imm2535.pdf

您的示例:

你有元素:1、2、3、4、5、6、7、8、9、10。

N = 10
M = 2^n where M ≤ N
M = 8
R = 10 - (8 - 1) = 3

所以 3 ≤ M/2 是有效的。

LT = (M - 2)/2 + R
LR = 6
RT = (M - 2)/2
RT = 3

所以在左子树中有元素 1、2、3、4、5、6。在右子树中有元素 8、9、10 和 7 是中位数。

我们绘制根节点 7。

---

然后我们对 LT 元素 1、2、3、4、5、6 执行相同的操作。

N = 6
M = 2^n where M ≤ N
M = 4
R = 6 - (4 - 1) = 3

所以 3 ≤ M/2 是无效的。

LT = (M - 2)/2 + M/2
LT = 3
RT = (M - 2)/2 + R - M/2
RT = 2

在左子树中有元素 1、2、3。在右子树中有元素 5、6 和 4 是中位数。

我们画 4 作为 7 的左 child 。

---

然后我们对元素 1、2、3、4、5、6 的 LT 元素 1、2、3 执行相同的操作。

N = 2
M = 2^n where M ≤ N
M = 2
R = 3 - (2 - 1) = 2

所以 2 ≤ M/2 是无效的。

LT = (M - 2)/2 + M/2
LT = 1
RT = (M - 2)/2 + R - M/2
RT = 1

左子树中有元素1，右子树中有元素3，2是中位数。

我们画 2 作为 4 的左 child 。

---

从逻辑上讲，1 是 2 的左 child ，3 是 2 的右 child 。

根据规则，如果只有两个元素，右边的元素是中位数(根节点)。所以 6 是 4 的右 child ，5 是 6 的左 child 。

然后我们用元素 8、9、10 对 RT(根节点 7 的右 child )做同样的事情，其中​​ 9 是中值，8 是 9 的左 child ，10 是 9 的右 child 。

最终的树应该是这样的。