二叉树和快速排序? [英] Binary trees and quicksort?

问题描述

我有一个家庭作业，内容如下(不要发火/担心，我不是要你做我的作业):

编写一个程序，该程序使用二进制搜索使用快速排序"方法对一组数字进行排序 树.推荐的实现方式是使用递归算法.

这是什么意思?到目前为止，这是我的解释，正如我在下面解释的那样，我认为两者都有缺陷:

A.从用户那里获取数字数组(整数或其他).使用数组上的常规quicksort算法对它们进行快速排序.然后将内容放入二叉搜索树中，使数组的中间元素成为根，等等.

B.使用二进制搜索树的标准属性，从用户那里获取数字，将其直接一一直接放入树中.树是分类的"，一切都很好-完成.

这就是为什么我感到困惑.选项"A"可以完成分配所要求的一切，只是它并没有真正使用二叉树，而是因为它是二叉树上的一项家庭作业，所以最后一刻都没有使用二叉树.这使我认为预定的练习不可能是'A'，因为主要主题不是快速排序，而是二叉树.

但是选项'B'并不是更好-它根本不使用quicksort！所以，我很困惑.

这是我的问题:

1. 如果解释是选项'A'，请这样说，我没有问题，谢谢您的时间，再见.

2. 如果解释是选项'B'，为什么在二进制树中插入值的排序方法与quicksort相同?他们并没有内在的相似，只是他们都(按照我到目前为止所学的形式)都使用递归分而治之策略并将他们的输入一分为二.

3. 如果还有其他解释...我该怎么办?

解决方案

这是一个非常酷的发现.假设您按照选择的顺序将一系列值插入二叉搜索树中.一些值将在左侧子树中结束，而某些值将在右侧子树中结束.具体来说，左子树中的值小于根，右子树中的值大于根.

现在，假设您正在对相同的元素进行快速排序，只是您将BST根目录中的值用作轴.然后，将一堆元素放入左侧子数组中-小于枢轴的元素-并将一堆元素放入右侧子数组中-大于枢轴的元素.请注意，BST左子树和右子树中的元素将完全对应于第一个quicksort步骤的左子数组和右子数组中的元素！

将内容放入BST中后，将元素与根进行比较后，您将下降到左侧或右侧子树中，并与此处的根进行比较.在quicksort中，将数组划分为左右子数组后，您将为左侧选择一个轴并对其进行分区，然后向右侧选择一个轴并对其进行分区.再次，这里有一个漂亮的对应关系-整个BST中的每个子树都对应于使用子树的根执行快速排序中的关键步骤，然后递归地在左右子树中进行相同的操作.

再进一步，我们得到以下主张:

每次运行的快速排序都对应一个BST，其中根是初始枢轴，每个左和右子树对应于相应子数组中的快速排序递归调用.

这种连接非常牢固:在将元素插入BST时，将在quicksort的运行中进行每次比较，反之亦然.比较不是按照相同的顺序进行的，但是仍然可以进行.

所以我怀疑您的讲师要您做的是以不同的方式实现快速排序:不是对数组和数据透视表进行操作，而是按照您想要的任何顺序将所有内容放入BST中，然后步行有序遍历的树，以按排序的顺序取回元素.

这样做的一个非常酷的结果是，您可以将quicksort视为本质上是对空间进行优化的二叉树排序的实现.分区和透视步骤对应于构建左右子树，不需要显式指针.

I have a homework assignment that reads as follows (don't flame/worry, I am not asking you to do my homework):

Write a program that sorts a set of numbers by using the Quick Sort method using a binary search tree. The recommended implementation is to use a recursive algorithm.

What does this mean? Here are my interpretations thus far, and as I explain below, I think both are flawed:

A. Get an array of numbers (integers, or whatever) from the user. Quicksort them with the normal quicksort algorithm on arrays. Then put stuff into a binary search tree, make the middle element of the array the root, et cetera, done.

B. Get numbers from the user, put them directly one by one into the tree, using standard properties of binary search trees. Tree is 'sorted', all is well--done.

Here's why I'm confused. Option 'A' does everything the assignment asks for, except it doesn't really use the binary tree so much as it throws it last minute in the end since it's a homework assignment on binary trees. This makes me think the intended exercise couldn't have been 'A', since the main topic's not quicksort, but binary trees.

But option 'B' isn't much better--it doesn't use quicksort at all! So, I'm confused.

Here are my questions:

1. if the interpretation is option 'A', just say so, I have no questions, thank you for your time, goodbye.

2. if the interpretation is option 'B', why is the sorting method used for inserting values in binary trees the same as quicksort? they don't seem inherently similar other than the fact that they both (in the forms I've learned so far) use the recursion divide-and-conquer strategy and divide their input in two.

3. if the interpretation is something else...what am I supposed to do?

解决方案

Here's a really cool observation. Suppose you insert a series of values into a binary search tree in some order of your choosing. Some values will end up in the left subtree, and some values will end in the right subtree. Specifically, the values in the left subtree are less than the root, and the values of the right subtree are greater than the root.

Now, imagine that you were quicksorting the same elements, except that you use the value that was in the root of the BST as the pivot. You'd then put a bunch of elements into the left subarray - the ones less than the pivot - and a bunch of elements into the right subarray - the ones greater than the pivot. Notice that the elements in the left subtree and the right subtree of the BST will correspond perfectly to the elements in the left subarray and the right subarray of the first quicksort step!

When you're putting things into a BST, after you've compared the element against the root, you'd then descend into either the left or right subtree and compare against the root there. In quicksort, after you've partitioned the array into a left and right subarray, you'll pick a pivot for the left and partition it, and pick a pivot to the right and partition it. Again, there's a beautiful correspondence here - each subtree in the the overall BST corresponds to doing a pivot step in quicksort using the root of the subtree, then recursively doing the same in the left and right subtrees.

Taking this a step further, we get the following claim:

Every run of quicksort corresponds to a BST, where the root is the initial pivot and each left and right subtree corresponds to the quicksort recursive call in the appropriate subarrays.

This connection is extremely strong: every comparison made in that run of quicksort will be made when inserting the elements into the BST and vice-versa. The comparisons aren't made in the same order, but they're still made nonetheless.

So I suspect that what your instructor is asking you to do is to implement quicksort in a different way: rather than doing manipulations on arrays and pivots, instead just toss everything into a BST in whatever order you'd like, then walk the tree with an inorder traversal to get back the elements in sorted order.

A really cool consequence of this is that you can think of quicksort as essentially a space-optimized implementation of binary tree sort. The partitioning and pivoting steps correspond to building left and right subtrees and no explicit pointers are needed.

这篇关于二叉树和快速排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！