一群算法

by Sachin Malhotra

由Sachin Malhotra

树遍历解释：他们就像一群懒惰的学生，试图欺骗他们的考试 (Tree Traversals explained: They’re like a class of lazy students trying to cheat on their exam)

Imagine that you are enrolled in a math class at one of the most prestigious universities of the world.

想象一下，您正在世界上最负盛名的大学之一参加数学班。

You have an exam coming up real soon. Obviously, you want to perform well on the exam.

您即将进行一次真正的考试。 显然，您希望在考试中表现良好。

The thing about this university is that it has a clumsy set of professors. So cheating is really simple. You can easily copy from the guy sitting behind and ahead without getting caught.

关于这所大学的事情是，它拥有一批笨拙的教授。 所以作弊真的很简单。 您可以轻松地从后面和后面的那个人那里复制，而不会被抓住。

The professors, in order to take control of this problem, came up with two solutions:

为了控制这个问题，教授们提出了两种解决方案：

• The number of students sitting in a class is never fixed. And the people sitting in one class taking the test change from one test to another.
  上课的学生人数永远是固定的。 参加一堂课的人从一项考试变为另一项考试。
• The seating arrangement is released five minutes before the exam. The seating arrangement is alphabetical. But since the students are never fixed and new ones may get added or old ones removed from a class randomly, the arrangement has to be explicitly released for the students to know where exactly they have to sit.
  考试前五分钟释放座位安排。 座位安排是按字母顺序排列的。 但是由于学生永远不会固定下来，可能会随机添加新学生或从课堂上删除老学生，因此必须明确发布安排，让学生知道他们确切坐在哪里。

Say you’re one of those lazy students who wants to cheat, despite the consequences. Five minutes before the exam when the seating arrangement is released, how do you find out who is sitting in front of you and who’s behind as quickly as possible?

假设您是尽管有后果但还是想作弊的懒惰学生之一。 考试开始前五分钟，放开座位，您如何尽快找出谁坐在您的前面，谁在后面？

You won’t be able to cheat if you don’t talk to these two people beforehand and strategize, right?

如果您不事先与这两个人交谈并制定策略，您将无法作弊，对吗？

座位安排 (The Seating Arrangement)

So the professors released the seating arrangement for the first test ever conducted this way. Say it had N students. If these students were to remain the same from one test to another, then it would have been very easy to cheat, right? Because the seating arrangement is always done alphabetically.

因此，教授们发布了以这种方式进行的首次测试的座位安排。 假设有N个学生。 如果这些学生从一项测试到另一项测试保持相同，那么作弊就很容易了，对吧？ 因为座位安排总是按字母顺序进行。

Therefore, the professors keep on adding or removing students from this list from one test to another, and only released these modifications before each test. This way, students could never know deterministically before a test who would be sitting in front of or behind them.

因此，教授们一直在从一个测试到另一个测试的列表中添加或删除学生，并且仅在每次测试之前发布这些修改。 这样，学生在考试之前永远无法确定地知道坐在他们前面还是后面。

Let’s consider this problem in algorithmic terms. We are given a list of N elements where elements in this case are student’s names. This list keeps on varying from one exam to another, such that new elements can be added to the list or existing elements can be removed from the list.

让我们从算法上考虑这个问题。 我们给出了N个元素的列表，其中这种情况下的元素是学生的名字。 此列表在一项考试之间不停变化，因此可以将新元素添加到列表中，或者可以将现有元素从列表中删除。

Given the list of modifications at any given time T and a name N, we need to determine the elements B and A, such that B would come right before N and A would come right after N if the list were to be sorted.

给定在任何给定时间T的修改列表和名称N，我们需要确定元素B和A，以便如果要对列表进行排序，则B将在N之前出现，而A将在N之后出现。

Now let’s look at what data structures are available to us and what would suit this problem the best.

现在，让我们看一下我们可以使用哪些数据结构以及最适合该问题的数据结构。

哦，Array，我的老朋友，您能帮我吗？ (Oh Array, my old friend, will you help me?)

Using an array seems to be a rather straightforward approach.

使用数组似乎是一种相当简单的方法。

• We can simply put all the names on the released list in an array.
  我们可以简单地将所有名称放在数组中的已发布列表中。
