笛卡尔和left join

问题： (Problem:)

A Cartesian tree with sequence S is a binary tree defined by the following two properties:

具有序列S笛卡尔树是由以下两个属性定义的二叉树：

It is heap-ordered, so that each parent value is strictly less than that of its children.

它是堆排序的，因此每个父值严格小于其子值。

An in-order traversal of the tree produces nodes with values that correspond exactly to S.

树的有序遍历将产生具有与S完全对应的值的节点。

For example, given the sequence [3, 2, 6, 1, 9], the resulting Cartesian tree would be:

例如，给定序列[3, 2, 6, 1, 9] 3，2，6，1，9 [3, 2, 6, 1, 9] ，结果的笛卡尔树将是：

1 / \ 2 9 / \ 3 6

Given a sequence S, construct the corresponding Cartesian tree.

给定序列S ，构造相应的笛卡尔树。

天真的算法： (Naive Algorithm:)

A naive algorithm can be found by using the fundamental property of heap: The smallest element of the heap is alway at the root!

通过使用堆的基本属性，可以找到一种幼稚的算法：堆的最小元素始终位于根！

Here is how we can recursively construct the tree using this property:

这是我们可以使用此属性递归构造树的方法：

Find the smallest element of the array, a[i] for some index i.

找到数组的最小元素a[i]以获得某个索引i 。

This index divides the array in two parts: (1) {a[0], a[1], ..., a[i-1]} and {a[i+1], a[i+2], ..., a[N]}. Recursive build the binary trees for these two parts, and add them as children of a new node with value a[i].

此索引将数组分为两部分：(1) {a[0], a[1], ..., a[i-1]}和{a[i+1], a[i+2], ..., a[N]} 。 递归为这两个部分构建二进制树，并将它们添加为值为a[i]的新节点的子代。

Let’s start with the definition of a Node.

让我们从节点的定义开始。

struct Node { int value = 0; Node* left = nullptr; Node* right = nullptr; Node*parent = nullptr; };

And define a helper function to find the index of minimum of an array between start and end, both inclusive.

