289-跳跃表SkipList

跳跃表性质：

1. 由很多层链表组成
2. 每一层都是一个有序的链表
3. 最底层（level 1）的链表包含所有元素
4. 如果一个元素出现在level i层的链表中，则它在level i之下的链表也都会出现
5. 每个节点都包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素

跳跃表的增加、删除、查询操作时间复杂度和红黑树一样，也是O(logn)。

相比于红黑树，它的优势是：

1. 实现起来更加简单
2. 跳跃表的增加、删除操作只会改动局部，不像红黑树的增加、删除操作，因为需要节点重新着色和旋
   转，可能整棵树都要进行调整，因此在并发环境下，跳跃表加锁的粒度会更小一些，并发能力更强
3. 因为跳跃表的每一层都是一个有序的链表，因此范围查找非常方便，优于红黑树的范围搜索的

跳跃表相比于红黑树，是用空间换时间（level 2层开始每一层都有会存储重复的数据），因此占用的内存空间比红黑树大。

应用：

• redis的底层的有序集合sorted sets也使用 SkipList！

面试聊跳跃表的3个切入点：

• 现在跳表的头指针Top指向的是最上面一层的链表的头节点（level3的-1）！
• 跳表的头节点为图中的h，每一层链表的头结点都是我们在代码中定义的是ListNode。
  所有的元素都是在最底下（第一层）出现的，然后往上走，会把第一层的某些元素在第二层存储一下，然后再往上走，会把第二层的某些元素在第三层存储一下，以此类推下去。
  每一层都是有序的链表，默认从小到大。

• K=1，然后进入while循环，随机数是0或者1，相当于是不断抛硬币的过程，符号我们正态分布的过程。

• 也就是说，抛一万次硬币，得到的结果近似一半正面朝上，一半的正面朝下，符合正态分布的结果。

• 我们根据抛硬币的方式决定下面这一层的某一个元素是否需要在上一层再存储一遍。

• 也就是说，从我们的正态分布的角度来看，最终我们可能会把趋于下面这一层的一半的元素提升到上面这一层来。

• 再往上一层走，就把下面的第二层的所有元素进行抛硬币，然后把近似一半的元素提到第三层再存储一遍。

这样，最终就和我们的二叉树一样了，最顶层可能就1个元素节点。
然后它的下面一层可能是2个，以此类推。
其实，这个过程，搭建起来跳表的过程，元素的组织方式和我们的二叉搜索树是非常相似的。

• 使用两个指针pre和cur进行操作，当cur找到当前节点的值 > 搜索的值后，cur前面的pre跳到下一层，然后cur指向pre的后面一个元素；
• pre前面的元素可以都不用找了！

搜索元素是从最上面的那层元素开始搜索的。

如果要插入元素：

• 如果我们要插入119这个数字，通过抛硬币，决定119要插几行；
• 跳表本身是3行，插2行是没有问题的；
• 在最后一行按序插入，因为要插2行，所以在第二行也插了一个119。

假如我们要插入119，但是抛硬币抛出了4层，但是跳表只有3层，但是最终我们也是要插4层的，也就是说，在最上层（第4层）就只有一个数字119。

但是如果说，这个跳表只有3层，在插入数字119的时候，抛硬币的结果是5层，在5层里面都要添加119这个数字，但是跳表只有3层，所以我们最终也是只插4层就可以了。

跳表的层数增长是一层一层增长的，不会一下子多个层，每个层放的数据一样。

K初始化=1，因为一定要在最底层添加元素。然后按照随机进行K++。

• 如果我们要删除元素37，首先得查找，我们是从最上层开始查找，我们在最上层（level3）一下子就找到37这个元素了，既然这个37在level3出现了，那么37肯定还出现在level2和level1中，如果我们在第三层，也就是最上层找到37了，然后往下，把这3个节点都删除了。也就是：在每一层中，把37的前面1个节点的地址域写成37后面的那个节点的地址。
• 如果我们要删除元素71，首先是查找，在最上层中遍历到37，比37大，再往找的话，已经是末尾节点1了，所以71在level3上不存在，所以从37直接往下走，走到level2层，然后往后走，找到了71，然后就不用往后找了，往下找！因为没有到最底层，所以下面都是71，从上到下，把这个垂直上的71全部删除掉，也就是每一层的71的前一个节点的地址域存储71后一个节点的地址。

#include 
using namespace std;