• Then we sort all the names (the list of names released might be randomly arranged) lexicographically
  然后，我们按字典顺序对所有名称(发布的名称列表可能是随机排列的)进行排序
• And then we can find our name in the list by using a binary search procedure. This would give us the predecessor and the successor.
  然后，我们可以使用二进制搜索过程在列表中找到我们的名字。 这将给我们前任和后任。

This seems to be a viable approach to solve this problem. The issue at hand, however, is that the students are never fixed from one exam to another. And so the list that was released for the very first exam would vary dynamically when new students were added and old ones were removed.

这似乎是解决此问题的可行方法。 然而，眼下的问题是，学生永远不会从一项考试固定到另一项考试。 因此，当添加新学生而删除旧学生时，为第一次考试发布的列表将动态变化。

We can sort the list for the very first time, and then keep on adding new elements and removing old ones accordingly moving forward.

我们可以第一次对列表进行排序，然后继续添加新元素并删除旧元素。

However, the complexity of adding or removing an element from an array is of the order O(n) . Since the number of students could be very large, and we don’t know how many modifications there would be before some new test, this would take a lot of time and the test would start before we could solve the problem. Remember that the modifications are released just five minutes before the test.

但是，从数组中添加或删除元素的复杂度约为O(n) 。 由于学生人数可能很大，并且我们不知道在进行新测试之前会有多少修改，因此这将花费大量时间，并且在我们解决问题之前就开始测试。 请记住，修改是在测试前五分钟发布的。

So what other data structure do we have where insertion and deletion can be done very quickly?

那么，我们还有什么其他数据结构可以快速完成插入和删除操作呢？

嗯，也许链表毕竟是我真正的朋友 (Hmmmm, maybe Linked List is my true friend after all)

As far as a linked list is concerned, it has it’s own set of problems when dealing with this type of situation. Initially, we need to sort the list of elements lexicographically. Since this is a one-time operation, because it is only to be done for the first exam, the time taken here does not really matter.

就链接列表而言，在处理此类情况时，它具有一系列自身的问题。 最初，我们需要按字典顺序对元素列表进行排序。 由于这是一次性操作，因为它仅用于第一次检查，所以这里花费的时间并不重要。

From the next exam onwards, only the modifications are released. Adding or deleting an element from a linked list is a constant time operation, provided we know the location of that element in the list.

从下一次考试开始，仅发布修改内容。 只要我们知道该元素在列表中的位置，就可以从链接列表中添加或删除元素，这是一项固定时间的操作。

Finding an element in a linked list is a linear time operation — it takes O(n) . I know there are concepts like skip lists, but why dive into something like this when we can solve this problem in a much better fashion by using another type of data structure?

在链表中查找元素是线性时间操作-花费O(n) 。 我知道有一些类似跳过列表的概念，但是当我们可以通过使用另一种类型的数据结构以更好的方式解决此问题时，为什么要深入研究呢？

输入二元搜索树，镇上的新孩子 (Enter Binary Search Trees, the new kid in town)

Let’s look at how we can model our data using a binary search tree (BST). Then we’ll see how a BST can help us solve the problem we initially set out to solve.

让我们看看如何使用二叉搜索树(BST)对数据建模。 然后，我们将了解BST如何帮助我们解决最初要解决的问题。

A Binary Search Tree is basically a binary tree with a special way of ordering the nodes.

二进制搜索树基本上是具有特殊排序节点方式的二进制树。

For a node with key k, every key in the left subtree is less than k and every key in the right subtree is greater than k.

对于具有键k的节点，左子树中的每个键都小于k ，而右子树中的每个键都大于k 。

In our case, the keys will be the names of the students.

在我们的例子中，键将是学生的姓名。

Consider the following example to see how a binary search tree is constructed. This should lend greater clarity to the data structure.

考虑以下示例，以了解如何构建二进制搜索树。 这应该使数据结构更加清晰。

Constructing a Binary Search Tree is not enough. We need to make sure it is balanced. The reason we say that a Binary Search Tree needs to be balanced is that, if it is not balanced, then we can have something like this:

仅仅建立一个二叉搜索树是不够的。 我们需要确保它是平衡的 。 我们说二进制搜索树需要平衡的原因是，如果它不是平衡的，那么我们可以得到这样的东西：

