创建一个自订购的二进制树

Question

我有一个作业，我需要使用二进制搜索树并将其更改为自行订单本身，以便最多访问的项目（优先级更高）在树的顶部，根是最访问的节点。

这位教授给了我BST和节点结构，但是试图让我的头围绕算法更新树，因为插入了东西使我感到困惑。

我知道，随着插入的发生，它会检查当前节点的数据是否比当前节点更大或更大，然后递归地朝正确的方向行驶，直到找到空指针并在此处插入自身。插入后，将优先级提高了1。

template <class Type>
void BinarySearchTree<Type> ::  insert( const Type & x, BinaryNode<Type> * & t )
{
    if( t == NULL )
        t = new BinaryNode<Type>( x, NULL, NULL );
    else if( x < t->element )
        insert( x, t->left );
    else if( t->element < x )
        insert( x, t->right );
    else
        t->priority++;  // Duplicate; do nothing for right now
}

现在，我需要弄清楚节点何时相等，如何重新排序树，以使当前节点（谁等于已经存在的节点）找到现有节点，增加该节点的优先级，然后将其移动根是优先级。

我想我有一个想法，即AVL逻辑可以起作用，并且当发生轮班时，它将是右旋转或左右旋转。

这是我困惑的地方，真的不知道从哪里开始创建算法来解决问题。由于AVL算法可以跟踪树的平衡，然后相应地向左或向右旋转节点，因此这棵树不必担心保持平衡，只是优先级最高的节点没有更高优先级的孩子。

Answer 1

只有两个指针：

1. 如果您想真正将优先队列和二进制搜索树的想法结合在一起，请考虑将堆和BST结合在一个结构中。
2. 有一个概念 自组织清单. 。这个想法是将最近访问的元素移至（或朝向前线），以加快对未来访问相同元素的访问，从而“学习”随时间推移的元素分布（质量取决于特定的实现）。也许您可以适应树木？

---

剧透： 仅当您无法自己提出某些内容时，请按照以下链接进行以下链接。

1.这称为 特雷普.
2. 张开树 实施这个想法。

Answer 2

看看张开树，它们确实是您所需要的。您将必须修改splay函数，而不是将每个访问的节点一直移至树，而要缓慢向上移动