手写AVL 树

ShenduCC

发布于 2019-04-01 06:59:53

50100

代码可运行

文章被收录于专栏：算法修养算法修养

运行总次数：0

代码可运行

平衡二叉树

左旋，右旋，左右旋，右左旋

具体原理就不说了，网上教程很多。这里只实现了建树的过程，没有实现删除节点的操作。

下一篇会实现删除节点的操作。

//
//  main.cpp
//  AVL
//
//  Created by 小康 on 2019/3/30.
//  Copyright © 2019 小康. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

using namespace std;

struct Tree
{
    Tree* leftChild;
    Tree* rightChild;
    int key;
    int value;
    int leftHeight;
    int rightHeight;
};

int num;
void LeftSpin(Tree*& root)
{
    Tree* temp = root;
    Tree* temp2 = root->rightChild->leftChild;
    root = temp->rightChild;
    root->leftChild = temp;
    temp->rightChild = temp2;
    
    root->leftChild->rightHeight = root->leftChild->rightChild==NULL?0:max(root->leftChild->rightChild->leftHeight,root->leftChild->rightChild->rightHeight)+1;
    
    root->leftHeight = max(root->leftChild->leftHeight,root->leftChild->rightHeight)+1;
}

void RightSpin(Tree*& root)
{
    Tree* temp = root;
    Tree* temp2 = root->leftChild->rightChild;
    
    root = temp->leftChild;
    root->rightChild = temp;
    temp->leftChild = temp2;
    
    root->rightChild->leftHeight =root->rightChild->leftChild==NULL?0:max(root->rightChild->leftChild->leftHeight,root->rightChild->leftChild->rightHeight)+1;
    root->rightHeight = max(root->rightChild->leftHeight,root->rightChild->rightHeight)+1;
}

void LeftRightSpin(Tree*& root)
{
    LeftSpin(root->leftChild);
    RightSpin(root);
}

void RightLeftSpin(Tree*& root)
{
    RightSpin(root->rightChild);
    LeftSpin(root);
}

void Insert(Tree*& root,int key,int value)
{
    if(root==NULL)
    {
        root = new Tree;
        root->leftChild=NULL;
        root->rightChild=NULL;
        root->key = key;
        root->value = value;
        root->leftHeight = 0;
        root->rightHeight = 0;
        return;
    }
   
    if(key < root->key)
    {
        Insert(root->leftChild,key,value);
        root->leftHeight = max(root->leftChild->leftHeight,root->leftChild->rightHeight)+1;
        if(root->leftHeight > root->rightHeight+1)
        {
            if(root->leftChild ->leftHeight > root->leftChild->rightHeight)
            {
                RightSpin(root);
            }
            else if(root->leftChild->leftHeight < root->leftChild->rightHeight)
            {
                LeftRightSpin(root);
            }
        }
    }
    else{
        Insert(root->rightChild, key,value);
        root->rightHeight = max(root->rightChild->leftHeight,root->rightChild->rightHeight)+1;
        
        if(root->leftHeight<root->rightHeight-1)
        {
            if(root->rightChild->rightHeight > root->rightChild->leftHeight)
            {
                LeftSpin(root);
            }
            else if(root->rightChild->rightHeight<root->rightChild->leftHeight)
            {
                RightLeftSpin(root);
            }
        }
    }
}

int Get(Tree* root,int key)
{
    if(key<root->key)
    {
       return Get(root->leftChild,key);
    }
    if(key>root->key)
    {
       return Get(root->rightChild,key);
    }
   
    return root->value;
    
}

int main()
{
    
    Tree* root = NULL ;
    
    Insert(root, 1, 1);
    Insert(root, 2, 2);
    Insert(root, 3, 3);
    Insert(root, 4, 4);
    printf("%d",Get(root,1));
    printf("%d",Get(root,2));
    printf("%d",Get(root,3));
    //Insert(root, 4, 5);
    
    
    
    return 0;
}