splay树的实现

「爱情、让人受尽委屈。」 2022-08-04 15:50 114阅读 0赞

伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造，后者对其进行了改进。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。

伸展树并没有AVL的平衡要求，任意节点的左右子树可以相差任意深度。

基本伸展树操作：  
1、插入：  
    当一个节点插入时，先插入，然后调整树（伸展操作），使得新插入的节点在根上。  
2、查找：  
    如果查找成功（找到），然后调整树（伸展操作），使得被查找的节点成为树的新根。  
如果查找失败（没有），那么在查找遇到NULL之前的那个节点成为新的根。也就是，如果查找的节点在树中，那么，此时根上的节点就是距离这个节点最近的节点。  
3、查找最大(find\_max)最小(find\_min)：  
      查找之后执行伸展。  
4、删除最大最小：  
a)删除最小：  
    首先执行查找最小的操作。  
这时，要删除的节点就在根上。根据二叉查找树的特点，根没有左子节点。  
使用根的右子结点作为新的根，删除旧的包含最小值的根。  
b)删除最大：  
首先执行查找最大的操作。  
删除根，并把被删除的根的左子结点作为新的根。  
5、删除：  
        首先执行查找操作，查找完后要删除的节点成为树根，然后删除根，剩下两个子树L（左子树）和R（右子树）。使用find\_max查找L的最大节点，此时，L的根没有右子树。使R成为L的根的右子树。

可以看到算法的核心就是伸展操作，也就是调整树使得目标节点成为树根。

下面是我的实现，其实比AVL树还是简单不少，因为限制条件少了

