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

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成为右树。我们递归计算整棵树。

你的例子：

您有元素：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 作为左 child of 7.

然后我们对元素 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 作为左 child of 4.

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

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

然后我们对 RT（根节点 7 的右 children）使用元素 8、9、10 执行相同操作，其中 9 是中位数，8 是左 child of 9 and 10 is右边 child 共 9 个

最终的树应该是这样的。

How to create left canonical binary search tree?