在 n log n 时间内从排列构建二叉树
Construct a binary tree from permutation in n log n time
将数字 1 到 n 按指定顺序插入二叉搜索树中 p_1、p_2、...、p_n。描述一个 O(nlog n) 时间算法来构造最终的二叉搜索树。
注意：-
- 我要的不是平均时间n log n，而是最差时间。
- 我需要使用常规规则进行插入时生成的确切树。不允许使用 AVL 或红黑树。
这是一道作业题。这是非常非常重要的。事实上，乍一看似乎不可能。我想了很多。我的观察：-
- 我们用来证明排序至少需要 n log n 时间的论点并没有排除这种算法的存在。
- 如果总能在O(n)时间内找到一棵大小介于树大小的二分之一之间的子树，问题就很容易解决
- 选择根的中值或左 child 作为子树的根无效。
诀窍是不使用构造的 BST 进行查找。相反，保留一个额外的、平衡的 BST 用于查找。 Link叶子。
例如，我们可能有
Constructed Balanced
3 2
/ \ / \
2 D 1 3
/ \ / | | \
1 C a b c d
/ \
A B
其中 a, b, c, d 分别是指向 A, B, C, D 的指针，而 A, B, C, D 通常是空指针。
要插入，先插入平衡BST（O(log n)），按照指向构造树的指针（O（1）），进行构造插入（O（1）），然后重新链接新叶 (O(1)).
这是我的 O(n log^2 n) 尝试，不需要构建平衡树。
按照自然顺序（1 到 n）将节点放入数组中。此外 link 它们按插入顺序放入 linked 列表中。每个节点都存储其插入顺序和密钥。
算法是这样的。
输入是 linked 列表中的一个节点，以及节点数组
中索引的范围 (low, high)
- 将输入节点称为root，它的key是
rootkey。从列表中取消link它。
- 判断输入节点的哪个子树较小。
- 遍历对应的数组范围，从linked列表中取出link每个节点，然后link将它们放在单独的linked列表中，并对列表进行排序再次按插入顺序。
- 两个结果列表的头部是输入节点的子节点。
- 对输入节点的子节点递归执行算法，传递范围
(low, rootkey-1) 和 (rootkey+1, high) 作为索引范围。
每个级别的排序操作为算法提供了额外的 log n 复杂度。
这是一个 O(n log n) 算法，它也可以适应 O(n log log m) 时间，其中 m 是范围，通过使用 Y-fast trie 而不是平衡二进制树.
在二叉搜索树中，较低的值留在较高的值中。插入顺序与沿着最终树移动时的 right-or-left 节点选择相对应。任何节点 x 的 parent 是先前插入的最小较高数字或先前插入的最大较低数字，以较晚插入的为准。
我们可以使用上面 O(n log n) worst-time 中的逻辑识别列出的节点并将其与正确的 parent 连接起来我们遍历插入的顺序。
解释：
让我们想象一下提议的更低 parent、p。现在假设有一个数字，l > p，但仍然低于 x，插入在 p 之前。 (1) p 在插入期间通过了 l，在这种情况下，x 必须通过 l 才能到达 p，但这与 x如果达到l一定是走对了；或 (2) p 没有通过 l，在这种情况下 p 位于 l 左侧的子树中，但这意味着插入的数字小于 l 但大于 x，矛盾。
显然，在 p 之后插入的大于 p 的数字 l < x 也会与 p 相矛盾，因为 x 的 parent 因为 (1) l 在插入期间传递了 p，这意味着 p 的权利 child 在插入 x 时已经被分配;或 (2) l 在 p 右侧的子树中，这又意味着插入了一个小于 l 但大于 x 的数字，这是矛盾的.
因此，对于任何节点x，具有较低的parent，parent必须是小于并插入在x之前的最大数。类似的逻辑涵盖了更高提议的场景 parent.
现在假设x的parent、p < x被插入到h之前，最小的数字大于并插入到x之前。然后要么 (1) h 传递给 p，在这种情况下 p 的右节点在插入 x 时已经分配；或 (2) h 在 p 的子树右侧，这意味着之前插入了一个小于 h 且大于 x 的数字，但这与我们的断言相矛盾h 是迄今为止插入的大于 x.
的最小数字
由于 David Eisenstat 没有时间扩展他的答案，我将尝试将更多细节放入类似的算法中。
直觉
算法背后的主要直觉基于以下陈述：
语句 #1：如果 BST 包含值 a 和 b (a < b) 并且它们之间没有值，那么 A（值 a 的节点）是 B（值 b 的节点）的（可能是间接的）parent 或 B是 A 的（可能是间接的）parent。
这个说法显然是正确的，因为如果它们的最低共同祖先 C 是 A 和 B 以外的某个节点，那么它的值 c 必须介于 a 和 b。请注意，语句 #1 对于任何 BST（平衡或不平衡）都是正确的。
语句 #2：如果一个简单的（不平衡的）BST 包含值 a 和 b (a < b) 并且没有它们之间的值并且我们试图添加值 x 使得 a < x < b，然后 X（值 x 的节点）将直接向右（更大）child 的 A 或直接向左（较少）child 的 B 以树中较低的节点为准。
让我们假设两个节点中较低的节点是a（另一种情况是对称的）。在插入阶段，值 x 将在其插入期间经过与 a 相同的路径，因为树不包含 a 和 x 之间的任何值，即在任何比较值 a 和 x 是无法区分的。这意味着值 x 将导航树直到节点 A 并将在较早的步骤中通过节点 B （请参阅语句 #1）。作为 x > a 它应该成为 A 的右 child。 A 的直接右 child 此时必须为空，因为 A 在 B 的子树中，即该子树中的所有值都小于 b 并且由于在树中 a 和 b 之间没有值，所以没有值可以是节点 A 的正确 child。
请注意，在执行 re-balancing 之后，语句 #2 对于某些平衡 BST 可能不正确，尽管这应该是一个奇怪的情况。
语句#3：在平衡 BST 中，对于任何值 x 还不在树中，您可以在 [=55 中找到最接近的更大和最接近的更小的值=]时间。
这直接来自语句 #1 和 #2：您所需要的只是在 BST 中找到值 x 的潜在插入点（采用 O(log(N))），这两个值之一将是插入点的直接 parent 并找到另一个你需要将树返回到根（再次需要 O(log(N))）。
所以现在算法背后的想法变得清晰了：为了快速插入到不平衡的BST中，我们需要找到距离最近的节点更少和更大的价值。如果我们另外维护一个平衡 BST，使用与我们的目标（非平衡）BST 相同的键，并将来自该 BST 的相应节点作为值，我们可以很容易地做到这一点。使用该附加数据结构，我们可以在 O(log(N)) 时间内为每个新值找到插入点，并在 O(log(N)) 时间内用新值更新此数据结构。
算法
- 用
null初始化"main"root和balancedRoot。
- 对于列表中的每个值
x 执行：
- 如果这是第一个值，只需将它作为根节点添加到两棵树中，然后转到#2
- 在
balancedRoot指定的树中找到对应于最近的less（BalancedA，指向主BST中的节点A）和最近的greater（BalancedB, 指向主 BST 中的节点 B) 值。
- 如果没有最接近的较低值，即我们正在添加最小元素，将其作为左侧 child 添加到节点
B
- 如果没有最接近的更大的值，即我们正在添加最大元素，将它作为右边的 child 添加到节点
A
- 找到树中节点
A 或 B 中较低的节点。您可以使用存储在节点中的显式 level。如果下节点是A（较少节点），则添加x作为A的直接右child else 添加x作为[=168的直接左=] of B（更大的节点）。或者（更巧妙地）您可能会注意到，从语句 #1 和 #2 中，恰好是两个候选插入位置之一（A 的右边 child 或 B 的left child) 将为空，这是您要插入值的地方 x.
将值 x 添加到平衡树（可能 re-use 来自步骤 #4）。
- 转到步骤 #2
由于循环的内部步骤都不会超过 O(log(N))，因此总复杂度为 O(N*log(N))
Java实施
我懒得自己实现平衡 BST，所以我使用标准 Java TreeMap that implements Red-Black tree and has useful lowerEntry and higherEntry methods that correspond to step #4 of the algorithm (you may look at the source code 来确保两者实际上都是 O(log(N)))。
import java.util.Map;
import java.util.TreeMap;
public class BSTTest {
static class Node {
public final int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
public boolean compareTree(Node other) {
return compareTrees(this, other);
}
public static boolean compareTrees(Node n1, Node n2) {
if ((n1 == null) && (n2 == null))
return true;
if ((n1 == null) || (n2 == null))
return false;
if (n1.value != n2.value)
return false;
return compareTrees(n1.left, n2.left) &&
compareTrees(n1.right, n2.right);
}
public void assignLeftSafe(Node child) {
if (this.left != null)
throw new IllegalStateException("left child is already set");
this.left = child;
}
public void assignRightSafe(Node child) {
if (this.right != null)
throw new IllegalStateException("right child is already set");
this.right = child;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
static Node insertToBst(Node root, int value) {
if (root == null)
root = new Node(value);
else if (value < root.value)
root.left = insertToBst(root.left, value);
else
root.right = insertToBst(root.right, value);
return root;
}
static Node buildBstDirect(int[] values) {
Node root = null;
for (int v : values) {
root = insertToBst(root, v);
}
return root;
}
static Node buildBstSmart(int[] values) {
Node root = null;
TreeMap<Integer, Node> balancedTree = new TreeMap<Integer, Node>();
for (int v : values) {
Node node = new Node(v);
if (balancedTree.isEmpty()) {
root = node;
} else {
Map.Entry<Integer, Node> lowerEntry = balancedTree.lowerEntry(v);
Map.Entry<Integer, Node> higherEntry = balancedTree.higherEntry(v);
if (lowerEntry == null) {
// adding minimum value
higherEntry.getValue().assignLeftSafe(node);
} else if (higherEntry == null) {
// adding max value
lowerEntry.getValue().assignRightSafe(node);
} else {
// adding some middle value
Node lowerNode = lowerEntry.getValue();
Node higherNode = higherEntry.getValue();
if (lowerNode.right == null)
lowerNode.assignRightSafe(node);
else
higherNode.assignLeftSafe(node);
}
}
// update balancedTree
balancedTree.put(v, node);
}
return root;
}
public static void main(String[] args) {
int[] input = new int[]{7, 6, 9, 4, 1, 8, 2, 5, 3};
Node directRoot = buildBstDirect(input);
Node smartRoot = buildBstSmart(input);
System.out.println(directRoot.compareTree(smartRoot));
}
}
由于这是一项作业，我发布的是提示而不是答案。
对数字进行排序，同时保持插入顺序。假设您有输入：[1,7,3,5,8,2,4]。然后在排序后你会得到 [[1,0], [2,5], [3,2], [4, 6], [5,3], [7,1], [8,4]] 。这实际上是结果树的中序遍历。认真思考如何在给定中序遍历和插入顺序的情况下重构树（这部分将是线性时间）。
如果您确实需要，我们会提供更多提示。
这是一个 linear-time 算法。 （我说过我不打算研究这个问题，所以如果你喜欢这个答案，请将赏金奖励给 SergGr。）
创建一个节点为 1..n 的双向链表并计算 p 的倒数。对于从 n 到 1 的 i，令 q 为列表中 p_i 的左邻居，令 r 为右邻居。如果p^-1(q) > p^-1(r)，则使p_i成为q的右child。如果 p^-1(q) < p^-1(r)，则使 p_i 为 r 的左 child。从列表中删除 p_i。
在Python中：
class Node(object):
__slots__ = ('left', 'key', 'right')
def __init__(self, key):
self.left = None
self.key = key
self.right = None
def construct(p):
# Validate the input.
p = list(p)
n = len(p)
assert set(p) == set(range(n)) # 0 .. n-1
# Compute p^-1.
p_inv = [None] * n
for i in range(n):
p_inv[p[i]] = i
# Set up the list.
nodes = [Node(i) for i in range(n)]
for i in range(n):
if i >= 1:
nodes[i].left = nodes[i - 1]
if i < n - 1:
nodes[i].right = nodes[i + 1]
# Process p.
for i in range(n - 1, 0, -1): # n-1, n-2 .. 1
q = nodes[p[i]].left
r = nodes[p[i]].right
if r is None or (q is not None and p_inv[q.key] > p_inv[r.key]):
print(p[i], 'is the right child of', q.key)
else:
print(p[i], 'is the left child of', r.key)
if q is not None:
q.right = r
if r is not None:
r.left = q
construct([1, 3, 2, 0])
将数字 1 到 n 按指定顺序插入二叉搜索树中 p_1、p_2、...、p_n。描述一个 O(nlog n) 时间算法来构造最终的二叉搜索树。
注意：-
- 我要的不是平均时间n log n，而是最差时间。
- 我需要使用常规规则进行插入时生成的确切树。不允许使用 AVL 或红黑树。
这是一道作业题。这是非常非常重要的。事实上，乍一看似乎不可能。我想了很多。我的观察：-
- 我们用来证明排序至少需要 n log n 时间的论点并没有排除这种算法的存在。
- 如果总能在O(n)时间内找到一棵大小介于树大小的二分之一之间的子树，问题就很容易解决
- 选择根的中值或左 child 作为子树的根无效。
诀窍是不使用构造的 BST 进行查找。相反，保留一个额外的、平衡的 BST 用于查找。 Link叶子。
例如，我们可能有
Constructed Balanced
3 2
/ \ / \
2 D 1 3
/ \ / | | \
1 C a b c d
/ \
A B
其中 a, b, c, d 分别是指向 A, B, C, D 的指针，而 A, B, C, D 通常是空指针。
要插入，先插入平衡BST（O(log n)），按照指向构造树的指针（O（1）），进行构造插入（O（1）），然后重新链接新叶 (O(1)).
这是我的 O(n log^2 n) 尝试，不需要构建平衡树。
按照自然顺序（1 到 n）将节点放入数组中。此外 link 它们按插入顺序放入 linked 列表中。每个节点都存储其插入顺序和密钥。
算法是这样的。
输入是 linked 列表中的一个节点，以及节点数组
中索引的范围(low, high)
- 将输入节点称为root，它的key是
rootkey。从列表中取消link它。 - 判断输入节点的哪个子树较小。
- 遍历对应的数组范围，从linked列表中取出link每个节点，然后link将它们放在单独的linked列表中，并对列表进行排序再次按插入顺序。
- 两个结果列表的头部是输入节点的子节点。
- 对输入节点的子节点递归执行算法，传递范围
(low, rootkey-1)和(rootkey+1, high)作为索引范围。
每个级别的排序操作为算法提供了额外的 log n 复杂度。
这是一个 O(n log n) 算法，它也可以适应 O(n log log m) 时间，其中 m 是范围，通过使用 Y-fast trie 而不是平衡二进制树.
在二叉搜索树中，较低的值留在较高的值中。插入顺序与沿着最终树移动时的 right-or-left 节点选择相对应。任何节点 x 的 parent 是先前插入的最小较高数字或先前插入的最大较低数字，以较晚插入的为准。
我们可以使用上面 O(n log n) worst-time 中的逻辑识别列出的节点并将其与正确的 parent 连接起来我们遍历插入的顺序。
解释：
让我们想象一下提议的更低 parent、p。现在假设有一个数字，l > p，但仍然低于 x，插入在 p 之前。 (1) p 在插入期间通过了 l，在这种情况下，x 必须通过 l 才能到达 p，但这与 x如果达到l一定是走对了；或 (2) p 没有通过 l，在这种情况下 p 位于 l 左侧的子树中，但这意味着插入的数字小于 l 但大于 x，矛盾。
显然，在 p 之后插入的大于 p 的数字 l < x 也会与 p 相矛盾，因为 x 的 parent 因为 (1) l 在插入期间传递了 p，这意味着 p 的权利 child 在插入 x 时已经被分配;或 (2) l 在 p 右侧的子树中，这又意味着插入了一个小于 l 但大于 x 的数字，这是矛盾的.
因此，对于任何节点x，具有较低的parent，parent必须是小于并插入在x之前的最大数。类似的逻辑涵盖了更高提议的场景 parent.
现在假设x的parent、p < x被插入到h之前，最小的数字大于并插入到x之前。然后要么 (1) h 传递给 p，在这种情况下 p 的右节点在插入 x 时已经分配；或 (2) h 在 p 的子树右侧，这意味着之前插入了一个小于 h 且大于 x 的数字，但这与我们的断言相矛盾h 是迄今为止插入的大于 x.
由于 David Eisenstat 没有时间扩展他的答案，我将尝试将更多细节放入类似的算法中。
直觉
算法背后的主要直觉基于以下陈述：
语句 #1：如果 BST 包含值 a 和 b (a < b) 并且它们之间没有值，那么 A（值 a 的节点）是 B（值 b 的节点）的（可能是间接的）parent 或 B是 A 的（可能是间接的）parent。
这个说法显然是正确的，因为如果它们的最低共同祖先 C 是 A 和 B 以外的某个节点，那么它的值 c 必须介于 a 和 b。请注意，语句 #1 对于任何 BST（平衡或不平衡）都是正确的。
语句 #2：如果一个简单的（不平衡的）BST 包含值 a 和 b (a < b) 并且没有它们之间的值并且我们试图添加值 x 使得 a < x < b，然后 X（值 x 的节点）将直接向右（更大）child 的 A 或直接向左（较少）child 的 B 以树中较低的节点为准。
让我们假设两个节点中较低的节点是a（另一种情况是对称的）。在插入阶段，值 x 将在其插入期间经过与 a 相同的路径，因为树不包含 a 和 x 之间的任何值，即在任何比较值 a 和 x 是无法区分的。这意味着值 x 将导航树直到节点 A 并将在较早的步骤中通过节点 B （请参阅语句 #1）。作为 x > a 它应该成为 A 的右 child。 A 的直接右 child 此时必须为空，因为 A 在 B 的子树中，即该子树中的所有值都小于 b 并且由于在树中 a 和 b 之间没有值，所以没有值可以是节点 A 的正确 child。
请注意，在执行 re-balancing 之后，语句 #2 对于某些平衡 BST 可能不正确，尽管这应该是一个奇怪的情况。
语句#3：在平衡 BST 中，对于任何值 x 还不在树中，您可以在 [=55 中找到最接近的更大和最接近的更小的值=]时间。
这直接来自语句 #1 和 #2：您所需要的只是在 BST 中找到值 x 的潜在插入点（采用 O(log(N))），这两个值之一将是插入点的直接 parent 并找到另一个你需要将树返回到根（再次需要 O(log(N))）。
所以现在算法背后的想法变得清晰了：为了快速插入到不平衡的BST中，我们需要找到距离最近的节点更少和更大的价值。如果我们另外维护一个平衡 BST，使用与我们的目标（非平衡）BST 相同的键，并将来自该 BST 的相应节点作为值，我们可以很容易地做到这一点。使用该附加数据结构，我们可以在 O(log(N)) 时间内为每个新值找到插入点，并在 O(log(N)) 时间内用新值更新此数据结构。
算法
- 用
null初始化"main"root和balancedRoot。 - 对于列表中的每个值
x执行： - 如果这是第一个值，只需将它作为根节点添加到两棵树中，然后转到#2
- 在
balancedRoot指定的树中找到对应于最近的less（BalancedA，指向主BST中的节点A）和最近的greater（BalancedB, 指向主 BST 中的节点B) 值。 - 如果没有最接近的较低值，即我们正在添加最小元素，将其作为左侧 child 添加到节点
B - 如果没有最接近的更大的值，即我们正在添加最大元素，将它作为右边的 child 添加到节点
A - 找到树中节点
A或B中较低的节点。您可以使用存储在节点中的显式level。如果下节点是A（较少节点），则添加x作为A的直接右child else 添加x作为[=168的直接左=] ofB（更大的节点）。或者（更巧妙地）您可能会注意到，从语句 #1 和 #2 中，恰好是两个候选插入位置之一（A的右边 child 或B的left child) 将为空，这是您要插入值的地方x.
- 如果没有最接近的较低值，即我们正在添加最小元素，将其作为左侧 child 添加到节点
将值
x添加到平衡树（可能 re-use 来自步骤 #4）。- 转到步骤 #2
由于循环的内部步骤都不会超过 O(log(N))，因此总复杂度为 O(N*log(N))
Java实施
我懒得自己实现平衡 BST，所以我使用标准 Java TreeMap that implements Red-Black tree and has useful lowerEntry and higherEntry methods that correspond to step #4 of the algorithm (you may look at the source code 来确保两者实际上都是 O(log(N)))。
import java.util.Map;
import java.util.TreeMap;
public class BSTTest {
static class Node {
public final int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
public boolean compareTree(Node other) {
return compareTrees(this, other);
}
public static boolean compareTrees(Node n1, Node n2) {
if ((n1 == null) && (n2 == null))
return true;
if ((n1 == null) || (n2 == null))
return false;
if (n1.value != n2.value)
return false;
return compareTrees(n1.left, n2.left) &&
compareTrees(n1.right, n2.right);
}
public void assignLeftSafe(Node child) {
if (this.left != null)
throw new IllegalStateException("left child is already set");
this.left = child;
}
public void assignRightSafe(Node child) {
if (this.right != null)
throw new IllegalStateException("right child is already set");
this.right = child;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
static Node insertToBst(Node root, int value) {
if (root == null)
root = new Node(value);
else if (value < root.value)
root.left = insertToBst(root.left, value);
else
root.right = insertToBst(root.right, value);
return root;
}
static Node buildBstDirect(int[] values) {
Node root = null;
for (int v : values) {
root = insertToBst(root, v);
}
return root;
}
static Node buildBstSmart(int[] values) {
Node root = null;
TreeMap<Integer, Node> balancedTree = new TreeMap<Integer, Node>();
for (int v : values) {
Node node = new Node(v);
if (balancedTree.isEmpty()) {
root = node;
} else {
Map.Entry<Integer, Node> lowerEntry = balancedTree.lowerEntry(v);
Map.Entry<Integer, Node> higherEntry = balancedTree.higherEntry(v);
if (lowerEntry == null) {
// adding minimum value
higherEntry.getValue().assignLeftSafe(node);
} else if (higherEntry == null) {
// adding max value
lowerEntry.getValue().assignRightSafe(node);
} else {
// adding some middle value
Node lowerNode = lowerEntry.getValue();
Node higherNode = higherEntry.getValue();
if (lowerNode.right == null)
lowerNode.assignRightSafe(node);
else
higherNode.assignLeftSafe(node);
}
}
// update balancedTree
balancedTree.put(v, node);
}
return root;
}
public static void main(String[] args) {
int[] input = new int[]{7, 6, 9, 4, 1, 8, 2, 5, 3};
Node directRoot = buildBstDirect(input);
Node smartRoot = buildBstSmart(input);
System.out.println(directRoot.compareTree(smartRoot));
}
}
由于这是一项作业，我发布的是提示而不是答案。
对数字进行排序，同时保持插入顺序。假设您有输入：[1,7,3,5,8,2,4]。然后在排序后你会得到 [[1,0], [2,5], [3,2], [4, 6], [5,3], [7,1], [8,4]] 。这实际上是结果树的中序遍历。认真思考如何在给定中序遍历和插入顺序的情况下重构树（这部分将是线性时间）。
如果您确实需要，我们会提供更多提示。
这是一个 linear-time 算法。 （我说过我不打算研究这个问题，所以如果你喜欢这个答案，请将赏金奖励给 SergGr。）
创建一个节点为 1..n 的双向链表并计算 p 的倒数。对于从 n 到 1 的 i，令 q 为列表中 p_i 的左邻居，令 r 为右邻居。如果p^-1(q) > p^-1(r)，则使p_i成为q的右child。如果 p^-1(q) < p^-1(r)，则使 p_i 为 r 的左 child。从列表中删除 p_i。
在Python中：
class Node(object):
__slots__ = ('left', 'key', 'right')
def __init__(self, key):
self.left = None
self.key = key
self.right = None
def construct(p):
# Validate the input.
p = list(p)
n = len(p)
assert set(p) == set(range(n)) # 0 .. n-1
# Compute p^-1.
p_inv = [None] * n
for i in range(n):
p_inv[p[i]] = i
# Set up the list.
nodes = [Node(i) for i in range(n)]
for i in range(n):
if i >= 1:
nodes[i].left = nodes[i - 1]
if i < n - 1:
nodes[i].right = nodes[i + 1]
# Process p.
for i in range(n - 1, 0, -1): # n-1, n-2 .. 1
q = nodes[p[i]].left
r = nodes[p[i]].right
if r is None or (q is not None and p_inv[q.key] > p_inv[r.key]):
print(p[i], 'is the right child of', q.key)
else:
print(p[i], 'is the left child of', r.key)
if q is not None:
q.right = r
if r is not None:
r.left = q
construct([1, 3, 2, 0])