// splay-tree.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<vector>
    
    #define KeyType int
    #define MAX -1000000
    #define MIN 1000000
    
    class SplayTree
    {
    public:
    	static struct TreeNode
    	{
    		KeyType ele;
    		TreeNode*lnode, *rnode, *parent;
    	};
    private:
    	TreeNode*root;
    	void splay(TreeNode*node);
    	TreeNode*find_minmax(const KeyType val);
    
    public:
    	SplayTree()
    	{
    		root = NULL;
    	}
    	bool insert(const KeyType val);
    	bool erase(const KeyType val);
    	TreeNode*find(const KeyType val);
    	TreeNode*find_max();
    	TreeNode*get_root()
    	{
    		return root;
    	}
    };
    SplayTree::TreeNode*SplayTree::find_minmax(const KeyType val)
    {
    	std::vector<TreeNode*>aa;
    	aa.push_back(root);
    	TreeNode*minmax = NULL;
    	int near = MIN;
    	while (!aa.empty())//非递归先根遍历
    	{
    		TreeNode*node = aa.back();
    		aa.pop_back();
    		if (node->ele - val > 0 && node->ele - val < near)
    		{
    			minmax = node;
    			near = node->ele - val;
    
    		}
    		if (node->rnode != NULL)
    			aa.push_back(node->rnode);
    		if (node->lnode != NULL)
    			aa.push_back(node->lnode);
    	}
    	return minmax;
    
    }
    bool SplayTree::insert(const KeyType val)
    {
    	if (root == NULL)
    	{
    		root = new TreeNode;
    		root->ele = val;
    		root->lnode = root->rnode = root->parent = NULL;
    		return true;
    	}
    	TreeNode*pos = find_minmax(val);
    	if (pos == NULL)
    	{
    		TreeNode*nn = root;
    		while (nn->rnode != NULL)
    		{
    			nn = nn->rnode;
    		}
    		TreeNode*node = new TreeNode;
    		node->ele = val;
    		node->lnode = node->rnode = NULL;
    		nn->rnode = node;
    		node->parent = nn;
    		splay(node);
    		return true;
    	}
    	if (pos->lnode == NULL)
    	{
    		TreeNode*node = new TreeNode;
    		node->ele = val;
    		node->lnode = node->rnode = NULL;
    		pos->lnode = node;
    		node->parent = pos;
    		splay(node);
    		return true;
    	}
    	TreeNode*nn = pos->lnode;
    	while (nn->rnode != NULL)
    	{
    		nn = nn->rnode;
    	}
    	TreeNode*node = new TreeNode;
    	node->ele = val;
    	node->lnode = node->rnode = NULL;
    	nn->rnode = node;
    	node->parent = nn;
    	splay(node);
    	return true;
    }
    
    bool SplayTree::erase(const KeyType val)
    {
    	if (root == NULL)
    		return false;
    	TreeNode*todel = find(val);
    	if (todel->ele != val)
    		return false;
    	TreeNode*r_node = root->rnode;
    	TreeNode*l_node = root->lnode;
    	delete root;
    	if (l_node == NULL)
    	{
    		root = r_node;
    		if (r_node != NULL)
    			root->parent = NULL;
    		return true;
    	}
    	root = l_node;
    	root->parent = NULL;
    	find_max();
    	root->rnode = r_node;
    	if (r_node != NULL)
    		r_node->parent = root;
    	return true;
    }
    SplayTree::TreeNode* SplayTree::find_max()
    {
    	if (root == NULL)
    		return false;
    	TreeNode*node = root;
    	while (node->rnode != NULL)
    	{
    		node = node->rnode;
    	}
    	splay(node);
    	return root;
    }
    
    SplayTree::TreeNode* SplayTree::find(const KeyType val)
    {
    	if (root == NULL)
    		return NULL;
    	TreeNode*node = root;
    	TreeNode*nn = NULL;
    	while (node != NULL)
    	{
    		if (node->ele == val)
    		{
    			splay(node);
    			return root;
    		}
    		if (node->ele > val)
    		{
    			nn = node;
    			node = node->lnode;
    		}
    		else
    		{
    			nn = node;
    			node = node->rnode;
    		}
    	}
    	_ASSERTE(nn != NULL);
    	splay(nn);
    	return root;
    }
    void SplayTree::splay(SplayTree::TreeNode*node)
    {
    	while (node->parent != NULL)
    	{
    		if (node->parent == root)
    		{
    			if (root->lnode == node)
    			{
    				TreeNode*nn = node;
    				while (nn->rnode != NULL)
    				{
    					nn = nn->rnode;
    				}
    				root->lnode = NULL;
    				nn->rnode = root;
    				root->parent = nn;
    				node->parent = NULL;
    				root = node;
    				return;
    			}
    			if (root->rnode == node)
    			{
    				TreeNode*nn = node;
    				while (nn->lnode != NULL)
    				{
    					nn = nn->lnode;
    				}
    				root->rnode = NULL;
    				nn->lnode = root;
    				root->parent = nn;
    				node->parent = NULL;
    				root = node;
    				return;
    			}
    		}
    		TreeNode*parent = node->parent;
    		TreeNode*grandpa = node->parent->parent;
    		if (parent->rnode == node&&grandpa->lnode == parent)
    		{
    
    			TreeNode*node_lnode = node->lnode;
    			TreeNode*node_rnode = node->rnode;
    			TreeNode*gg = grandpa->parent;
    			bool isleft = true;
    			if (gg != NULL&&gg->rnode == grandpa)
    				isleft = false;
    			node->lnode = parent;
    			node->rnode = grandpa;
    			parent->parent = node;
    			grandpa->parent = node;
    			parent->rnode = node_lnode;
    			if (node_lnode != NULL)
    				node_lnode->parent = parent;
    			grandpa->lnode = node_rnode;
    			if (node_rnode != NULL)
    				node_rnode->parent = grandpa;
    			if (gg == NULL)
    			{
    				node->parent = NULL;
    				root = node;
    				return;
    			}
    			node->parent = gg;
    
    			if (isleft)
    				gg->lnode = node;
    			else
    				gg->rnode = node;
    
    		}
    		else if (parent->lnode == node&&grandpa->rnode == parent)
    		{
    			TreeNode*node_lnode = node->lnode;
    			TreeNode*node_rnode = node->rnode;
    			TreeNode*gg = grandpa->parent;
    			bool isleft = true;
    			if (gg != NULL&&gg->rnode == grandpa)
    				isleft = false;
    			node->rnode = parent;
    			node->lnode = grandpa;
    			parent->parent = node;
    			grandpa->parent = node;
    			parent->lnode = node_rnode;
    			if (node_rnode != NULL)
    				node_rnode->parent = parent;
    			grandpa->rnode = node_lnode;
    			if (node_lnode != NULL)
    				node_lnode->parent = grandpa;
    			if (gg == NULL)
    			{
    				node->parent = NULL;
    				root = node;
    				return;
    			}
    			node->parent = gg;
    
    			if (isleft)
    				gg->lnode = node;
    			else
    				gg->rnode = node;
    		}
    		else if (parent->rnode == node&&grandpa->rnode == parent)
    		{
    			TreeNode*node_lnode = node->lnode;
    			TreeNode*parent_lnode = parent->lnode;
    			TreeNode*gg = grandpa->parent;
    			bool isleft = true;
    			if (gg != NULL&&gg->rnode == grandpa)
    				isleft = false;
    			node->lnode = parent;
    			parent->lnode = grandpa;
    			parent->parent = node;
    			grandpa->parent = parent;
    			parent->rnode = node_lnode;
    			if (node_lnode != NULL)
    				node_lnode->parent = parent;
    			grandpa->rnode = parent_lnode;
    			if (parent_lnode != NULL)
    				parent_lnode->parent = grandpa;
    			if (gg == NULL)
    			{
    				node->parent = NULL;
    				root = node;
    				return;
    			}
    			node->parent = gg;
    			if (isleft)
    				gg->lnode = node;
    			else
    				gg->rnode = node;
    		}
    		else if (parent->lnode == node&&grandpa->lnode == parent)
    		{
    			TreeNode*node_rnode = node->rnode;
    			TreeNode*parent_rnode = parent->rnode;
    			TreeNode*gg = grandpa->parent;
    			bool isleft = true;
    			if (gg != NULL&&gg->rnode == grandpa)
    				isleft = false;
    			node->rnode = parent;
    			parent->rnode = grandpa;
    			parent->parent = node;
    			grandpa->parent = parent;
    			parent->lnode = node_rnode;
    			if (node_rnode != NULL)
    				node_rnode->parent = parent;
    			grandpa->lnode = parent_rnode;
    			if (parent_rnode != NULL)
    				parent_rnode->parent = grandpa;
    			if (gg == NULL)
    			{
    				node->parent = NULL;
    				root = node;
    				return;
    			}
    			node->parent = gg;
    			if (isleft)
    				gg->lnode = node;
    			else
    				gg->rnode = node;
    		}
    		else
    			_ASSERTE(1 < 0);
    	}
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	SplayTree st;
    	st.insert(100);
    	SplayTree::TreeNode*root = st.get_root();
    	st.insert(500);
    	root = st.get_root();
    	st.insert(600);
    	root = st.get_root();
    	st.insert(800);
    	root = st.get_root();
    	st.insert(1000);
    	root = st.get_root();
    	st.insert(1500);
    	root = st.get_root();
    	st.insert(900);
    	root = st.get_root();
    	st.insert(300);
    	root = st.get_root();
    	st.insert(200);
    	root = st.get_root();
    	st.insert(700);
    	root = st.get_root();
    	st.insert(550);
    	root = st.get_root();
    	st.insert(350);
    	root = st.get_root();
    	st.insert(650);
    	root = st.get_root();
    	st.insert(750);
    	root = st.get_root();
    	st.insert(950);
    	root = st.get_root();
    	st.insert(400);
    	root = st.get_root();
    	st.insert(450);
    	root = st.get_root();
    	st.insert(250);
    	root = st.get_root();
    	st.insert(580);
    	root = st.get_root();
    	st.insert(380);
    	root = st.get_root();
    	st.insert(660);
    	root = st.get_root();
    	st.insert(780);
    	root = st.get_root();
    	st.find(750);
    	root = st.get_root();
    	st.erase(780);
    	root = st.get_root();
    	return 0;
    }