Bst with particular characteristics; Bst which keeps nodes with multiple interactions at the root

huangapple go评论75阅读模式
英文:

Bst with particular characteristics; Bst which keeps nodes with multiple interactions at the root

问题

我必须实现一种特定类型的二叉搜索树(BST),它会将具有多个交互的节点保持在上部。
具体来说:

  1. 每次将键 K 插入或在树中搜索时,通过一系列称为 CLIMB 的上升操作将其移动到根节点(保持 BST 的属性)。
  2. 如果在 FST 中搜索 K 元素,并在给定节点 N 中找到它,则将 CLIMB 操作应用于它。如果元素 K 不存在,则在搜索结束的叶子上应用该操作。
  3. 如果删除了一个节点,则在已删除节点的父节点上应用 CLIMB 操作。

我已经尝试了几天来实现它,但我无法做到。我想到了一个算法:
用新根替换旧根,并将旧根挂接到新根的左侧(如果小于新根)或右侧(如果大于新根)。此外,如果旧根小于新根,还要在旧根的右分支上查找新根的第一个最大元素,并将其移动到新根的右分支。反之亦然,如果它更大。

但我无法实现它。有人可以帮助我吗?
我确信对于专家来说这是小菜一碟,但对我来说却是一场噩梦。

这不是我第一次提出这个问题,在之前的问题中,我也输入了代码,但即使得到了积极的投票,也没有人能够回答我的问题,而且我现在知道所提供的代码也不是正确的方法。

链接到 Stack Overflow 问题

请帮忙。

英文:

I have to implement a particular type of BST that: keeps the nodes with multiple interactions in the upper part.
In particular:
1 Each time a K key is inserted or searched for in the tree, it is moved to the root (maintaining the property of being a BST), through a succession of ascent operations called CLIMB.
2 If the K element is searched in the FST and is found in a given node N, the CLIMB operation is applied on it. If element K is not present, the operation is applied on the leaf where the search ends.
3 If a node is removed, the CLIMB operation is applied on the parent node of the removed node.

I've been trying to implement it for days but I'm not capable. I thought of an algorithm:
Replace the old root with the new one and hook the old root to the left of the new one, if it is smaller, or to the right if it is larger. Also if it is the old root is smaller than the new one, look for the first largest element of the new root on the right branch of the old root, and move it by hooking it as the new root right branch. Vice versa if it is bigger.

But I can't implement. Can anyone help me?
I am sure that for an expert it is a triviality, but for me it is a nightmare.

It is not the first question I ask about it, in a past question I had also entered the code, however even if it was voted positively nobody was able to answer me, and the code presented now I am aware that it is not the right way.

https://stackoverflow.com/questions/61069856/i-dont-understand-how-to-move-portions-of-a-tree

Help.

答案1

得分: 0

假设我们正在调用 climb(n)。从树中删除以 n 为根的子树,并将其放置为新的根。不幸的是,我们无法将整个旧树放在 n 的任何子节点中并结束。

我们唯一能确定的是,如果 [l, u] 是以根为 n 的子树中存储的值的范围,那么在该子树之外的所有节点都位于该范围之外。实际上,这适用于所有子树。然而,您的方法中的关键点在于:您假设“旧树”中的所有值都位于该范围的一侧,而实际上它们可以围绕该范围排列。也就是说,想象一下在根的右子节点的左子节点(7)上调用 climb

                            5
                3                     8
               ...                7        9
               ...             6             ...

无论您将5放在节点7的哪一侧,都会是错误的。要么5或8必须被错误放置。

利用这一事实,我们可以从 parent(n) 回溯,直到达到旧根,并将沿路径遇到的所有子树放入新树中,使用标准的BST插入:

climb(n):
    // 获取新根并从以 old_root 为根的树中移除它
    old_root = root(n)
    new_root = n
    remove_node(old_root, n)
    
    // 迭代 n 的祖先节点直到根
    node = parent(n)
    while node != nil do
        // 从原始树中移除当前祖先节点node
        next = parent(node)
        remove_child(parent(node), node)
        
        // 将节点插入新树仍然附加的所有节点仍然是节点的子节点
        insert_node(new_root, node)
        node = next
    done

    return new_root

由于上述关于范围的规则,这将在每次迭代后产生一个有效的BST。然而,在每次迭代中,将一个新的子树添加为 new_root 的最右叶子的最右子节点或最左叶子的最左子节点,因此可能是个不错的主意重新平衡以 left_child(new_root)right_child(new_root) 为根的子树,因为树可能很快变得不平衡。

英文:

Suppose we're calling climb(n). Remove the subtree with n as root from the tree and place it as the new root. Unfortunately we can't place the entire old tree in any child of n and call it a day.

The only thing we can say for sure is that if [l, u] is the range of values stored in the subtree with root n, then all nodes outside of that subtree lie outside of that range. This applies to all subtrees in fact. Here however also the crux with your approach lies: you're assuming that all values in the "old tree" lie on one side of that range, when in fact they can be arranged around that range. I.e. imagine calling climb on the left child of the right child of root (7):

                        5
            3                     8
           ...                7        9
           ...             6             ...

No matter on which side of node 7 you place 5, it'll be wrong. Either 5 or 8 must be misplaced.

Using this fact, we can backtrack from parent(n) until we reach the old root and place all subtrees encountered along the path in the new tree using a standard BST-insert:

climb(n):
    // get the new-root and remove it from the tree rooted at old_root
    old_root = root(n)
    new_root = n
    remove_node(old_root, n)
    
    // iterate ancestors of n up to root
    node = parent(n)
    while node != nil do
        // remove current ancestor (node) from the original tree
        next = parent(node)
        remove_child(parent(node), node)
        
        // insert node into the new tree (all nodes that are still appended remain children of node)
        insert_node(new_root, node)
        node = next
    done

    return new_root

Thanks to the above stated rule about ranges, this will produce a valid BST after each iteration. However in each iteration a new subtree will be added as either right-most child of the right-most leaf or left-most child of the left-most leaf of the tree rooted at new_root, so it might be a good idea to rebalance the subtrees rooted at left_child(new_root) and right_child(new_root), since the tree will become rather imbalanced pretty soon.

huangapple
  • 本文由 发表于 2020年4月9日 06:41:01
  • 转载请务必保留本文链接:https://go.coder-hub.com/61111186.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定