This is known as a skewed binary search tree. If such a thing happens, then the BST basically transforms into a linked list and that is of no use to us. Therefore, we have this notion of keeping a BST balanced so that we don’t run into this problem.

这被称为倾斜的二进制搜索树。 如果发生这种情况，则BST基本上会转换为链接列表，这对我们没有用。 因此，我们有保持BST平衡的想法，这样就不会遇到这个问题。

The notion of balanced is defined differently by different approaches, like Red Black Trees or AVL trees. Further explanation of these trees is out of the scope of this article.

平衡的概念通过不同的方法(例如，红黑树或AVL树)有不同的定义。 这些树的进一步说明超出了本文的范围。

Coming back to arranging our data in a balanced BST: the keys to our BST would be the names of the students, and lexicographic matching would be used to determine the structure of the BST.

回到将数据安排在平衡的BST中：BST的关键将是学生的姓名，而词典编纂匹配将用于确定BST的结构。

Suppose that there were a million students taking the test. If our binary search tree is balanced, then the complexity of performing any operation is upper bounded by O(log(n)) . Hence, for 1 million nodes, the maximum number of nodes to be scanned would be just 14.

假设有一百万学生参加考试。 如果我们的二叉搜索树是平衡的，那么执行任何操作的复杂度都会受到O(log(n)) 。 因此，对于一百万个节点，要扫描的最大节点数仅为14个。

That’s a lot of complexity reduction simply by arranging the data in a certain manner. That is the advantage of representing data in a balanced Binary Search Tree.

只需按某种方式排列数据，就可以减少很多复杂性。 这就是平衡地表示数据的优势 二进制搜索树。

The main problem with the array-based approach was that we could not efficiently insert or delete an element from the array. And the problem with the linked list approach was that there was no efficient way for us to find an element in the linked list even if it were sorted.

基于数组的方法的主要问题是我们无法有效地从数组中插入或删除元素。 链表方法的问题在于，即使对链表进行排序，我们也无法找到有效的方法。

As for a balanced binary search tree, the time complexity to insert, delete, or search for an element is all bounded by O(log(n)) . And this is precisely what makes this data structure extremely exciting.

对于平衡的二叉搜索树，插入，删除或搜索元素的时间复杂度全部受O(log(n)) 。 这正是使此数据结构异常令人兴奋的原因。

However, we still haven’t solved our original problem. Given the name of a student, we want to find out the student sitting right behind and right in front of them. This boils down to finding the in-order successor and predecessor in the given Binary Search Tree.

但是，我们仍然没有解决我们原来的问题。 给定一个学生的名字，我们想找出坐在他们后面和前面的那个学生。 归结为在给定的二分搜索树中找到有序的后继者和前任者。

BST中的顺序遍历和排序顺序 (In-order Traversal and Sorted Order in a BST)

An interesting property of the binary search trees is that we can retrieve the elements in the sorted order (even reverse) by doing an in-order traversal over the binary search tree.

二进制搜索树的一个有趣特性是，通过对二进制搜索树进行有序遍历，我们可以按排序顺序(甚至反向)检索元素。

So the in-order successor of a node X is the element that comes right after X in the in-order traversal over the given BST. For our cheating problem, this in-order successor would be the student sitting in front of us.

因此，节点X的有序后继元素是在给定BST上有序遍历中X之后的元素。 对于我们的作弊问题，这个有序的继任者是坐在我们前面的学生。

The in-order predecessor of a node X is the element that comes right before X in the in-order traversal (or the element that comes right after X in the reverse in-order traversal) over the given BST. For our cheating problem, this in-order predecessor would be the student sitting right behind us.

节点X的有序前任元素是有序遍历中X之前的元素(或相反的元素是有序遍历中X之后的元素) 在指定的BST上进行有序遍历)。 对于我们的作弊问题，这个有序的前身是坐在我们后面的学生。

BST中的有序后继者 (In-order Successor in a BST)

There are two different cases that we need to handle when finding the in-order successor of a node in a BST.

在BST中找到节点的有序后继者时，我们需要处理两种不同的情况。

The first case is when the right child exists for the node whose in-order successor we are trying to find. Consider the following example.

