练习3.6: Skiena算法设计手册

Question

我正在为面试做准备，并试图解决书中的练习问题。

3-6。5描述了如何修改任何平衡的树数据结构，例如搜索、插入、删除、最小和最大仍然需要O(log )时间，而后继和前任现在则各花O(1)时间。需要修改哪些操作才能支持这一点？

解决方案:维护指向后继和前任的额外指针。更新insert和delete的指针。

没别的对吧？或者还有其他的诡计。

谢谢

Answer 1

树上的典型操作是插入、删除和遍历--包括后续和先前操作。当一棵树被平衡时，就会有一个内部再平衡操作，因此需要修改哪些操作的答案取决于您想要解释有关外部接口还是内部接口的“操作”。

答案通常是肯定的--您需要保持一个指向后继元素(下一个元素大于当前元素)和前一个元素的指针。

但问题是，如何保持这些新提出的指针在插入、删除和再平衡的情况下保持最新。您可以通过归纳进行推理--给定一个平衡的树T，使得问题中给出的条件适用于T，插入一个新节点V将如何影响树的所有其他节点，特别是那些V将成为新的继承者和前身的节点。您必须证明只有O(log n)节点才会受到影响、定位和修改，否则您就不能将讨论的操作保持在必要的复杂性范围内。

Answer 2

`void delete( root, val ) 
{
    node = findNode( root, &par );
    nodePred = node->pred;
    nodeSucc = node->succ;
    if ( nodeSucc )
        nodeSucc->pred = nodePred;
    if( nodePred )
        nodePred->succ = nodeSucc;
    // Node delete the node as usual as only parent child relation changes and
    // succ pred relation will still remain intact
}

void insert( root, node ) 
{
    if ( root == NULL ) {
        root = node;
        node->succ = node->pred = NULL;
        return;
    }
    curr = root;
    while ( curr ) {
        par = curr;
        curr = node->val < curr->val ?  curr->left : curr->right;
    }
    if ( node->val < par->val ) {
        par->left = node;
        parPred = par->pred;
        node->succ = par;
        node->pred = parPred;
        par->pred = node;
        if ( oldPred )
            oldPred->succ = node;
    } else {
        par->right = node;
        oldSucc = par->succ;
        node->pred = par;
        node->succ = oldSucc;
        par->succ = node;
        if ( oldSucc )
            oldSucc->pred = node;
    }
}`