跳表

class Skiplist {
private:
	struct node {//定义链表节点
		int val;
		struct node* down, * right;//下指针和右指针
		node() {//默认构造函数
			val = -2e9;down = right = nullptr;
		}
		node(int val1) {//带参构造函数
			val = val1;down = right = nullptr;
		}
	};
	typedef node* Node;
	static const int max_level = 20;//最大层数
	Node head[max_level];//每一层的头结点
 
public:
	Skiplist() {
		srand(time(nullptr));//初始化随机数种子
		//初始化头结点head数组
		for (int i = 0;i < max_level;i++)head[i] = new node;
		for (int i = max_level - 1;i >= 1;i--)head[i]->down = head[i - 1];
	}
 
	void add(int num) {//增
		int level = get_level();
		Node now = head[max_level - 1];
		int now_level = max_level - 1;//现在到达的层数
		Node ahead = nullptr;//上一个(记录ahead为了给上一个down指针赋值)
		while (now) {
			while (now->right && now->right->val < num) {
				now = now->right;
			}
			if (now_level <= level) {//小于分配的层数就执行插入操作
				Node new_node = new node(num);
				new_node->right = now->right;
				now->right = new_node;
				if (ahead)ahead->down = new_node;
				ahead = new_node;
			}
			now = now->down;
			now_level--;
		}
	}
        
	bool erase(int num) {//删
		Node now = head[max_level - 1];
		int flag = 0;
		while (now) {
			while (now->right && now->right->val < num) {
				now = now->right;
			}
			if (now->right && now->right->val == num) {
				now->right = now->right->right;//删除now->right节点
				flag = 1;
			}
			now = now->down;
		}
		return flag;//返回是否删除成功
	}
 
	bool search(int target) {//查
		Node now = head[max_level - 1];//从最高层头指针开始找
		while (now != nullptr) {
			while (now->right && now->right->val < target) {
				now = now->right;
			}
			if (now->right && now->right->val == target) {
				return true;
			}
			now = now->down;
		}
		return false;
	}
        
	int get_level() {//随机分配层数
		int cnt = 0;
		while (cnt < max_level - 1) {
			if (rand() % 2)cnt++;
			else break;
		}
		return cnt;
	}
};