手写AVL 树

平衡二叉树

左旋,右旋,左右旋,右左旋

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

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

//
//  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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 104. Maximum Depth of Binary Tree

    Given a binary tree, find its maximum depth.

    ShenduCC
  • LeetCode 98. Validate Binary Search Tree( 递归,BST )

    题解:所有思路都是去找二叉树中不满足BST性质的节点,找到了,就不符合,找不到就符合。那么怎么去找呢?我提供两种思想。

    ShenduCC
  • LeetCode 146 LRU Cache

    实现一个缓存机制。很多人的写法都是使用HashTable, Map,Dictionary 或者别的工具。

    ShenduCC
  • setgid-修改权限的时候前边加的是2

    setgid详解 修改权限是让其他用户也有这个用户组下对应的权限,相当于 在这个用户组下一样 标记是 在-rwx–s–x 用户组那里的执行位是s ...

    逐梦的青春
  • 原 树莓派(raspberry)启用roo

    霡霂
  • LeetCode 250. 统计同值子树(递归)

    Michael阿明
  • LeetCode Weekly Contest 24 之 538.Convert BST to Greater Tree

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 查看linux里的initrd.img里的内容

    用户3765803
  • CentOS系统SSH免密后依然需要输入密码(已解决)

    1、问题 通过ssh-keygen -t rsa和ssh-copy-id -i node1操作后,免密登录依然需要输入密码。 [root@node1 ~]# s...

    程裕强
  • 104. Maximum Depth of Binary Tree

    Given a binary tree, find its maximum depth.

    ShenduCC

扫码关注云+社区

领取腾讯云代金券