将排序的双向链表转换为常量 space 中的平衡 BST

Question

有什么方法可以将已排序的双向链表就地转换为平衡 BST 常量 space？

我发现 ([1]、[2]、[3]) 的最佳方法利用递归，但它们需要的不仅仅是常量 space 用于递归堆栈。我想可能有一些方法可以在没有递归的情况下预先计算索引。但是，我找不到好的方法。

这道题是一道面试题解法的一部分，该题需要将 2 个 BST 合并成一个平衡搜索树，其常数为 space [4]。

[1] Converting a sorted doubly linked list to a BST
[2] http://www.geeksforgeeks.org/in-place-conversion-of-sorted-dll-to-balanced-bst/
[3] http://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/
[4] http://www.careercup.com/question?id=5261732222074880

Answer 1

您正在寻找的是 vine_to_tree() 之类的东西，通常用作重新平衡二叉搜索树的一部分。正常过程从 tree_to_vine() 开始，它创建一个只有正确节点的树，本质上是一个排序的双向链表，这是您开始的地方。然后 vine_to_tree() 用于创建平衡二叉树。通常涉及几个函数，但它是一个非递归算法。

进行网络搜索，您应该会找到一些 vine_to_tree() 的示例，例如：

http://web.eecs.umich.edu/~qstout/pap/CACM86.pdf

在这种情况下，您想要的是使用 perfect_leaves() 的 vine_to_tree()。示例代码：

struct node {
    size_t value;
    node *p_left;
    node *p_right;
};
// defines to use for double link list nodes
#define p_prev p_left
#define p_next p_right

size_t floor_power_of_two(size_t size)
{
size_t n = 1;
    while(n <= size)
        n = n + n;
    return n/2;
}

size_t ceil_power_of_two(size_t size)
{
size_t n = 1;
    while(n < size)
        n = n + n;
    return n;
}

// split vine nodes, placing all even (0, 2, 4, ...) leaves on left branches
// p_root->p_right->p_left = 0, p_root->p_right->p_right->p_left = 2
node * perfect_leaves(node * p_root, size_t leaf_count, size_t size)
{
node *p_scanner;
node *p_leaf;
size_t i;
size_t hole_count;
size_t next_hole;
size_t hole_index;
size_t leaf_positions;

    if(leaf_count == 0)
        return p_root;
    leaf_positions = ceil_power_of_two(size+1)/2;
    hole_count = leaf_positions - leaf_count;
    hole_index = 1;
    next_hole = leaf_positions / hole_count;
    p_scanner = p_root;
    for(i = 1; i < leaf_positions; i += 1){
        if(i == next_hole){
            p_scanner = p_scanner->p_right;
            hole_index = hole_index + 1;
            next_hole = (hole_index * leaf_positions) / hole_count;
        } else {
            p_leaf = p_scanner->p_right;
            p_scanner->p_right = p_leaf->p_right;
            p_scanner = p_scanner->p_right;
            p_scanner->p_left = p_leaf;
            p_leaf->p_right = NULL;
        }
    }
    return p_root;
}

//  left rotate sub-tree
node * compression(node * p_root, size_t count)
{
node *p_scanner;
node *p_child;
size_t i;
    p_scanner = p_root;
    for(i = 1; i <= count; i += 1){
        p_child = p_scanner->p_right;
        p_scanner->p_right = p_child->p_right;
        p_scanner = p_scanner->p_right;
        p_child->p_right = p_scanner->p_left;
        p_scanner->p_left = p_child;
    }
    return p_root;
}

//  convert vine to perfect balanced tree
node * vine_to_tree(node *p_root, size_t size)
{
size_t leaf_count; // # of leaves if not full tree
    leaf_count = size + 1 - floor_power_of_two(size+1);
    perfect_leaves(p_root, leaf_count, size);
    size = size - leaf_count;
    while(size > 1){
        compression(p_root, size / 2);
        size = size / 2;
    }
    return p_root;
}

将排序的双向链表转换为常量 space 中的平衡 BST

Convert a sorted doubly linked list to a balanced BST in-place in constant space

sorting

recursion

linked-list

binary-search-tree