AVL树

男娘i 2023-05-21 08:58 25阅读 0赞

本节内容介绍AVL树，具体看下面：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 7][]

具体看如下代码：

AVLTree.h

#pragma once
    
    struct AVLNode;
    typedef struct AVLNode* Position;
    typedef struct AVLNode* AVLTree;
    
    
    typedef int ElementType;
    
    AVLTree MakeEmpty(AVLTree T);
    Position Find(ElementType X,AVLTree T);
    Position FindMin(AVLTree T);
    Position FindMax(AVLTree T);
    AVLTree Insert(ElementType X,AVLTree T);
    AVLTree Delete(ElementType X,AVLTree T);
    ElementType Retrieve(Position P);
    
    AVLTree SingleRotateLeft(AVLTree T);
    AVLTree SingleRotateRight(AVLTree T);
    AVLTree DoubleRotateLeft(AVLTree T);
    AVLTree DoubleRotateRight(AVLTree T);
    
    void PrintTree(AVLTree T,int depth);
    void PrintTree(AVLTree T);
    void PrintDepth(ElementType A,int dpth);
    
    
    struct  AVLNode
    {
    	ElementType Element;
    	AVLTree Lchild;
    	AVLTree Rchild;
    	int Hight;
    };

AVLTree.cpp

#include<iostream>
    #include <stdlib.h>
    #include "AVLTree.h"
    
    using namespace std;
    
    #define Max(a,b)  ((a)>(b)?(a):(b))
    
    
    //返回树节点的高度，如果为NULL返回-1
    int Height(AVLTree T)
    {
    	if (T == NULL)
    	{
    		return -1;
    	}
    	return T->Hight;
    }
    
    
    AVLTree MakeEmpty(AVLTree T)
    {
    	if (T != NULL)
    	{
    		MakeEmpty(T->Lchild);
    		MakeEmpty(T->Rchild);
    		free(T);
    	}
    	return NULL;
    }
    
    
    //递归查找
    Position Find(ElementType X, AVLTree T)
    {
    	if (T == NULL)
    	{
    		return NULL;
    	}
    
    	if (X < T->Element)
    	{
    		return Find(X,T->Lchild);
    	}
    	else if (X > T->Element)
    	{
    		return Find(X,T->Rchild);
    	}
    	else
    	{
    		return T;
    	}
    }
    
    
    //非递归查找
    Position FindMin(AVLTree T)
    {
    	if (T != NULL)
    	{
    		while (T->Lchild!=NULL)
    		{
    			T = T->Lchild;
    		}
    		return T;
    	}
    	return NULL;
    }
    
    
    //非递归查找
    Position FindMax(AVLTree T)
    {
    	if (T != NULL)
    	{
    		while (T->Rchild != NULL)
    		{
    			T = T->Rchild;
    		}
    		return T;
    	}
    	return NULL;
    }
    
    
    
    //递归插入
    AVLTree Insert(ElementType X, AVLTree T)
    {
    	if (T == NULL)
    	{
    		T = (AVLTree)malloc(sizeof(AVLNode));
    		if (T == NULL)
    		{
    			exit(1);
    		}
    		T->Element = X;
    		T->Lchild = T->Rchild = NULL;
    		T->Hight = 0;
    	}
    
    	if (X < T->Element)
    	{
    		T->Lchild = Insert(X,T->Lchild);
    		//左边插入之后检查是否满足平衡条件，如果不平衡需要进行旋转
    		if ((Height(T->Lchild)) - (Hight(T->Rchild)) == 2)
    		{
    			if (X < T->Lchild->Element)
    			{
    				T = SingleRotateLeft(T);
    			}
    			else
    			{
    				T = DoubleRotateLeft(T);
    			}
    		}
    	}
    	if (X > T->Element)
    	{
    		T->Rchild = Insert(X,T->Rchild);
    		//右边插入之后检查是否满足平衡条件，如果不平衡需要进行旋转
    		if (((Height(T->Rchild)) - Height(T->Lchild)) == 2)
    		{
    			if (X > T->Rchild->Element)
    			{
    				T = SingleRotateRight(T);
    			}
    			else
    			{
    				T = DoubleRotateRight(T);
    			}
    		}
    	}
    
    	//插入完成更新该节点高度
    	T->Hight = Max(Height(T->Lchild), Height(T->Rchild)) + 1;
    	return T;
    }
    
    
    //左边树枝旋转
    AVLTree SingleRotateLeft(AVLTree T)
    {
    	AVLTree k1;
    
    	k1 = T->Lchild;
    	T->Lchild = k1->Rchild;
    	k1->Rchild = T;
    
    	T->Hight = Max(Height(T->Lchild),Height(T->Rchild))+1;
    	k1->Hight = Max(Height(k1->Lchild),Height(k1->Rchild))+1;
    
    	return k1;
    }
    
    //右边树旋转
    AVLTree SingleRotateRight(AVLTree T)
    {
    	AVLTree k1;
    
    	k1 = T->Rchild;
    	T->Rchild = k1->Lchild;
    	k1->Lchild = T;
    
    	T->Hight = Max(Height(T->Lchild),Height(T->Rchild))+1;
    	k1->Hight = Max(Height(k1->Lchild),Height(k1->Rchild))+1;
    
    	return k1;
    }
    
    //左边树枝双旋转
    AVLTree DoubleRotateLeft(AVLTree k3)
    {
    	k3->Lchild = SingleRotateRight(k3->Lchild);
    	return SingleRotateLeft(k3);
    }
    
    //右边树枝双旋转
    AVLTree DoubleRotateRight(AVLTree k4)
    {
    	k4->Rchild = SingleRotateLeft(k4->Rchild);
    	return SingleRotateRight(k4);
    }
    
    
    //递归删除
    AVLTree Delete(ElementType X, AVLTree T)
    {
    	if (T == NULL)
    	{
    		fprintf(stderr,"%d not exists\n",X);
    	}
    	else
    	{
    		if (X<T->Element)
    		{
    			T->Lchild = Delete(X,T->Lchild);
    			//删除之后需要更新该节点高度
    			T->Hight = Max(Height(T->Lchild),Height(T->Rchild))+1;
    			//删除之后检查是否满足平衡条件，不满足需要旋转
    			if ((Height(T->Rchild) - Height(T->Lchild)) == 2)
    			{
    				if (Height(T->Rchild->Rchild) >= Height(T->Rchild->Lchild))
    				{
    					T = SingleRotateRight(T);
    				}
    				else
    				{
    					T = DoubleRotateRight(T);
    				}
    			}
    		}
    		else if (X > T->Element)
    		{
    			T->Rchild = Delete(X,T->Rchild);
    			//删除之后需要更新节点T的高度
    			T->Hight = Max(Height(T->Lchild),Height(T->Rchild))+1;
    			//如果不是平衡二叉树，那么就需要通过旋转来进行调整
    			if (Height(T->Lchild)-Height(T->Rchild)==2)
    			{
    				if (Height(T->Lchild->Lchild) >= Height(T->Lchild->Rchild))
    				{
    					T = SingleRotateLeft(T);
    				}
    				else
    				{
    					T = DoubleRotateLeft(T);
    				}
    			}
    		}
    		else
    		{
    			//找到的树节点如果有两个孩子的话就用它右子树的最小值代替该点，再删除右子树上的最大值
    			if (T->Lchild && T->Rchild)
    			{
    				T->Element = FindMin(T->Rchild)->Element;
    				T->Rchild = Delete(T->Element,T->Rchild);
    
    				T->Hight = Max(Height(T->Lchild),Height(T->Rchild))+1;
    
    				if (Height(T->Lchild) - Height(T->Rchild) == 2)
    				{
    					if (Height(T->Lchild->Lchild) >= Height(T->Lchild->Rchild))
    					{
    						T = SingleRotateLeft(T);
    					}
    					else
    					{
    						T = DoubleRotateLeft(T);
    					}
    				}
    
    			}
    			else
    			{
    				AVLTree temp = T;
    				if (T->Lchild == NULL)
    				{
    					T = T->Rchild;
    				}
    				else
    				{
    					T = T->Lchild;
    				}
    				free(temp);
    			}
    		}
    	}
    
    	return T;
    }
    
    
    
    void PrintDepth(ElementType A,int depth)
    {
    	while (depth!=0)
    	{
    		printf(" ");
    		depth--;
    	}
    	printf("%d\n",A);
    }
    
    
    //中序遍历
    void PrintTree(AVLTree T, int depth)
    {
    	if (T == NULL)
    	{
    		perror("wrong tree");
    		exit(1);
    	}
    
    	if (T->Lchild != NULL)
    	{
    		PrintTree(T->Lchild,depth+1);
    	}
    	PrintDepth(T->Element,depth);
    	if (T->Rchild != NULL)
    	{
    		PrintTree(T->Rchild,depth+1);
    	}
    }
    
    
    
    void PrintTree(AVLTree T)
    {
    	if (T == NULL)
    	{
    		perror("wrong tree");
    		exit(1);
    	}
    	if (T->Lchild != NULL)
    		PrintTree(T->Lchild);
    
    	printf("%d\n", T->Element);
    	if (T->Rchild != NULL)
    		PrintTree(T->Rchild);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70]: /images/20230521/8d799e16da8a47c69cbdf3ab81aaf501.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 1]: /images/20230521/b3886f6537d84876ba083f78c3717697.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 2]: /images/20230521/3a45d03d1f2b4b1f9da04d5da564de3d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 3]: /images/20230521/7f11a1f2984a41b191384700538cca4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 4]: /images/20230521/123cc392aeef4108a810a337506bb794.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 5]: /images/20230521/4d9daf38322b490c8c5e38f2d03af1ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 6]: /images/20230521/2ed243d69d50491785822f32e3000dd0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW5ndWl5dXl1_size_16_color_FFFFFF_t_70 7]: /images/20230521/e3d4c918f91042e9aa7d213e6eb5a6f8.png