Treap树理解

简介

随机平衡二叉查找树

Treap树其实就是BST＋Heap，在值的比较上，按照二叉树的性质，在优先度的比较上，按照堆的性质，当然最小最大堆都可以；

Treap树算是平衡树中的一种，但是其又并不满足于平衡树中的性质－“左右子树的高度小于等于1”，当然，我们还知道还有其他的平衡树，比如红黑树，Splay Tree（伸展树），Size Balance Tree，AVL树等（后面打算做个平衡树的总结）

性质

先看二叉树

左右子树上结点的值均小于其跟结点的值；
左右子树均是二叉搜索树

再看堆（以最小堆为例）

任何一个结点的优先级的值都要小于其跟结点的优先级的值（其优先值随机生成）；

操作

查找

其操作和BST一样，通过判断结点的值进行左右的查找，不再赘述；

插入

（重点！！！）

我们先来了解一下左旋转和右旋转的概念

上图左边那幅图是X结点优先级的值小于Y结点优先级的值，则需要右旋转，右边那幅图则是Y结点优先级的值小于X结点优先级的值，则需要左旋转（以最小堆为例，最终都是为了让优先级小的值在上面，大的在下面，这也是堆的性质）；

按照BST的性质插入结点到叶子上；
按照堆的性质维护（左或者右旋转）树；

删除

删除的结点的情况有几种，需要掌握；

叶子结点：直接删除；
只包含一个叶子结点的结点：将叶子结点赋到该结点上；
正常结点：找左右子结点中优先级小的结点，进行反方向的旋转，如果左结点小，则右旋转，如果右结点小，则左旋，当然删除的还是它自己（注意应该先旋转，后删除）

实现

代码用C++实现：

Treap.hpp

//
//  Treap.hpp
//  Treap
//
//  Created by George on 16/10/5.
//  Copyright © 2016年 George. All rights reserved.
//

#ifndef Treap_hpp
#define Treap_hpp

#include <stdio.h>

namespace Treap {
    
    class TreeNode {
    public:
        TreeNode();
        TreeNode(int value, int priority);
        ~TreeNode();
    
        TreeNode * _left;
        TreeNode * _right;
        int _key;
        int _priority;
    };
    
    class Tree {
    public:
        Tree();
        ~Tree();
        
        void Insert(TreeNode* node, TreeNode* &root);
        void Delete(int key, TreeNode* &root);
        TreeNode* Search(int key, TreeNode* &root);
        void Traverse(TreeNode* root);
        
        TreeNode * _root;
    private:
        void insertNode(TreeNode* node);
        void deleteNode(int key);
        TreeNode* searchNode(int key);
        void traverse();
        void rotateLeft(TreeNode* &node);
        void rotateRight(TreeNode* &node);
    };
    
    void insertNode();
    void deleteNode();
    void searchNode();
    void traverseNode();
}

#endif /* Treap_hpp */

Treap.cpp

//
//  Treap.cpp
//  Treap
//
//  Created by George on 16/10/5.
//  Copyright © 2016年 George. All rights reserved.
//

#include "Treap.hpp"
#include <cassert>
#include <stack>
#include <iostream>
#include <random>
#include <ctime>
#include <string>

namespace Treap {
    
    void LogNode(TreeNode* node) {
        std::cout << "key :" << node->_key << ", priority :" << node->_priority << std::endl;
    }
    
    std::string GetInputString(const std::string content) {
        std::cout << content << " :";
        std::string input;
        std::cin >> input;
        return input;
    }
    
    TreeNode::TreeNode() : _left(nullptr), _right(nullptr), _key(-1), _priority(-1) {
        
    }
    
    TreeNode::TreeNode(int value, int priority) {
        _key = value;
        _priority = priority;
        _left = nullptr;
        _right = nullptr;
    }
    
    TreeNode::~TreeNode() {
        
    }
    
    Tree::Tree() {
        _root = nullptr;
    }
    
    Tree::~Tree() {
        
    }
    
    /**
     *  三种情况：小于跟结点和大于跟结点以及跟结点为空
     *
     *  @param node <#node description#>
     *  @param root <#root description#>
     */
    void Tree::Insert(TreeNode* node, TreeNode* &root) {
        if (root == nullptr) {
            root = node;
            root->_left = nullptr;
            root->_right = nullptr;
        }
        else if (node->_key > root->_key) {
            // 往右边插入结点
            Insert(node, root->_right);
            // 向左旋转
            if (root->_right->_priority < root->_priority) {
                rotateLeft(root);
            }
        }
        else if (node->_key < root->_key) {
            // 往左边插入结点
            Insert(node, root->_left);
            // 向右旋转
            if (root->_left->_priority < root->_priority) {
                rotateRight(root);
            }
        }
    }
    