并定义一个辅助函数以查找start和end (包括end之间的最小数组索引。

int min_index(const std::vector<int>& a, int start, int end) { if (start < 0 || end >= a.size()) return 0; int min = a[start]; int min_idx = start; for (int i = start+1; i<=end; i++) { if (a[i] < min) { min = a[i]; min_idx = i; } } return min_idx; }

Finally, the recursive method to construct the tree:

最后，构造树的递归方法：

Node* buildify(const std::vector<int>& a, int start, int end) { if (start < 0 || end >= a.size()) return nullptr; if (start > end) return nullptr; if (start == end) { std::unique_ptr<Node> root = std::make_unique<Node>(); root->value = a[start]; return root->get(); } int min_idx = min_index(a, start, end); std::unqiue_ptr<Node> root = std::make_unique<Node>(); root->value = a[min_idx]; root->left = buildify(a, start, min_idx-1); root->right = buildify(a, min_idx+1, end); (root->left)->parent = root->get(); (root->right)->parent = root->get(); return root->get(); } Node* build_tree(const std::vector<int>& a) { if (a.empty()) return nullptr; return buildify(a, 0, a.size()-1); }

What’s the complexity of this algorithm? For each node in the tree, we are performing O(N)work to find a minimum element of the subarray and split the array. Since there are O(N) nodes in the tree, the total complexity of the algorithm is O(N^2). Can we do better?

该算法的复杂性是什么？ 对于树中的每个节点，我们正在执行O(N)工作以找到子数组的最小元素并将数组拆分。 由于树中有O(N)节点，因此该算法的总复杂度为O(N ^ 2)。 我们可以做得更好吗？

高效算法： (Efficient Algorithm:)

The efficient algorithm on this problem relies on two properties of a min-heap, and in-order traversal

针对此问题的有效算法取决于最小堆和有序遍历的两个属性

Every path in a min-heap from root to leaf contains monotonically increasing values.

从根到叶的最小堆中的每个路径都包含单调递增的值。 An in-order traversal always traverses the tree from left to right.

有序遍历始终会从左到右遍历树。

Here’s how we can use these two properties to design an algorithm:

这是我们如何使用这两个属性来设计算法的方法：

Traverse the array from left to right.

从左到右遍历数组。 For every new element of the array, we need to find its appropriate place in the tree. In the beginning, try inserting it at the most logical place — end of the tree; i.e. rightmost child of the tree!. This might violate the min-heap property. In that case, heapify the tree, i.e. try pushing this node upwards on the path from the rightmost child to the root till it finds its appropriate place. Place all remaining elements of the path on the left subtree of this newly inserted node.

对于数组的每个新元素，我们都需要在树中找到它的适当位置。 首先，尝试将其插入最合理的位置-树的末端； 即树的最右边的孩子！ 这可能会违反min-heap属性。 在这种情况下，堆放树，即尝试从最右边的子节点到根节点的路径向上推动该节点，直到找到合适的位置为止。 将路径的所有其余元素放在此新插入的节点的左子树上。

Here is the working of the algorithm on the example {3, 2, 6, 1, 9}.

这是算法在示例{3, 2, 6, 1, 9} 。

Start with the single node tree with the value 3.

从值为3的单节点树开始。

Try inserting the new value, 2 as the rightmost child.

尝试插入新值2作为最右边的子级。

3 \ 2

This new tree violates the min-heap property. Push the value 2 up the path towards root, and add any existing nodes as left subtree, giving us

此新树违反了min-heap属性。 将值2推向根的路径，并添加任何现有节点作为左子树，从而使我们

2 /3

The next node 6 can be easily inserted as the rightmost leaf without violating the min-heap property.

可以容易地将下一个节点6插入为最右边的叶子，而不会违反min-heap属性。

2 / \3 6

The next node, 1 again violates the min-heap property.

下一个节点1再次违反min-heap属性。

2 / \3 6 \ 1 Pushing the new node up, and restructuring the existing nodes to the left subtree gives the correct partial result

向上推新节点，并将现有节点重组到左侧子树中，可以得出正确的部分结果 1 / 2 / \ 3 6

As the final step, we can insert 9 in its correct place as the rightmost child.

最后一步，我们可以将9作为最右边的孩子插入正确的位置。

1 / \ 2 9 / \ 3 6

Here is the code to perform the insertion and adjustment to the tree structure. The height of the tree is O(log N). Since we are performing O(log N) work for every new node, and since there are O(N) nodes in the tree, the total complexity of this algorithm is O(N log N).

这是执行插入和调整树结构的代码。 树的高度为O(log N) 。 由于我们正在为每个新节点执行O(log N)工作，并且由于树中存在O(N)节点，因此该算法的总复杂度为O(N log N) 。

Node* find_rightmost(Node* root) { node curr = root; while (curr != nullptr) { if (curr->right == nullptr) return curr; curr = curr->right; } return nullptr; } Node* insert(Node* root, int val) { if (root == nullptr) { std::unique_ptr<Node> new_root = std::make_unique<Node>(); new_root->value = val; return new_root.release(); } // Iterate from the rightmost leaf upwards - finding first node with // the value less than val. Node* rightmost = find_rightmost(root); Node* rightost_child = nullptr; while (rightmost != nullptr && rightmost->value > val) { rightmost_child = rightmost; rightmost = rightmost->parent; } std::unique_ptr<Node> new_root_ptr = std::make_unique<Node>(); new_root_ptr->value = val; Node* new_root = new_root_ptr.release(); // Case 1: rightmost is null. Return the new root. if (rightmost == nullptr) { if (rightmost_child != nullptr) { new_root->left = rightmost_child; rightmost_child->parent = new_root; } return new_root; } // Case 2: rightmost is not null. Insert the new node in appropriate // place, and return the original root. if (rightmost->right == rightmost_child) { rightmost->right = new_root; } else { rightmost->left = new_root; } new_root->parent = rightmost; if (rightmost_child != nullptr) { new_root->left = rightmost_child; rightmost_child->parent = new_root; } return root; } Node* build_tree(const std::vector<int>& a) { if (a.empty()) return nullptr; Node* root = nullptr; for (int val : a) { root = insert(root, val); } return root; }

测试： (Testing:)

Start testing some simple cases of empty and singleton array.

开始测试一些简单的空数组和单例数组。

GTEST("Empty array") { EXPECT_EQ(nullptr, build_tree({})); } GTEST("Singleton array") { Node* root = build_tree({1}); ASSERT_NE(nullptr, root); EXPECT_EQ(1, root->value); EXPECT_EQ(nullptr, root->left); EXPECT_EQ(nullptr, root->right); EXPECT_EQ(nullptr, root->parent); }

Finally, here is one way of testing the complex tree from the example

最后，这是从示例中测试复杂树的一种方法

GTEST("Complex tree") { Node* root = build_tree({3, 2, 6, 1, 9}); // root node ASSERT_NE(nullptr, root); EXPECT_EQ(1, root->value); // left subtree ASSERT_NE(nullptr, root->left); Node* left = root->left; EXPECT_EQ(2, left->value); ASSERT_NE(nullptr, left->parent); EXPECT_EQ(1, left->parent->value); // right subtree ASSERT_NE(nullptr, root->right); Node* right = root->right; EXPECT_EQ(9, right->value); ASSERT_NE(nullptr, right->parent); EXPECT_EQ(1, right->parent->value); EXPECT_EQ(nullptr, right->left); EXPECT_EQ(nullptr, right->right); // Deeper subtree ASSERT_NE(nullptr, left->left); ASSERT_NE(nullptr->left->right); EXPECT_EQ(3, left->left->value); EXPECT_EQ(6, left->right->value); }

Originally published at https://cppcodingzen.com on September 3, 2020.

最初于 2020年9月3日 发布在 https://cppcodingzen.com 上。

翻译自: https://medium.com/swlh/cartesian-sequence-and-binary-tree-538cbd0b0ca8

笛卡尔和left join