具有给定节点指针的恒定时间后继者和前任者的平衡树？

Question

我被问到这个问题，我个人觉得很难：

创建一个数据结构可以：

插入元素，删除元素，搜索元素，在时间 O(log n)

此外，它应该具有以下两个在时间 O(1) 中工作的功能：

下一个（x）：给定一个指向值为 x 的节点的指针，return 一个指向具有比 x 大的最小值的节点的指针。
上一个(x) 给定一个指向值为 x 的节点的指针，return 一个指向具有比 x 最大最小值的节点的指针。

Answer 1

如果您的元素是整数，您可以使用 y-fast trie 支持 O(log log m) 中提到的所有操作。此外，几乎任何搜索树都允许在 O(log n) 时间内完成这些操作，只需先向上然后向下（不过需要高度集中才能不弄乱顺序）

Answer 2

与大多数自平衡树一样，B+ tree 提供插入、删除和搜索操作，时间复杂度为 O(log n)。

在B+树中，一个叶子节点在一个数组中承载多个键，所以"pointer to node with value x"的概念并不存在，但我们可以将其定义为元组（指针，索引），其中pointer是指向节点，index是存放x的slot。

在 B+ 树中，底层节点包含所有键，并且这些节点经常被 linked，通常只在向前方向（即向右），但很有可能同样在反方向维护一个link，不增加上述操作的时间复杂度

考虑到这两点，prev-next 操作显然可以在 O(1) 时间内执行。

Answer 3

如果每个节点都包含一个指向其后继节点的指针和一个指向其前导节点的指针，或者等效地 - 如果您同时维护一个双链表和一个树，其中树中的每个节点都指向其在列表中的等效节点反之亦然——你会得到你想要的。在 insert/delete 上更新列表是 O(1)（在找到树中最近的节点之后）。搜索是在树上执行的。继任者/前任都在名单上执行。

Answer 4

@RogerLindsjö 从评论中得出的想法很好。本质上，保持一个规则的、平衡的 BST，然后通过节点线程化一个双向链表，使它们按排序顺序排列。这样，给定一个指向树中节点的指针，您只需跟随每个节点中的下一个或上一个指针，就可以找到小于它的最大值或大于它的最小值。

您可以通过插入和删除来维护此列表，而无需更改插入或删除的总体运行时间。例如，下面是插入元素 x:

的方法

执行标准 BST 后继查询以查找树中大于 x 的最小值，并执行标准 BST 前导查询以查找树中小于 x 的最大值。每次搜索都需要时间 O(log n) 才能完成。
进行常规 BST 插入以插入 x。然后，将其 next 和 previous 指针设置为您在上一步中找到的两个元素，并更新这些节点以指向您的新节点 x。这也需要时间 O(log n).

插入的总时间为 O(log n)，与平衡树所能提供的相匹配。

删除就交给你了，同样可以维护链表指针而不改变操作的整体开销。

Answer 5

您可以在平衡树的节点中使用两个指针，即pred - 前驱和succ - 后继。在向树中插入一个节点或从树中删除一个节点时，您只需进行一些指针操作，相当于双向链表中的操作。在每种情况下，时间复杂度都是 O(1)。

我在下面的 AVL Tree 的情况下提供了插入和删除的实现。完整的实现可用 here.

node的结构

template<typename T>
struct node {
    T key;
    int freq;
    node<T> *left;
    node<T> *right;
    node<T> *pred;
    node<T> *succ;
    int height;
    node(T key): key(key), freq(1), 
                left(nullptr), 
                right(nullptr), 
                height(1),
                pred(nullptr),
                succ(nullptr) {}
};

insert函数

node<T> *insert(node<T> *root, T key) {
    if(root == nullptr)
        return new node<T>(key);
    
    if(!comp(key, root->key) && !comp(root->key, key)) {
        ++root->freq;
    } else if(comp(key, root->key)) {
        if(root->left == nullptr) {
            node<T> *new_node = new node<T>(key);
            /* set the pred and succ ptrs*/
            new_node->succ = root;
            new_node->pred = root->pred;
            if(root->pred != nullptr)
                root->pred->succ = new_node;
            root->pred = new_node;

            root->left = new_node;
        } else {
            root->left = insert(root->left, key);
        }
    } else {
        if(root->right == nullptr) {
            node<T> *new_node = new node<T>(key);
            /* set the pred and succ ptrs*/
            new_node->pred = root;
            new_node->succ = root->succ;
            if(root->succ != nullptr)
                root->succ->pred = new_node;
            root->succ = new_node;

            root->right = new_node;
        } else {
            root->right = insert(root->right, key);
        }
    }
    
    root->height = max(height(root->left), height(root->right)) + 1;

    int bf = balance_factor(root);
    node<T> *left = root->left;
    node<T> *right = root->right;
    if(bf > 1 && left != nullptr && comp(key, left->key)) {
        /* 
            node was inserted at left subtree of left child
            fix - right rotate root
        */ 
        root = rotate_right(root);
    } else if(bf > 1 && left != nullptr && comp(left->key, key)) {
        /* 
            node was inserted at right subtree of left child
            fix - left rotate left child
                - right rotate root
        */
        root->left = rotate_left(root->left);
        root = rotate_right(root);
    } else if(bf < -1 && right != nullptr && comp(right->key, key)) {
        /*
            node was inserted at right subtree of right child
            fix - left rotate root
        */
        root = rotate_left(root);
    } else if(bf < -1 && right != nullptr && comp(key, right->key)) {
        /*
            node was inserted at left subtree of right child
            fix - right rotate right child
                - left roatate root
        */
        root->right = rotate_right(root->right);
        root = rotate_left(root);
    }

    return root;
}

erase函数

node<T> *erase(node<T> *root, T key) {
    if(root == nullptr)
        return nullptr;
    
    if(comp(key, root->key)) {
        root->left = erase(root->left, key);
    } else if(comp(root->key, key)) {
        root->right = erase(root->right, key);
    } else {
        if(root->left == nullptr || root->right == nullptr) {
            /* update pred and succ ptrs */
            if(root->succ != nullptr)
                root->succ->pred = root->pred;
            if(root->pred != nullptr)
                root->pred->succ = root->succ;
            
            if(root->right == nullptr) {
                node<T> *temp = root->left;
                delete root;
                root = temp;
            } else  {
                node<T> *temp = root->right;
                delete root;
                root = temp;
            }
        } else {
            // node<T> *succ = minVal(root->right);
            root->key = root->succ->key;
            root->freq = root->succ->freq;
            root->right = erase(root->right, root->succ->key);
        }
    }
        
    if(root != nullptr) {
        root->height = max(height(root->left), height(root->right)) + 1;
        int bf_root = balance_factor(root);
        if(bf_root > 1) {
            /*
                case R 
            */
            int bf_left = balance_factor(root->left);
            if(bf_left >= 0) {
                /* 
                    case R0 and R1
                */
                root = rotate_right(root);
            } else {
                /*
                    case R -1
                */
                root->left = rotate_left(root->left);
                root = rotate_right(root);
            }
        } else if(bf_root < -1) {
            /*
                Case L
            */
            int bf_right = balance_factor(root->right);
            if(bf_right <= 0) {
                /*
                    case L0 and L -1 
                */
                root = rotate_left(root);
            } else {
                /*
                    case L1
                */
                root->right = rotate_right(root->right);
                root = rotate_left(root);
            }
        }
    }
    return root;
}

具有给定节点指针的恒定时间后继者和前任者的平衡树？

Balanced tree with constant-time successor and predecessor given node pointers?

algorithm

data-structures

avl-tree