二叉搜索树 - 排序？
dev*_*r87 2 sorting binary-search-tree data-structures
我不明白二进制搜索树总是被定义为"已排序".我得到一个二进制堆的数组表示,你有一个完全排序的数组.我没有看到二进制搜索树的数组表示,所以我很难看到它们像数组一样排序,例如[0,1,2,3,4,5],而是相对于每个节点排序.考虑BST在概念上"排序"的正确方法是什么？
有许多类型的二叉搜索树.所有这些都有一个共同点:它们满足一个不变量,它允许二进制搜索,即一个顺序关系,通过该顺序关系,可以将树中的每个元素与树中的任何其他元素进行比较,在总预订中.
那是什么意思？
让我们考虑一下教科书中BST不变量的典型陈述,该陈述指出每个节点的密钥大于其左子树中的所有密钥,并且小于其右子树中的所有密钥.我们省略了比较相等的键的冲突解决细节.
BST是什么样的？这是一个例子:
我将它解释为一个三岁的孩子的方法是尝试将所有节点折叠到叶子的底层,让它们倒下.或者,对于高中生,从每个节点/键上绘制一条线,将它们投影在x轴上.一旦你这样做,很明显键已经处于(升序)顺序.
这个虚构和随意的观察是否类似于我们对排序序列的定义？是的.由于BST的元素满足总预订顺序,因此BST的有序遍历必须按顺序生成这些元素(例如:证明它).
它等同于状态,如果我们通过有序遍历存储BST的键,则在数组中对数组进行排序.
因此,通过我们对BST的初始定义,有序遍历是将一个人视为"已排序"的直观方式.