第一种情况是当我们尝试查找其顺序后继者的节点存在正确的子代时。 考虑以下示例。

Here we wanted to find the in-order successor of the highlighted node 8. Since it has a right child, the in-order successor would be the leftmost node in the tree with a right child, or 15 as the root. So that node would be 10 in this case.

在这里，我们想找到突出显示的节点8的有序后继者。由于它有一个正确的子代，因此该有序继任者将是树中具有正确子代的最左边节点，或者以15为根 。 因此，在这种情况下，该节点将为10。

The second case is when there is no right child.

第二种情况是没有合适的孩子。

In this case, the in-order successor has two possibilities:

在这种情况下，有序后继者有两种可能性：

1. One is where the node under consideration is the left child of its parent. In this case, the in-order successor would be the parent itself. So for our given case, the in-order successor would be 10.
   一种是所考虑的节点是其父节点的左子节点的地方。 在这种情况下，有序后继者将是父代本身。 因此，对于给定的情况，有序后继者为10。
2. The second case is when the current node is the right child of it’s parent. And it doesn’t have a right child. So it is the rightmost node in the BST and it has no in-order successor.
   第二种情况是当前节点是其父节点的右子节点。 而且它没有合适的孩子。 因此它是BST中最右边的节点，并且没有顺序的后继节点。

Handling the first case is fairly simple for a binary search tree. For the second case, where the given node does not have a right child (or any parent pointers), we will have to rely on our good ol’ recursion mechanism and do an in-order traversal until we figure out the parent of our given node.

对于二叉搜索树，处理第一种情况非常简单。 对于第二种情况，当给定节点没有合适的子代(或任何父指针)时，我们将不得不依靠良好的ol'递归机制并进行有序遍历，直到我们弄清楚给定节点的父代节点。

So, the worst case complexity can be O(n) if the case above occurs.

因此，如果发生上述情况，则最坏情况下的复杂度可能为O(n)。

Using this algorithm, we can quickly find out the student who will be sitting right in front of us in the exam.

使用此算法，我们可以快速找出即将参加考试的学生。

BST中的有序前任 (In-order Predecessor in a BST)

This is the exact reverse of the previous case.

这与前一种情况完全相反。

Again, we need to handle two different cases when finding the in-order predecessor of a node in a BST. Look at the following diagrams and try to relate the two cases being referred to here.

同样，在BST中找到节点的有序前任时，我们需要处理两种不同的情况。 查看下图，并尝试将此处提到的两种情况联系起来。

This is the case where the node has a left child. We need to find the rightmost child of the tree rooted at this left child — the rightmost node in the tree rooted at 2.

这是节点有左子节点的情况。 我们需要找到以该左子节点为根的树的最右子节点-以2为根的树中最右节点。

No left child. So we need to find the parent.

没有左子。 所以我们需要找到父母。

If you look closely, I’ve just reversed the order of traversal here and the rest of the code is the same as before. (NOTE: this code is used when there is no left child of the node for which we want to find the in-order predecessor).

如果您仔细观察的话，我只是在这里反转了遍历的顺序，其余的代码与以前相同。 (注意：当我们要为其找到有序前任节点的节点没有左子节点时，将使用此代码)。

In-order predecessor becomes the reverse in-order successor.

有序前任成为反向有序后继。

Well now that you know how you should arrange the class seating arrangement list, go get some solid marks ???. Just kidding!! Cheating is bad — don’t ever do it!

好了，既然您知道如何安排班级座位安排表，那就加一个明显的标记???。 开玩笑！！ 作弊是不好的-永远不要这样做！

Hope you got the main idea behind the different usages for data structures and how to find the in-order successor and predecessor in a BST.

希望您对数据结构的不同用法以及如何在BST中找到有序的后继者和前任者有一个主要的了解。

EDIT: Kudos to Divya Godayal for pointing out a set of major mistakes in the initial draft and also for ensuring that the article flows nicely :) :)

编辑：对Divya Godayal表示感谢 ，他指出了初稿中的一系列重大错误，并且还确保了文章的流畅性:) :)

翻译自: https://www.freecodecamp.org/news/tree-traversals-explained-theyre-like-a-class-of-lazy-students-trying-to-cheat-on-their-exam-b46563211427/

一群算法