1回答

liuyubobobo

2018-09-26

已采纳

你对“有序性”的理解是有误的。

有序的意思是指：数据结构本身不仅可以存储这些数据，同时，还可以维护这些数据之间的大小关系（而不是放入拿出的顺序）。

所以，数组可以是有序的，也可以是无序的，看你实现的具体逻辑。如果在插入一个元素的时候，始终维护这个数组内所有的元素都是有序的，找到这个新元素的位置来插入，这样的数组就是有序数组；如果每次插入一个元素都直接将新元素放在最后的位置，就是一个无序数组。链表同理。

而二分搜索树这种结构也是有序的，回忆一下：通过二分搜索树的中序遍历，就可以得到所存储的所有元素的顺序排列，这说明二分搜索树维护了元素间的顺序（虽然不像有序的数组或者链表那么直观）。

有序的意义绝不仅仅在于能取出最大值和最小值。还可以：找到任意一个元素的下一个元素(succesor)；上一个元素(predecessor)；查找所存储的数据中的第k大元素或第k小元素(select)；看某个元素是排名第几的元素(rank)，等等。这些操作，都需要数据结构本身维护数据的顺序，才可以快速得出。

对于二分搜索树的这些操作，除了最大值和最小值，我并没有给出具体实现。在6-13小节有提及。有兴趣的同学，可以尝试自己编程完成。实现这些接口：）在我的课程，《算法与数据结构》的补充代码中，给出了succesor和predecessor两个接口的实现，有兴趣可以参考。Java代码传送门：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(Java)/Optional-06-Predecessor-and-Successor-in-BST/src/bobo/algo/BST.java

如果理解了什么是有序性，就会明白：说集合是有序的，或者无序的，都不对。集合是一种抽象出具结构，我们可以实现一个有序的集合，也可以实现一个无序的集合。这依赖于我们所选择的具体底层实现结构和实现逻辑。我们可以使用数组，链表，哈希表，实现无序的集合；也可以使用数组，链表，二分搜索树，实现有序的集合。映射同理。如果感兴趣，也强烈建议即使用这些数据结构，实现一遍有序的集合，再使用这些数据结构，实现无序的集合。仔细体会一下，什么叫有序性，为了维护有序性，需要多做哪些工作（对于链表或者数组作为底层数据结构的实现），以及所使用的数据结构有什么本质的不同（对于二分搜索树，平衡二叉树和哈希表）；什么是抽象数据结构，我们可以使用完全不同的数据结构和逻辑，实现完全相同的接口，甚至解决完全相同的问题（虽然时间复杂度可能不同）

和这个问题相关的讨论，也可以参考这里：https://coding.imooc.com/learn/questiondetail/62784.html

加油！：）

5

2

李爽爽爽爽

非常感谢！

2018-09-26

共2条回复