Splay Tree的删除操作

Splay Tree的删除操作

Splay Tree的插入操作,搜索操作,和删除操作都实现了,那么就能够使用来解题了。

指针的删除操作的处理还是那么难的,非常多坎须要避开.

同一个坎还是坑了我好多次,就是指针传递的问题,什么时候须要改动指针本身的值,就必须返回指针或者传递指针的指针,或者传递指针的的实參。

这里的删除操作就是须要改变传递到函数的指针本身的,所以我这里使用了返回指针操作。

还有删除树的问题,之前的代码没做删除操作,所以没问题,如今须要逐个节点删除,所以要小心不能把整个树都删除了。

至此, splay 树的功能差点儿相同完好了。


代码中凝视标明了几个坑都被我碰到了。


#pragma once
#include <stdio.h>

class SplayTreeComplete
{
	struct Node
	{
		int key;
		Node *left, *right;
		explicit Node(int k):key(k),left(NULL),right(NULL){}
		/*~Node()
		{教训:这种话整颗树都删除了,不能这么删除,要逐个节点删除
			if (left) delete left, left = NULL;
			if (right) delete right, right = NULL;
		}*/
	};

	Node *leftRotate(Node *x)
	{
		Node *y = x->right;
		x->right = y->left;
		y->left = x;
		return y;
	}

	Node *rightRotate(Node *x)
	{
		Node *y = x->left;
		x->left = y->right;
		y->right = x;
		return y;
	}

	Node *splay(Node *root, const int key)
	{
		if (!root || key == root->key) return root;

		if (key < root->key)
		{
			if (!root->left) return root;

			if (key < root->left->key)
			{
				root->left->left = splay(root->left->left, key);
				root = rightRotate(root);
			}
			else if (root->left->key < key)
			{
				root->left->right = splay(root->left->right, key);
				if (root->left->right) root->left = leftRotate(root->left);
			}
			return root->left? rightRotate(root) : root;
		}

		if (!root->right) return root;
		if (root->right->key < key)
		{
			root->right->right = splay(root->right->right, key);
			root = leftRotate(root);
		}
		else if (key < root->right->key)
		{
			root->right->left = splay(root->right->left, key);
			if (root->right->left) root->right = rightRotate(root->right);
		}
		return root->right? leftRotate(root) : root;
	}

	Node *insert(Node *root, const int key)
	{
		if (!root) return new Node((int)key);//别忘了创建新的节点

		root = splay(root, key);//别忘了 root = 
		
		if (key == root->key) return root;

		Node *newNode = new Node((int)key);
		if (key < root->key)
		{
			newNode->right = root;
			newNode->left = root->left;
			root->left = NULL;//别漏了这句,否则破坏了树结构
		}
		else
		{
			newNode->left = root;
			newNode->right = root->right;
			root->right = NULL;
		}
		return newNode;
	}

	Node *deleteNode(Node *root, const int key)
	{
		if (!root) return root;

		root = splay(root, key);

		if (key == root->key)
		{
			if (!root->left)
			{
				Node *x = root;
				root = root->right;
				delete x, x = NULL;
			}
			else
			{
				Node *x = root->right;
				Node *y = root->left;
				delete root;
				root = splay(y, key);
				root->right = x;
			}
		}
		return root;
	}

	void preOrder(Node *root)
	{
		if (root != NULL)
		{
			printf("%d ", root->key);
			preOrder(root->left);
			preOrder(root->right);
		}
	}
public:
	SplayTreeComplete()
	{
		Node *root = NULL;
		int keys[] = {100, 50, 200, 40, 30, 20, 25};
		int n = sizeof(keys) / sizeof(keys[0]);
		for (int i = 0; i < n; i++)
		{
			root = insert(root, keys[i]);
		}

		printf("\nInser create Preorder traversal Splay tree is \n");
		preOrder(root);
		putchar('\n');

		root = splay(root, 50);
		bool found = root->key == 50;

		printf("\n50 is %s the tree\n", found? "in" : "not in");

		root = deleteNode(root, 50);//root 发生改变了,所以必须返回新的指针值

		root = splay(root, 50);
		found = root->key == 50;

		printf("\n50 is %s the tree\n", found? "in" : "not in");

		printf("\nInser create Preorder traversal Splay tree is \n");
		preOrder(root);
		putchar('\n');

		deleteTree(root);
	}

	void deleteTree(Node *root)
	{
		if (root)
		{
			deleteTree(root->left);
			deleteTree(root->right);
			delete root, root = NULL;
		}
	}
};


<span>Splay Tree的删除操作</span>

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119014.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号