bit*_*ion 13 algorithm tree binary-tree binary-search-tree data-structures
如何将二叉树就地转换为二叉搜索树,即我们不能使用任何额外的空间.
Pet*_*ter 14
将二进制树转换为双向链表 - 可以在O(n)中就地完成
然后使用合并排序对其进行排序,nlogn
将列表转换回树 - O(n)
简单的nlogn解决方案.
nat*_*ose 11
你没有给予太多的帮助,但是如果要求是我认为的那样,你就已经创建了一个二进制树并且坐在内存中,但没有排序(无论如何你想要它的排序方式).
我假设树节点看起来像
struct tree_node {
struct tree_node * left;
struct tree_node * right;
data_t data;
};
我也假设你可以读C
虽然我们可以坐下来想知道为什么这个树是在没有按照排序顺序创建的情况下创建的,这对我们没有任何好处,所以我会忽略它并只处理它的排序.
不使用额外空间的要求是奇怪的.暂时会有额外的空间,如果只是在堆栈上.我将假设它意味着调用malloc或类似的东西,并且结果树不得不使用比原始未排序树更多的内存.
第一个也是最简单的解决方案是对未排序的树进行预序遍历,从树中删除每个节点并对新树进行排序插入.这是O(n + n log(n)),其为O(n log(n)).
如果这不是他们想要的东西,你将不得不使用旋转和东西.....这太可怕了!
我认为你可以通过做一个奇怪版本的堆排序来做到这一点,但我遇到了问题.我想到的另一件事情,即速度非常慢,会在树上做一个奇怪的冒泡版本.
为此,每个节点都会被比较,并且可能会与每个节点的直接子节点(因此也与其父节点)重复交换,直到您遍历树并且找不到任何需要的交换.执行一个振动器排序(从左到右和从右到左的冒泡排序)版本的效果最好,并且在初始传递之后,您不需要遍历那些看起来没有关于它的父级的子树.
我敢肯定,这个算法是在我之前被其他人想到的,并且有一个我不知道的名字,或者它在某些方面存在根本缺陷,我没有看到.
提出第二个建议的运行时计算是非常复杂的.起初我认为它只是O(n ^ 2),就像泡沫和振动器类型一样,但我不能满足自己,子树遍历避免可能不会赢得足够的比O(n ^更好) 2).基本上泡沫和振动器排序也可以得到这种优化,但只有在总排序发生得很早的末端才能达到极限.使用这个树版本,您可以获得机会,以避免在集合中间的块.好吧,就像我说的那样,它可能存在致命缺陷.