title: Treap树理解

comments: true

date: 2016-10-06 07:57:37

categories: 算法

tags:

  • Treap树

Treap树理解

简介

随机平衡二叉查找树

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

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

性质

先看二叉树

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

再看堆(以最小堆为例)

  • 任何一个结点的优先级的值都要小于其跟结点的优先级的值(其优先值随机生成);

操作

查找

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

插入

(重点!!!)

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

Treap树理解-LMLPHP

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

  1. 按照BST的性质插入结点到叶子上;
  2. 按照堆的性质维护(左或者右旋转)树;

删除

删除的结点的情况有几种,需要掌握;

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

实现

代码用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;
}

运行结果:

Treap树理解-LMLPHP

应用

在别的地方看到的应用

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

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

[解]

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

对于问题(1),先查询玩家是否已经存在,如果已经存在,在Treap中更新对应已经存在的记录。

对于问题(2),就是基本的求排名操作。

对于问题(3),就是分别查找第(总记录数 + 1 – k)小的记录。

05-08 15:27