数据结构（7）-- Splay tree(伸展树)

首先，对P做一次单旋
然后，对X做一次单旋

#include<iostream>

using namespace std;

class TreeNode {
public:
	//这几个数据放做公有的，方便操作
	int depth; //深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡
	TreeNode* parent; //该结点的父节点，方便操作
	int val;
	TreeNode* left;
	TreeNode* right;

	TreeNode(int x) : val(x), depth(0), left(NULL), right(NULL) {}
	TreeNode() : val(0), depth(0), left(NULL), right(NULL) {}
};



class splay_tree {
public:
	TreeNode* left_head;
	TreeNode* right_head;
	TreeNode* head;
	TreeNode* tail_right;
	TreeNode* tail_left;

public:
	splay_tree(TreeNode* head) :left_head(NULL), right_head(NULL), head(head) , tail_right(NULL), tail_left(NULL){}
	TreeNode* zig_left(TreeNode* node) {
		/*
			左单旋

			A					A
		  /	  \				   /
		A2	   B		->	  A2		B
			  /  \					   / \
			B2	  C					  B2  C
		*/

		TreeNode* res = node->right;

		node->right = NULL;

		//左子树还是空的
		if (NULL == tail_left) {
			left_head = node;
			tail_left = node;
		}
		//接在左子树的右侧
		else {
			tail_left->right = node;
		}

		//调整左子树的尾结点
		while (tail_left->right) {
			tail_left = tail_left->right;
		}

		return res;
	}

	TreeNode* zig_right(TreeNode* node) {
		/*
			右单旋

			A					      A
		  /	  \				           \
		B	   A2		->	    B	    A2
	   /  \					   / \ 
	 B2	   C				  B2  C
		*/

		TreeNode* res = node->left;

		node->left = NULL;

		if (NULL == tail_right) {
			right_head = node;
			tail_right = node;
		}
		else {
			tail_right->left = node;
		}

		while (tail_left->right) {
			tail_left = tail_left->right;
		}

		return res;
	}

	//一字向左
	TreeNode* zig_zig_left(TreeNode* node) {
		//先来一个普通右转，再来一个拆分右转
		
		TreeNode* temp = node->left;
		node->left = temp->right;
		temp->right = node;
		
		return zig_right(temp);
	}

	//一字向右
	TreeNode* zig_zig_right(TreeNode* node) {
		TreeNode* temp = node->right;
		node->right = temp->left;
		temp->left = node;
		
		return zig_left(temp);
	}

	//合并
	void combine_trees() {
		TreeNode* temp_left = head->left;
		TreeNode* temp_right = head->right;
		
		head->left = left_head;
		head->right = right_head;

		tail_left->right = temp_left;
		tail_right->left = temp_right;

		left_head = NULL;
		right_head = NULL;
		tail_right = NULL;
		tail_left = NULL;
	}

	//自顶向下，不用管这个头了，反正遍历的过程中会一路往上翻
	bool search_node(int val) {
		//一次看三个值
		while (1) {
			if (val == head->val) {
				return true;	//一遍过自然是最好的了
			}
			else if (val > head->val) {	//右
				if (head->right) {	//如果右边存在
					if (val == head->right->val) {	//如果是两遍过，那要简单的旋转一下了
						head = zig_left(head);
						combine_trees();	//我也觉得简单转一下就好了，但是，想了想还是按规矩来
						return true;
					}
					else if (val > head->right->val) {	//右右
						if (head->right->right) {	//不管它的值了，直接转
							head = zig_zig_right(head);
						}
						else{
							return false;
						}
					}
					else {	//右左
						//处理一个节点即可
						head = zig_left(head);
					}
				}
				else{
					return false;
				}
			}
			else {	//左
				if (head->left) {	//如果左边存在
					if (val == head->left->val) {	//如果是两遍过，那要简单的旋转一下了
						head = rotate_left(head);
						return true;
					}
					else if (val > head->left->val) {	//左左
						if (head->left->right) {	//不管它的值了，直接转
							head = zig_zig_left(head);
						}
						else{
							return false;
						}
					}
					else {	//左右
						//处理一个节点即可
						head = zig_right(head);
					}
				}
				else{
					return false;
				}
			}
		}
	}
};