// 跳跃表SkipList
class SkipList
{
public:
	SkipList()
	{
		head_ = new HeadNode(1);
	}
	~SkipList()
	{
		int level = head_->level_;
		for (int i = 0; i < level; i++)
		{
			//先删每一层链表的头节点的后面节点，头结点就先不管
			Node* cur = head_->next_;
			while (cur != nullptr)
			{
				Node* tmp = cur->next_;
				delete cur;
				cur = tmp;
			}
			cur = head_;
			head_ = static_cast(head_->down_);
			delete cur;
		}
	}

public:
	// 搜索数据
	bool find(int data)
	{
		Node* pre = head_;
		Node* cur = pre->next_;

		for (;;)
		{
			if (cur != nullptr)
			{
				if (cur->data_ < data)
				{
					pre = cur;
					cur = cur->next_;
					continue;
				}
				else if (cur->data_ == data)
				{
					return true;
				}
			}

			// cur == nullptr了
			if (pre->down_ == nullptr)
			{
				// pre和cur已经遍历到第一层的末尾了
				break;
			}

			pre = pre->down_;
			cur = pre->next_;
		}
		return false;
	}

	// 添加数据
	void add(int data)
	{
		// 先查找数据是否存在
		if (find(data))
			return;

		// 抛硬币，data数据添加几层
		int level = getLevel();
		if (level > head_->level_)
		{
			// level过大时，SkipList只增长一层
			level = head_->level_ + 1;
			HeadNode* hnode = new HeadNode(level);
			hnode->down_ = head_;
			head_ = hnode;
		}

		// 先创建level层的data节点，修改down指针域
		Node** nodeList = new Node * [level];
		for (int i = level - 1; i >= 0; i--)//i = level - 1是最下面的节点
		{
			nodeList[i] = new Node(data);
			if (i < level - 1)
			{
				//上面节点的down指针域，存储下面节点的地址
				nodeList[i]->down_ = nodeList[i + 1];
			}
		}

		Node* head = head_;
		for (int i = head_->level_; i > level; i--)
		{
			head = head->down_;
		}

		//head就指向了要插入节点的那一层链表了
		Node* pre = head;
		Node* cur = pre->next_;

		for (int i = 0; i < level; i++)
		{
			while (cur != nullptr && cur->data_ < data)
			{
				pre = cur;
				cur = cur->next_;
			}

			// 新节点插入到pre和cur的中间
			nodeList[i]->next_ = cur;
			pre->next_ = nodeList[i];

			pre = pre->down_;
			if (pre != nullptr)
				cur = pre->next_;
		}

		delete[]nodeList;
		nodeList = nullptr;
	}

	// 删除数据
	void remove(int data)
	{
		Node* pre = head_;
		Node* cur = pre->next_;

		for (;;)
		{
			if (cur != nullptr)
			{
				if (cur->data_ < data)
				{
					pre = cur;
					cur = cur->next_;
					continue;
				}
				else if (cur->data_ == data)
				{
					// 删除cur指向的节点
					pre->next_ = cur->next_;
					delete cur;
				}
			}

			if (pre->down_ == nullptr)
			{
				break;
			}

			pre = pre->down_;
			// cur == nullptr 或 当前层没有data节点
			if (head_->next_ == nullptr)
			{
				delete head_;
				head_ = static_cast(pre);
			}
			cur = pre->next_;
		}
	}

	// 打印
	void show() const
	{
		Node* head = head_;
		while (head != nullptr)
		{
			Node* cur = head->next_;
			while (cur != nullptr)
			{
				cout << cur->data_ << " ";
				cur = cur->next_;
			}
			cout << endl;
			head = head->down_;
		}
		cout << endl;
	}

private:
	int getLevel() const
	{
		int level = 1;
		while (rand() % 2 == 1)
			level++;
		return level;
	}

private:
	// 普通节点类型
	struct Node
	{
		Node(int data = int())
			: data_(data)
			, next_(nullptr)
			, down_(nullptr)
		{}
		int data_;     // 数据域
		Node* next_;   // 指向同一层后一个节点的指针域
		Node* down_;   // 指向下一层相同节点的指针域
	};

	// 跳跃表的头节点类型
	struct HeadNode : public Node
	{
		HeadNode(int level)
			: level_(level)
		{}
		int level_; // 跳跃表的层数
	};

private:
	HeadNode* head_;   // 指向跳表最上面一层链表的头节点
};

int main()
{
	SkipList list;
	srand(time(nullptr));

	for (int i = 0; i < 20; i++)
	{
		list.add(rand() % 100);
	}

	list.add(50);
	list.show();

	list.remove(50);
	list.show();

	return 0;
}