Tag: algorithm

使用mergesort对链接列表进行排序

我目前正在研究mergesort算法。 我有三个function。 list_sort_merge，mergelist和splitlist。 list_sort_merge调用另外两个来拆分和合并列表。 我无法正常工作。 那么当我运行GDB时会发生的事情是我通过split函数并自己获取每个数字，例如以下示例： 427 42.7 4.2.7 然后mergesort出现了，并且我发生了段错误。 会发生什么是right_list和left_list没有传递给mergesort。 当mergesort在函数comp_proc中进行比较时，它表示它们都是NULL。 我认为问题来自分裂function。 谁能看到我在这里做错了什么？

完美平衡的二进制搜索树

我有关于Balanced BST的理论问题。 我想构建具有2^k – 1节点的Perfect Balanced Tree ，来自常规的unbalanced BST 。 我能想到的最简单的解决方案是使用排序的Array/Linked list并递归地将数组划分为子数组，并从中构建Perfect Balanced BST 。 但是，在树大小非常大的情况下，我需要创建一个相同大小的Array/List ，因此这种方法会占用大量内存。 另一种选择是使用AVL旋转function，逐个元素插入并根据树平衡因子平衡树和旋转 – 左和右子树的三个高度。 我的问题是，我对我的假设是对的吗？ 还有其他方法可以从不平衡的BST创建完美的BST吗？