    /**
     *  重点在于其中决定删除那个结点，也就是翻转的情况
     *
     *  @param node <#node description#>
     *  @param root <#root description#>
     */
    void Tree::Delete(int key, TreeNode* &root) {
        if (root != nullptr) {
            if (key > root->_key) {
                Delete(key, root->_right);
            }
            else if (key < root->_key) {
                Delete(key, root->_left);
            }
            else {
                // 叶子结点
                if (root->_left == nullptr && root->_right == nullptr) {
                    delete root;
                    root = nullptr;
                }
                // 包含一个叶子结点的结点
                else if (root->_left == nullptr || root->_right == nullptr) {
                    if (root->_left) {
                        root = root->_left;
                        root->_left = nullptr;
                    }
                    else if (root->_right) {
                        root = root->_right;
                        root->_right = nullptr;
                    }
                }
                else {
                    // 向右翻转
                    if (root->_left->_priority < root->_right->_priority) {
                        rotateRight(root);
                        Delete(key, root->_right);
                    }
                    // 向左翻转
                    else {
                        rotateLeft(root);
                        Delete(key, root->_left);
                    }
                }
            }
        }
    }
    
    /**
     *  迭代查找
     *
     *  @param key  <#key description#>
     *  @param root <#root description#>
     *
     *  @return <#return value description#>
     */
    TreeNode* Tree::Search(int key, TreeNode* &root) {
        std::stack<TreeNode *> stack;
        stack.push(root);
        TreeNode * resultNode = nullptr;
        
        while (!stack.empty()) {
            TreeNode * node = stack.top();
            stack.pop();
            
            if (node->_key == key) {
                resultNode = node;
                break;
            }
            else if (node->_key > key) {
                if (node->_left) {
                    stack.push(node->_left);
                }
            }
            else {
                if (node->_right) {
                    stack.push(node->_right);
                }
            }
        }
        
        return resultNode;
    }
    
    /**
     *  中序遍历得到顺序值
     *
     *  @param root <#root description#>
     */
    void Tree::Traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        if (root->_left) Traverse(root->_left);
        LogNode(root);
        if (root->_right) Traverse(root->_right);
    }
    
    void Tree::insertNode(TreeNode* node) {
        assert(node == nullptr);
        Insert(node, _root);
    }
    
    void Tree::deleteNode(int key) {
        Delete(key, _root);
    }
    
    TreeNode* Tree::searchNode(int value) {
        return Search(value, _root);
    }
    
    void Tree::traverse() {
        Traverse(_root);
    }
    
    void Tree::rotateLeft(TreeNode* &node) {
        TreeNode* rNode = node->_right;
        node->_right = rNode->_left;
        rNode->_left = node;
        node = rNode;
    }
    
    void Tree::rotateRight(TreeNode* &node) {
        TreeNode* lNode = node->_left;
        node->_left = lNode->_right;
        lNode->_right = node;
        node = lNode;
    }

    double random(double start, double end)
    {
        return start+(end-start)*rand()/(RAND_MAX + 1.0);
    }
    
    static Tree * tree = new Tree();
    
    void insertNode() {
        srand(unsigned(time(0)));
        for (int i = 1; i <= 10; ++i) {
            int priority = int(random(1, 100));
            TreeNode * node = new TreeNode(i, priority);
            tree->Insert(node, tree->_root);
        }
    }
    
    void deleteNode() {
        std::string input = GetInputString("input the delete key");
        int key = atoi(input.c_str());
        tree->Delete(key, tree->_root);
    }
    
    void searchNode() {
        std::string input = GetInputString("input the search key");
        int key = atoi(input.c_str());
        TreeNode * node = tree->Search(key, tree->_root);
        LogNode(node);
    }
    
    void traverseNode() {
        tree->Traverse(tree->_root);
    }
    
}

main.cpp

//
//  main.cpp
//  Treap
//
//  Created by George on 16/10/5.
//  Copyright © 2016年 George. All rights reserved.
//

#include <iostream>
#include "Treap.hpp"

int main(int argc, const char * argv[]) {
    // insert code here...
    
    Treap::insertNode();
    
    Treap::traverseNode();
    
    Treap::deleteNode();
    
    Treap::traverseNode();
    
    Treap::searchNode();
    
    return 0;
}

运行结果：

应用

在别的地方看到的应用

[问题描述] 有一个游戏排名系统,通常要应付三种请求:上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时,他原有的得分记录会被删除。为了减轻服务器负担,在返回某个区段内的排名记录时,最多返回 10 条记录。[求]

更新玩家的得分记录
查询玩家排名（如果两个玩家的得分相同, 则先得到该得分的玩家排在前面。）
查询第 Index 名开始的最多 10 名玩家名字

[解]
因为作为字符串的姓名是不便于处理的,我们给每个玩家都制定一个ID,首先要建立一个由姓名到玩家ID的映射数据结构。为了查找快速,可以用Trie树。之后我们建立一个双关键字的Treap,关键字1为得分从小到大,关键字2为时间戳从大到小,这种排列方式的逆序,恰好是我们要的顺序(也可以直接就是逆序)。

对于问题（1），先查询玩家是否已经存在,如果已经存在,在Treap中更新对应已经存在的记录。
对于问题（2），就是基本的求排名操作。
对于问题（3），就是分别查找第(总记录数 + 1 – k)小的记录。