AVL树的实现

喜欢ヅ旅行 2022-08-04 14:49 118阅读 0赞

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

下面是我的实现，这个算法还是纠结了蛮久的

// AVL-Tree.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <crtdbg.h>
    #include<vector>
    
    #define MIN 1000000
    struct TreeNode{
    	int ele;
    	TreeNode*lnode, *rnode, *parent;
    };
    
    TreeNode*minmax = NULL;
    int minvalue = MIN;
    void find_postion(TreeNode*node, int value)
    {
    	if (node == NULL)
    		return;
    	if (node->ele - value > 0 && node->ele - value < minvalue)
    	{
    		minmax = node;
    		minvalue = node->ele - value;
    	}
    	find_postion(node->lnode, value);
    	find_postion(node->rnode, value);
    }
    int depth_between(TreeNode*floor, TreeNode*ceiling)
    {
    	_ASSERTE(floor != NULL);
    	int dep = 1;
    	while (ceiling != floor)
    	{
    		floor = floor->parent;
    		dep++;
    	}
    	return dep;
    }
    
    
    int maxdep = 0;
    int mindep = MIN;
    void depth(TreeNode*ceiling, TreeNode*node)
    {
    	if (node == NULL)
    		return;
    	int dep = depth_between(node, ceiling);
    	if (node->lnode == NULL&&node->rnode == NULL&&dep < mindep)
    	{
    		mindep = dep;
    	}
    	if (dep > maxdep)
    	{
    		maxdep = dep;
    	}
    	depth(ceiling, node->lnode);
    	depth(ceiling, node->rnode);
    }
    
    
    
    
    int tree_depth(TreeNode*node)
    {
    	maxdep = 0;
    	mindep = MIN;
    	depth(node, node);
    	return maxdep;
    }
    
    
    
    int is_balence(TreeNode*node)
    {
    	return tree_depth(node->lnode) - tree_depth(node->rnode);
    }
    
    std::vector<TreeNode*>vec;
    
    void inorder(TreeNode*node)
    {
    	if (node == NULL)
    		return;
    	inorder(node->lnode);
    	vec.push_back(node);
    	inorder(node->rnode);
    }
    
    
    
    void adjust(TreeNode*root, TreeNode*node)//插入删除后做调整
    {
    	while (node != NULL)
    	{
    		int aa = tree_depth(node->lnode);
    		int bb = tree_depth(node->rnode);
    		int tt = is_balence(node);
    		if (tt > 1)
    		{
    			if (node->rnode == NULL)
    			{
    				if (node->lnode->rnode != NULL)
    				{
    					int temp = node->ele;
    					node->ele = node->lnode->rnode->ele;
    					node->lnode->rnode->ele = temp;
    					node->rnode = node->lnode->rnode;
    					node->lnode->rnode = NULL;
    					node->rnode->parent = node;
    					node = node->parent;
    				}
    				else
    				{
    					int temp = node->ele;
    					node->ele = node->lnode->ele;
    					node->lnode->ele = node->lnode->lnode->ele;
    					node->rnode = node->lnode->lnode;
    					node->rnode->parent = node;
    					node->lnode->lnode = NULL;
    					node->rnode->ele = temp;
    					node = node->parent;
    				}
    			}
    			else
    			{
    				
    				TreeNode*t3 = node->lnode;
    				_ASSERTE(t3 != NULL);
    				
    				while (t3->rnode != NULL)
    				{
    					t3 = t3->rnode;
    				}
    			
    				TreeNode*t4;
    				t4 = node->rnode;
    				while (t4->rnode != NULL)
    				{
    					t4 = t4->rnode;
    				}
    
    				if (t4->parent->lnode == NULL)//旋转一次，便于后续插入
    				{
    					int temp = t4->parent->ele;
    					t4->parent->ele = t4->ele;
    					t4->ele = temp;
    					t4->parent->lnode = t4;
    					t4->parent->rnode = NULL;
    				}
    				TreeNode*t5 = t3->parent;
    				if (t3->lnode != NULL)
    				{
    					t3->lnode->parent = t3->parent;
    				}
    				t3->parent->rnode = t3->lnode;
    				t3->lnode = NULL;
    
    				vec.clear();
    				inorder(node->rnode);
    				int temp = node->ele;
    				node->ele = t3->ele;
    				int t = vec[0]->ele;
    				vec[0]->ele = temp;
    				temp = vec.back()->ele;
    				if (vec.size() == 1)
    					temp = t;
    				for (int i = 1; i < vec.size(); i++)
    				{
    					vec[i]->ele = vec[i - 1]->ele;
    				}
    				vec.back()->rnode = t3;
    				//t3->lnode = t3->rnode = NULL;
    				t3->ele = temp;
    				t3->parent = vec.back();
    
    				node = t5;
    			}
    		}//end of tt>1
    
    
    		else if (tt < -1)
    		{
    			if (node->lnode==NULL)
    			{
    				if (node->rnode->rnode != NULL)
    				{
    					int temp = node->ele;
    					node->ele = node->rnode->ele;
    					node->rnode->ele = node->rnode->rnode->ele;
    					node->lnode = node->rnode->rnode;
    					node->rnode->rnode = NULL;
    					node->lnode->ele = temp;
    					node->lnode->parent = node;
    					node = node->parent;
    				}
    				else
    				{
    					node->lnode = node->rnode->lnode;
    					node->lnode->parent = node;
    					node->rnode->lnode = NULL;
    					int temp=node->lnode->ele;
    					node->lnode->ele = node->ele;
    					node->ele = temp;
    					node = node->parent;
    				}
    			}
    			else//node->lnode !=NULL
    			{
    				TreeNode*t1 = node->lnode;
    				while (t1->rnode != NULL)
    				{
    					t1 = t1->rnode;
    				}
    				if (t1->parent->lnode == NULL)//旋转，便于后续插入
    				{
    					_ASSERTE(t1->lnode == NULL&&t1->rnode == NULL);
    					int temp = t1->ele;
    					t1->ele = t1->parent->ele;
    					t1->parent->ele = temp;
    					t1->parent->lnode = t1;
    					t1->parent->rnode = NULL;
    				}
    				TreeNode*t2 = node->rnode->lnode;
    				_ASSERTE(t2 != NULL);
    				while (t2->lnode != NULL)
    				{
    					t2 = t2->lnode;
    				}
    				TreeNode*t3 = t2->parent;
    				t2->parent->lnode = t2->rnode;
    				if (t2->rnode!=NULL)
    					t2->rnode->parent = t2->parent;
    				t1->rnode = t2;
    				t2->rnode = NULL;
    				t2->parent = t1;
    				int temp = node->ele;
    				node->ele = t2->ele;
    				t2->ele = temp;
    
    				node = t3;
    			}
    		}//end of tt<-1
    		
    		else //-2<tt<2,无需调整
    			node = node->parent;
    	}
    
    }
    
    
    
    TreeNode* insert(TreeNode*root, int value)//插入
    {
    	if (root == NULL)//当前树为空
    	{
    		root = new TreeNode;
    		root->ele = value;
    		root->lnode = root->rnode = root->parent = NULL;
    		return root;
    	}
    
    	minmax = NULL;
    	minvalue = MIN;
    	find_postion(root, value);
    	if (minmax == NULL)//要插入的值比树中所有节点的都大
    	{
    		if (root->rnode == NULL)
    		{
    			TreeNode*node = new TreeNode;
    			node->ele = value;
    			node->parent = root;
    			root->rnode = node;
    			node->lnode = node->rnode = NULL;
    			TreeNode*floor = NULL;
    			maxdep = -1;
    			depth(root, root);
    			_ASSERTE(maxdep == 2);
    			return root;
    		}
    
    		TreeNode*r_node = root;
    		while (r_node->rnode != NULL)
    		{
    			r_node = r_node->rnode;
    		}
    		TreeNode*node = new TreeNode;
    		node->ele = value;
    		node->parent = r_node;
    		r_node->rnode = node;
    		node->lnode = node->rnode = NULL;
    		adjust(root, r_node->parent);
    		return root;
    	}
    
    	TreeNode*nn = minmax->lnode;
    	if (nn == NULL)
    	{
    		TreeNode*node = new TreeNode;
    		node->ele = value;
    		node->lnode = node->rnode = NULL;
    		minmax->lnode = node;
    		node->parent = minmax;
    		adjust(root, minmax->parent);//对树做调整
    		return root;
    	}
    	while (nn->rnode != NULL)
    	{
    		nn = nn->rnode;
    	}
    	TreeNode*node = new TreeNode;
    	node->ele = value;
    	node->parent = nn;
    	nn->rnode = node;
    	node->lnode = node->rnode = NULL;
    	adjust(root,nn->parent);//对树做调整
    	return root;
    }
    TreeNode*bbb=NULL;
    void find(TreeNode*node,const int value)//查找
    {
    	if (node != NULL)
    	{
    		if (node->ele == value)
    			bbb=node;
    		if (node->ele > value)
    			find(node->lnode, value);
    		else
    			find(node->rnode, value);
    	}
    }
    
    
    TreeNode*erase(TreeNode*root,const int value)//删除
    {
    	bbb = NULL;
    	find(root, value);
    	TreeNode*tobedel = bbb;
    	if (tobedel != NULL)
    	{
    		if (tobedel == root)
    		{
    			if (root->lnode == NULL)
    			{
    				TreeNode*nn = root->rnode;
    				nn->parent = NULL;
    				delete root;
    				return nn;
    			}
    			TreeNode*t1 = root->lnode;
    			while (t1->rnode != NULL)
    			{
    				t1 = t1->rnode;
    			}
    			TreeNode*aa = t1->parent;
    			t1->parent->rnode = t1->lnode;
    			if (t1->lnode != NULL)
    				t1->lnode->parent = t1->parent;
    
    			t1->lnode = root->lnode;
    			root->lnode->parent = t1;
    			t1->parent = NULL;
    			t1->rnode = root->rnode;
    			if (root->rnode != NULL)
    				root->rnode->parent = t1;
    			if (aa == root)
    				aa=t1;
    			delete root;
    			adjust(t1, aa);
    			return t1;
    		}
    
    		if (tobedel->lnode == NULL)
    		{
    			tobedel->parent->lnode = tobedel->rnode;
    			if (tobedel->rnode != NULL)
    				tobedel->rnode->parent = tobedel->parent;
    			TreeNode*aa = tobedel->parent;
    			delete tobedel;
    			adjust(root, aa);
    			return root;
    		}
    		TreeNode*t1 = tobedel->lnode;
    		while (t1->rnode != NULL)
    		{
    			t1 = t1->rnode;
    		}
    		
    		t1->parent->rnode = t1->lnode;
    		if (t1->lnode != NULL)
    			t1->lnode->parent = t1->parent;
    		t1->lnode = NULL;
    		TreeNode*aa = t1->parent;
    		if (tobedel->parent->lnode == tobedel)
    		{
    			tobedel->parent->lnode = t1;
    			t1->parent = tobedel->parent;
    			tobedel->parent->rnode = tobedel->rnode;
    			if (tobedel->rnode != NULL)
    				tobedel->rnode->parent = tobedel->parent;
    			delete tobedel;
    			adjust(root, aa);
    			return root;
    		}
    		else
    		{
    			tobedel->parent->rnode = t1;
    			t1->parent = tobedel->parent;
    			tobedel->parent->rnode = tobedel->rnode;
    			if (tobedel->rnode != NULL)
    				tobedel->rnode->parent = tobedel->parent;
    			delete tobedel;
    			adjust(root, aa);
    			return root;
    		}
    	}
    
    	return root;
    }
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	TreeNode*root = NULL;
    	root=insert(root, 100);
    	root=insert(root, 200);
    	root=insert(root, 300);
    	root=insert(root, 50);
    	root = insert(root, 20);
    	root = insert(root, 500);
    	root = insert(root, 700);
    	root = insert(root, 1100);
    	root = insert(root, 1500);
    	root = insert(root, 900);
    	root = insert(root, 1000);
    	root = insert(root, 150);
    	root = insert(root, 350);
    	root = insert(root, 250);
    	root = insert(root, 15);
    	root = insert(root, 10);
    	root = insert(root, 8);
    	root = insert(root, 5);
    
    	bbb = NULL;
    	find(root, 150);
    	TreeNode*aa = bbb;
    
    	root = erase(root, 300);
    	root = erase(root, 150);
    	system("pause");
    	return 0;
    }