Myhui

#include <iostream>
#include <cmath>
using namespace std;
const int maxn=25;
int n,key,index=0;
struct node{
    int data,height;          //data为结点值，height为该结点高
    int lchild,rchild;
}Node[maxn];
int getHeight(int root){      //得结点root的高（空结点高为0）
    if(root==-1) return 0;   
    return Node[root].height;
}
int getBalanceFactor(int root){  //得root的平衡因子（左子树高减右子树高）
    return getHeight(Node[root].lchild)-getHeight(Node[root].rchild);
}
void updateHeight(int root){     //更新root的高（左右子树中更高者的高加1）
    Node[root].height=max(getHeight(Node[root].lchild),getHeight(Node[root].rchild))+1;
}
void L(int &root){               //左旋转
    int temp=Node[root].rchild;
    Node[root].rchild=Node[temp].lchild;
    Node[temp].lchild=root;
    updateHeight(root);
    updateHeight(temp);
    root=temp;
}
void R(int &root){              //右旋转
    int temp=Node[root].lchild;
    Node[root].lchild=Node[temp].rchild;
    Node[temp].rchild=root;
    updateHeight(root);
    updateHeight(temp);
    root=temp;
}
void insert(int &root,int key){ //将值为key的点插入AVL中
    if(root==-1){               //到达空结点（即插入位置）
        Node[index].data=key;
        Node[index].height=1;   //结点初始高为1（插入的为叶结点）
        Node[index].lchild=Node[index].rchild=-1;
        root=index++;           //修改当前root
        return;
    }
    if(key<Node[root].data){    //比当前root值小，插入root的左子树
        insert(Node[root].lchild,key);
        updateHeight(root);     //更新树高
        if(getBalanceFactor(root)==2){ //以root为根的子树不平衡
            if(getBalanceFactor(Node[root].lchild)==1) //LL型（右单旋转）
                R(root);
            else if(getBalanceFactor(Node[root].lchild)==-1){//LR型（左右双旋转）
                L(Node[root].lchild);
                R(root);
            }
        }
    }
    else{
        insert(Node[root].rchild,key); //比当前root值大或相等，插入root右子树
        updateHeight(root);
        if(getBalanceFactor(root)==-2){
            if(getBalanceFactor(Node[root].rchild)==-1) //RR型（左单旋转）
                L(root);
            else if(getBalanceFactor(Node[root].rchild)==1){ //RL型（右左双旋转）
                R(Node[root].rchild);
                L(root);
            }
        }
    }
}
int main(){
    cin>>n;
    int root=-1;            //定义头结点（初始化根）
    for(int i=0;i<n;i++){   //建树
        cin>>key;
        insert(root,key);
    }    
    cout<<Node[root].data;  
    return 0;
}

发表于 2019-01-23 22:17:36 回复(0)

啥

总体思路：

模拟AVL树的插入过程

代码如下：

#include <iostream>

#define LH  1 // 左子树高
#define EH  0 // 等高
#define RH  -1// 右子树高

using namespace std;

struct AVLTreeNode
{
    int             m_nValue;   // 值
    int             m_nBf;      // 平衡因子
    AVLTreeNode*    m_pLeft;    // 左孩子
    AVLTreeNode*    m_pRight;   // 右孩子
};

// 平衡操作
void RightRotation(AVLTreeNode*& pRoot);
void LeftRotation(AVLTreeNode*& pRoot);
void LeftBanlance(AVLTreeNode*& pRoot);
void RightBanlance(AVLTreeNode*& pRoot);

// 常规操作
bool InsertAVL(AVLTreeNode*& pRoot, int value, bool &taller);

int main()
{
    ios::sync_with_stdio(false);
    // 建树
    AVLTreeNode* pRoot = NULL;
    bool taller = false;
    int value, N; cin >> N;
    for(int i=0; i<N; i++) {
        cin >> value;
        InsertAVL(pRoot, value, taller);
    }

    cout << pRoot->m_nValue << endl;

    return 0;
}


// 新结点插入成功，则返回true
// taller反映树是否长高
bool InsertAVL(AVLTreeNode*& pRoot, int value, bool &taller)
{
    if(!pRoot)  // 走到NULL处插入新节点
    {
        pRoot = new AVLTreeNode();
        pRoot->m_nBf = EH;
        pRoot->m_nValue = value;
        pRoot->m_pLeft = pRoot->m_pRight = NULL;
        taller = true;
    }
    else
    {
        if(value == pRoot->m_nValue) // 走到此步，说明要插入的节点已存在，返回false
        {
            taller = false;
            return false;
        }
        if(value < pRoot->m_nValue) //继续在pRoot的左子树中搜索插入位置
        {
            if(!InsertAVL(pRoot->m_pLeft, value, taller)) // 插入失败
                return false;
            if(taller) // 已插入pRoot的左子树,且左子树长高
            {
                switch(pRoot->m_nBf)
                {
                case LH: // 原本左侧就高，还插在了左侧，作左部平衡
                    LeftBanlance(pRoot);
                    taller = false;     // 平衡处理后树高不变
                    break;
                case EH: // 原本等高，插在左侧，树增高
                    pRoot->m_nBf = LH;
                    taller = true;
                    break;
                case RH: // 原本右侧高，插在左侧，树高不变
                    pRoot->m_nBf = EH;
                    taller = false;
                    break;
                }
            }
        }
        else    //继续在pRoot的右子树中搜索插入位置
        {
            if(!InsertAVL(pRoot->m_pRight, value, taller)) // 插入失败
                return false;
            if(taller) // 已插入pRoot的右子树,且右子树长高
            {
                switch(pRoot->m_nBf)
                {
                case LH: // 原本左侧高，插在右侧，树高不变
                    pRoot->m_nBf = EH;
                    taller = false;
                    break;
                case EH: // 原本等高，插在右侧，树增高
                    pRoot->m_nBf = RH;
                    taller = true;
                    break;
                case RH: // 原本右侧就高，还插在了右侧，作右部平衡
                    RightBanlance(pRoot);
                    taller = false;
                    break;
                }
            }
        }
    }
    return true;
}

// 左旋，以pRoot为根节点的树进行左旋处理,并调整好了父子链接
void LeftRotation(AVLTreeNode*& pRoot)
{
    // pRoot现为左上失衡节点, pRight为pRoot的右子结点， pRoot、pRight进行左旋转
    AVLTreeNode* pRight = pRoot->m_pRight;

    pRoot->m_pRight = pRight->m_pLeft;
    pRight->m_pLeft = pRoot;

    pRoot = pRight;
}

// 右旋，以pRoot为根节点的树进行右旋处理,并调整好了父子链接
void RightRotation(AVLTreeNode*& pRoot)
{
    // pRoot现为失衡节点, pLeft为pRoot的左子结点， pLeft、pRoot进行右旋转
    AVLTreeNode* pLeft = pRoot->m_pLeft;

    pRoot->m_pLeft = pLeft->m_pRight;
    pLeft->m_pRight = pRoot;

    pRoot = pLeft;
}

// 左部失重平衡处理，处理LL、LR
//以pRoot为根节点的树进行左平衡旋转处理
void LeftBanlance(AVLTreeNode*& pRoot)
{
    AVLTreeNode* pLeft, *pLeftRight;
    pLeft = pRoot->m_pLeft;
    switch(pLeft->m_nBf)
    {
    case LH:    // LL型
        pRoot->m_nBf = EH;
        pLeft->m_nBf = EH;
        RightRotation(pRoot);
        break;
    case RH:    // LR型
        pLeftRight = pLeft->m_pRight;
        switch(pLeftRight->m_nBf)
        {
        case LH:
            pRoot->m_nBf = RH;
            pLeft->m_nBf = EH;
            break;
        case EH:
            pRoot->m_nBf = EH;
            pLeft->m_nBf = EH;
            break;
        case RH:
            pRoot->m_nBf = EH;
            pLeft->m_nBf = LH;
            break;
        }
        pLeftRight->m_nBf = EH;
        LeftRotation(pRoot->m_pLeft); //这里pRoot->m_pLeft不能写成pLeft，否则关系没调整
        RightRotation(pRoot);
        break;
    }
}

// 右部失重平衡处理，处理RL、RR
//以pRoot为根节点的树进行右平衡旋转处理
void RightBanlance(AVLTreeNode*& pRoot)
{
    AVLTreeNode* pRight, *pRightLeft;
    pRight = pRoot->m_pRight;
    switch(pRight->m_nBf)
    {
    case RH:    // RR型
        pRoot->m_nBf = pRight->m_nBf = EH;
        LeftRotation(pRoot);
        break;
    case LH:    // RL型
        pRightLeft = pRight->m_pLeft;
        switch(pRightLeft->m_nBf)
        {
        case LH:
            pRoot->m_nBf = EH;
            pRight->m_nBf = RH;
            break;
        case EH:
            pRoot->m_nBf = EH;
            pRight->m_nBf = EH;
            break;
        case RH:
            pRoot->m_nBf = LH;
            pRight->m_nBf = EH;
            break;
        }
        pRightLeft->m_nBf = EH;
        RightRotation(pRoot->m_pRight); //这里pRoot->m_pRight不能写成pRight，否则关系没调整
        LeftRotation(pRoot);
        break;
    }
}

发表于 2015-11-30 15:06:45 回复(3)

C/C++

Sologala

/*
Sologala @github https://github.com/Sologala/PAT_OJ
PAT_oj No.1066_Root_of_AVL_Tree
*/

硬模拟AVL树的插入，每次调整旋转，最后输出树根节点。

值得注意的是：在用递归的方式来插入新节点，如果新插入的节点的值大于等于当前的根节点，那么插在右子树上，小于插在左子树上。

当插入完成之后函数返回之前可以检查当前节点是否满足平衡的定义。如果不满足就旋转，旋转的具体可以去查阅一下资料，注意旋转也变动了部分节点的高，所以在旋转之后需要更新一下他们的高度。这样函数每一层返回之后就将整个树调整好了。

ac_code

/*
    Sologala [@github](/profile/211017) https://github.com/Sologala/PAT_OJ
    PAT_oj No.1066 Root of AVL Tree
*/

	
	
		#include <cstdio>
	

	
		#include <algorithm> 
	


using namespace std;
struct node{
    int data,h=1;
    node* left=NULL,*right=NULL;
};
int getheight(node* r){
    return r==NULL?0:r->h;
}
int calBalance_factor(node* r){
    return r==NULL?0:getheight(r->left)-getheight(r->right);
}
void R(node* &r){
    node* temp =r->left;
    r->left =temp->right;
    temp->right =r;
    //更新两个变动节点的高
    r->h =1+max(getheight(r->left),getheight(r->right));
    temp->h =1+max(getheight(temp->left),getheight(temp->right));
    r =temp;
}
void L(node* &r){
    node* temp =r->right;
    r->right =temp->left;
    temp->left =r;
    //更新两个变动节点的高
    r->h =1+max(getheight(r->left),getheight(r->right));
    temp->h =1+max(getheight(temp->left),getheight(temp->right));
    r =temp;
}
int insert(node* &r,int num){
    if(!r){
        r=new node();
        r->data =num;
    }
    else{
        int child_h;
        if(num>=r->data) child_h=insert(r->right,num);
        else child_h=insert(r->left,num);
        if(child_h+1>r->h){                     
                r->h =child_h+1;
        }       
    }
    //check if curNode is unBalanced
    int bal_fac =calBalance_factor(r);
    if(bal_fac==2){//L
        int child_bal_fac =calBalance_factor(r->left);
        if(child_bal_fac==1){//LL
            R(r);
        }
        else if(child_bal_fac==-1){//LR
            L(r->left);
            R(r);
        }
    }
    else if(bal_fac==-2){//R
        int child_bal_fac =calBalance_factor(r->right);
        if(child_bal_fac==1){//RL
            R(r->right);
            L(r);
        }
        else if(child_bal_fac==-1){//RR
            L(r);
        }
    }
    return r->h;
}
int main(){
    int cnt;
    scanf("%d",&cnt);
    node* ROOT;
    for(int i=0;i<cnt;i++){
        int num;
        scanf("%d",&num);
        insert(ROOT,num);
    }
    printf("%d\n",ROOT->data);
    return 0;
}

编辑于 2019-01-22 17:33:43 回复(0)

C/C++

nbgao

#include <iostream> 
#include <cstdio>
#include <algorithm>

using namespace std;

struct Node{     int val,height;     Node *left,*right;
};

Node* newNode(int v)
{     Node* node = new Node;     node->val = v;     node->height = 1;     node->left = node->right = NULL;     return node; 
}

int getHeight(Node *node)
{     if(node == NULL)         return 0;     else         return node->height;
}

int getBalance(Node *node)
{     return getHeight(node->left) - getHeight(node->right);
}

void updateHeight(Node* node)
{     node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
}

void L(Node* &node)
{     Node *t = node->right;     node->right = t->left;     t->left = node;     updateHeight(node);     updateHeight(t);     node = t;
}

void R(Node* &node)
{     Node* t = node->left;     node->left = t->right;     t->right = node;     updateHeight(node);     updateHeight(t);     node = t;
}

void insert(Node* &root, int v)
{     if(root == NULL)     {         root = newNode(v);         return;     }     if(v < root->val){         insert(root->left, v);         updateHeight(root);         if(getBalance(root)==2)         {             if(getBalance(root->left)==1)                 R(root);             else if(getBalance(root->left)==-1){                 L(root->left);                 R(root);             }         }     }else{         insert(root->right, v);         updateHeight(root);         if(getBalance(root)==-2)         {             if(getBalance(root->right)==-1)                 L(root);                 else if(getBalance(root->right)==1)             {                 R(root->right);                 L(root);             }         }     }
}

int main()
{     int n;     Node *s = NULL;     cin>>n;     for(int i=0;i<n;i++)     {         int v;         cin>>v;         insert(s,v);     }     cout<<s->val<<endl;     return 0;
}

发表于 2018-03-01 01:35:05 回复(0)

C/C++

猫猫猫1

#include<bits/stdc++.h>
using namespace std;

struct node {
	int data,height;
	node* lchild,*rchild;
};

node* newnode(int v){
	node* Node=new node;
	Node->data=v;
	Node->height=1;
	Node->lchild=Node->rchild=NULL;
	return Node;
}

int geth(node* root) {
	if(root==NULL) return 0;
	return root->height;
}

int getBF(node* root) {
	return geth(root->lchild)-geth(root->rchild);
}

void uph(node* root) {
	root->height=max(geth(root->lchild),geth(root->rchild))+1;
}

void L(node* & root) {
	node* temp=root->rchild;
	root->rchild=temp->lchild;
	temp->lchild=root;
	uph(root);
	uph(temp);
	root=temp;
}

void R(node* & root) {
	node* temp=root->lchild;
	root->lchild=temp->rchild;
	temp->rchild=root;
	uph(root);
	uph(temp);
	root=temp;
}

void Insert(node* & root,int v){
	if(root==NULL){
		root=newnode(v);
		return ;
	}
	if(root->data>v){
		Insert(root->lchild,v);
		uph(root);
		if(getBF(root)==2){
			if(getBF(root->lchild)==1){
				R(root);
			}else{
				L(root->lchild);
				R(root);
			}
		}
	}else{
		Insert(root->rchild,v);
		uph(root);
		if(getBF(root)==-2){
			if(getBF(root->rchild)==-1){
				L(root);
			}else{
				R(root->rchild);
				L(root);
			}
		}
	}
}

int main(){
	int n,x;
	scanf("%d",&n);
	node* root=NULL;
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		Insert(root,x);
	}
	printf("%d\n",root->data);
	return 0;
}

发表于 2022-11-26 22:20:33 回复(0)

gyr679

模拟AVL树，实现左旋，右旋等操作。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> P;
typedef long long ll;

const int N = 1e5 + 5;

struct Node {
  int val;
  Node* left;
  Node* right;
  int ldep, rdep;
  Node(int val, Node* left, Node* right, int ldep, int rdep) {
    this->val = val;
    this->left = left;
    this->right = right;
    this->ldep = ldep;
    this->rdep = rdep;
  }
};

int n;
Node* root;

Node* create_node(int x) { return new Node(x, nullptr, nullptr, 0, 0); }

Node* roatate_left(Node* cur) {
  Node* right = cur->right;
  cur->right = right->left;
  right->left = cur;
  cur->rdep = right->ldep;
  right->ldep = max(cur->ldep, right->ldep) + 1;
  return right;
}

Node* rotate_right(Node* cur) {
  Node* left = cur->left;
  cur->left = left->right;
  left->right = cur;
  cur->ldep = left->rdep;
  left->rdep = max(cur->rdep, left->rdep) + 1;
  return left;
}

Node* rotate_left_right(Node* cur) {
  cur->left = roatate_left(cur->left);
  return rotate_right(cur);
}

Node* rotate_right_left(Node* cur) {
  cur->right = rotate_right(cur->right);
  return roatate_left(cur);
}

Node* insert(Node* cur, int x) {
  if (cur == nullptr) return create_node(x);
  if (x < cur->val) {
    cur->left = insert(cur->left, x);
    cur->ldep = max(cur->left->ldep, cur->left->rdep) + 1;
    // 当前点为失衡点
    if (cur->ldep - cur->rdep >= 2) {
      // 向左儿子的左子树插入导致失衡
      if (cur->left != nullptr && cur->left->ldep > cur->left->rdep)
        return rotate_right(cur);
      else
        return rotate_left_right(cur);  // 向左儿子的右子树插入导致失衡
    } else
      return cur;
  } else {
    cur->right = insert(cur->right, x);
    cur->rdep = max(cur->right->ldep, cur->right->rdep) + 1;
    // 当前点为失衡点
    if (cur->rdep - cur->ldep >= 2) {
      // 向右儿子的左子树插入导致失衡
      if (cur->right != nullptr && cur->right->ldep > cur->right->rdep)
        return rotate_right_left(cur);
      else
        return roatate_left(cur);  // 向右儿子的右子树插入导致失衡
    } else
      return cur;
  }
}

Node* insert(int x) {
  if (root == nullptr)
    return root = create_node(x);
  else
    return root = insert(root, x);
}

void print_avl(Node* cur) {
  if (cur == nullptr) return;
  print_avl(cur->left);
  cout << cur->val << ' ';
  print_avl(cur->right);
}

void debug() {
  cout << "avl的中序遍历为:\n";
  print_avl(root);
}

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    insert(x);
  }
  // debug();
  cout << root->val << endl;
  return 0;
}

发表于 2022-08-22 18:15:55 回复(0)

懒散之魂

C++手写AVL树全面详解

AVL树简介

AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树（Self-Balancing Binary Search Tree,简称平衡二叉树）。

一棵AVL树有如下必要条件：

条件一：它必须是二叉查找树。
条件二：每个节点的左子树和右子树的高度差至多为1。

图一中左边二叉树的节点45的左孩子46比45大，不满足二叉搜索树的条件，因此它也不是一棵平衡二叉树。
右边二叉树满足二叉搜索树的条件，同时它满足条件二，因此它是一棵平衡二叉树。

左边二叉树的节点45左子树高度2，右子树高度0，左右子树高度差为2-0=2，不满足条件二；右边二叉树的节点均满足左右子树高度差至多为1，同时它满足二叉搜索树的要求，因此它是一棵平衡二叉树。

AVL树的查找、插入、删除操作在平均和最坏的情况下都是O（logn），这得益于它时刻维护着二叉树的平衡。但由于每次插入都需要不断的调整和维护，所以，实际上如果插入操作次数太多则同样会陷入超时的死局，最具优势的操作在于查找，因为它的底层设计使得它无论插入多少个元素，这颗二叉树总是严格平衡的，所以AVL树适用于插入操作不是很频繁，但查找操作极度频繁的情况，如果需要在插入和查找操作找一个均衡点，那么就只能选择红黑树了。

AVL树的相关概念

平衡因子：将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)。
在图二右边的AVL树上：
节点50的左子树高度为3，右子树高度为2，BF= 3-2 = 1；
节点45的左子树高度为2，右子树高度为1，BF= 2-1 = 1；
节点46的左子树高度为0，右子树高度为0，BF= 0-0 = 0；
节点65的左子树高度为0，右子树高度为1，BF= 0-1 = -1；
对于平衡二叉树，BF的取值范围为[-1,1]。如果发现某个节点的BF值不在此范围，则需要对树进行调整。
最小不平衡树：距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树。

在图三中，左边二叉树的节点45的BF = 1，插入节点43后，节点45的BF = 2。节点45是距离插入点43最近的BF不在[-1,1]范围内的节点，因此以节点45为根的子树为最小不平衡子树。(这正好对应了递归的后序返回操作
中序的前驱和后继：顾名思义，就是中序遍历下的前一个结点和后一个结点，由于时二叉搜索树，所以中序遍历的前一个结点对应比这个结点小的最大结点，而后一个结点对应比这个结点大的最小结点。(这个可以看后面代码再进行理解)这个概念在进行删除结点的操作时很有用，因为删除结点后需要同时保证仍然为二叉搜索树。
关于对前驱和后继的一些寻找方法，请看我的另一篇博客：面试题 04.06. 后继者

AVL树的实现详解

总体思维导图实现。

1. 结点结构

struct node {
    int val;
    int depth;
    node *lchild;
    node *rchild;

    node() : val(0), lchild(nullptr), rchild(nullptr) {}

    node(int x) : val(x), lchild(nullptr), rchild(nullptr) {}
};

val，结点的值。
depth，该结点的高度(它的左右子树中最高的高度+1)。
lchild，左孩子。
rchild，右孩子。

2. AVL树的抽象数据结构（ADT）

class AVLTree {
    /*date part*/
    node *head;
    int length;
public:
    /*construct and destruct part*/
    AVLTree() : head(nullptr), length(0) {}

    AVLTree(int x) : head(new node(x)), length(1) {}

    ~AVLTree() {
        destroy(head);
    }

public:
    /*iterator part*/
    class iterator {//封装迭代器：内部类--只能调用外部类的静态函数
        node *head;
        node *root;
    public:
        iterator(node *head, node *root) : head(head), root(root) {}

        iterator &operator++();

        bool operator==(const iterator &x);

        bool operator!=(const iterator &x);

        iterator operator++(int);

        iterator &operator--();

        iterator operator--(int);

        int operator*();
    };

private:
    /*static member function*/
    /*Rotate Part*/
    static node *rotateRight(node *root);

    static node *rotateLeft(node *root);

    static node *rotateLeftRight(node *root);

    static node *rotateRightLeft(node *root);

    /*Destruct*/
    static void destroy(node *root);

    /*Getter*/
    static node *getNext(node *root, node *p);

    static node *getPre(node *root, node *p);

    static node *getMinNode(node *root);

    static node *getMaxNode(node *root);

    static int get_depth(node *root);

    static void update_depth(node *root);

    /*Insert&Remove*/
    static node *Insert(int x, node *root, int &size);

    static node *remove(int x, node *root, int &size);

    /*print_order*/
    static void inorder(node *root);

public:
    /*public interface*/
    /*clear&empty*/
    void clear();

    bool isEmpty();

    /*find*/
    bool find(int x);

    /*insert&remove*/
    void insert(int x);

    void remove(int x);

    /*size*/
    int size();

    /*begin&end*/
    iterator begin();

    iterator end();

    /*print*/
    void inorder_print();
};

3. AVL树高度相关操作

得到高度

static int get_depth(node *root) {//得到深度
    if (root == nullptr)
        return 0;
    return root->depth;
}

更新高度

static void update_depth(node *root) {
    if (root == nullptr)
        return;
    root->depth = std::max(get_depth(root->lchild), get_depth(root->rchild)) + 1;
}

4. 得到子树中最大/最小结点

原理：根据二叉搜索树中结点的左子树一定小于该结点，右子树一定大于该结点。

得到最大：直接遍历得出该结点的最右结点。

    static node* getMaxNode(node* root) {
        if (root == nullptr)
            return nullptr;
        while (root->rchild != nullptr)
            root = root->rchild;
        return root;
    }

得到最小：直接遍历得出该结点的最左结点。

    static node* getMinNode(node* root) {
        if (root == nullptr)
            return nullptr;
        while (root->lchild != nullptr)
            root = root->lchild;
        return root;
    }

5. 得到结点的前驱和后继

注意：二叉搜索树的前驱后继一般指的是它中序遍历的前一个和后一个结点，也就是从小到大排的前一个和后一个结点。

具体可以看我之前的博客--后继者

后继结点求解：如果有右子树，就是右子树的最小结点，如果没有，则是距离该节点最近的处于该节点右边的父节点。

static node* getNext(node* root, node* p) { //得到p节点的后继结点
    if (root == nullptr || p == nullptr) return nullptr;
    if (p->val >= root->val) {
        return getNext(root->rchild, p);
    } else {
        node* left = getNext(root->lchild, p);
        return left ? left : root;
    }
}

前驱结点求解：如果有左子树，就是左子树的最大结点，如果没有，则是距离该节点最近的处于该节点左边的父节点。

static node* getPre(node* root, node* p) { //得到p节点的前驱结点
    if (root == nullptr || p == nullptr)return nullptr;
    if (p->val <= root->val) {
        return getPre(root->lchild, p);
    } else {
        node* right = getPre(root->rchild, p);
        return right ? right : root;
    }
}

6. AVL树失衡的调整

节点的插入或删除都有可能导致AVL树失去平衡，因此，失衡调整是插入与删除操作的基础。
AVL树的失衡调整可以分为四种情况，我们逐一分析。
假设我们要为数组a[]={4，5，6，3，2，8，7，0，1}构建一棵AVL树。
情况一：左旋
首先插入{4，5，6}，在插入元素6后出现不平衡的情况：

当我们在右子树插入右孩子导致AVL失衡时，我们需要进行单左旋调整。旋转围绕最小失衡子树的根节点进行。
在删除新节点时也有可能会出现需要单左旋的情况。
左旋代码如下：

static node *rotateLeft(node *root) {
    node *son = root->rchild;
    root->rchild = son->lchild;
    son->lchild = root;
    update_depth(root);
    update_depth(son);
    return son;
}

情况二：右旋
我们继续插入元素{3，2}，此时二叉树为：

插入3、2后出现了不平衡的情况。此时的插入情况是“在左子树上插入左孩子导致AVL树失衡”，我们需要进行单右旋调整。
右旋代码：

static node *rotateRight(node *root) {//右旋
    node *son = root->lchild;
    root->lchild = son->rchild;
    son->rchild = root;
    update_depth(root);//更新深度(右旋只会对这两结点产生影响
    update_depth(son);
    return son;
}

情况三：先左旋后右旋
需要进行两次旋转的原因是第一次旋转后，AVL树仍旧处于不平衡的状态，第二次旋转再次进行调整。
我们继续插入元素{8，7}

这种情况，总结起来就是“在右子树上插入左孩子导致AVL树失衡",此时我们需要进行先右旋后左旋的调整。
调整的代码为：

static node *rotateLeftRight(node *root) {
    root->lchild = rotateLeft(root->lchild);
    return rotateRight(root);
}

结合例子进行分析：

首先对最小不平衡子树的根节点（也就是节点6）的右孩子（也就是8）进行右旋操作
再对节点6进行一次左旋操作

情况四：先右旋再左旋
根据对称性原理，当我们“在左子树上插入右孩子导致AVL树失衡",此时我们需要进行先左旋后右旋的调整。如果你不理解接着看图。
我们接着插入节点{0，1}

调整的代码:

static node *rotateRightLeft(node *root) {
    root->rchild = rotateRight(root->rchild);
    return rotateLeft(root);
}

结合例子进行分析：

首先对最小不平衡子树的根节点（也就是节点2）的左孩子（也就是0）进行左旋操作
再对节点2进行一次右旋操作

总结：四种失衡调整

7. 插入新结点

//需要是否兼容相等的元素，可通过对 x<root->val 或 x>root->val 这两个中的一个取等号即可
static node *Insert(int x, node *root, int& size) { //所有的deep的更新都在后序遍历后
    if (root == nullptr) {
        root = new node(x);
        size++;//创建结点后size++
    } else if (x < root->val) {
        root->lchild = Insert(x, root->lchild, size);
        //由于在更新该root结点之前，当平衡度未达到该要求之前肯定以及是进行了update_depth操作
        if (get_depth(root->lchild) - get_depth(root->rchild) == 2)
            root = x < root->lchild->val ? rotateRight(root) : rotateLeftRight(root);
    } else if (x > root->val) {
        root->rchild = Insert(x, root->rchild, size);
        if (get_depth(root->lchild) - get_depth(root->rchild) == -2)
            root = x > root->rchild->val ? rotateLeft(root) : rotateRightLeft(root);
    }
    update_depth(root);
    return root;
}

8. 删除结点

失衡的处理：
删除节点也可能导致AVL树的失衡，实际上删除节点和插入节点是一种互逆的操作：

删除右子树的节点导致AVL树失衡时，相当于在左子树插入节点导致AVL树失衡，即情况情况二或情况四。
删除左子树的节点导致AVL树失衡时，相当于在右子树插入节点导致AVL树失衡，即情况情况一或情况三。

维持排序树的处理：
另外，AVL树也是一棵二叉排序树，因此在删除节点时也要维护二叉排序树的性质。

如果删除结点为叶子结点，则直接删除，并不会改变搜索树的性质。
如果删除结点只有左子树或者右子树，则直接把要删除的结点的数据用下一个结点覆盖，然后删除下一个结点，由于复制了下一层的左右孩子指针，所以不会出现断层的。
如果删除结点左右子树都有，则找出该节点的前驱结点或后继结点的值进行覆盖(不覆盖指针，这样便仍然是排序二叉树了，然后继续递归寻找对应的前驱或者后继结点进行删除，因为左右子树都有，所以它们的前驱或者后继只能是叶子结点，找到直接删除即可。

删除处理代码：

我这里对删除操作进行了进一步优化，如果被删除结点的左右子树都存在，则查看左右子树的高度，如果左边高于右边则选择前驱结点进行删除，反之则后继。

static node *remove(int x, node *root, int& size) {
    if (root == nullptr)
        return nullptr;

    if (x == root->val) {
        /*左右子树均不为空---用中序的前驱或者后继来进行替换*/
        if (root->lchild != nullptr && root->rchild != nullptr) {
            /*根据左右子树的深度来选择删除替换哪边的*/
            if (get_depth(root->lchild) > get_depth(root->rchild)) {
                node* t = getMaxNode(root->lchild);
                root->val = t->val;
                root->lchild = remove(t->val, root->lchild, size);
            } else {
                node* t = getMinNode(root->rchild);
                root->val = t->val;
                root->rchild = remove(t->val, root->rchild, size);
            }
        }
        /*左右子树至少有一个为空的情况，直接往下走一步即可*/
        else {
            node* tmp = root->lchild == nullptr ? root->rchild : nullptr;
            if (tmp != nullptr) {
                *root = *tmp;
                delete tmp;
            }
            else {
                delete root;
                root = nullptr;
            }
            //删除时size--
            size--;
        }
    } else if (x < root->val) {
        root->lchild = remove(x, root->lchild, size);
        if (get_depth(root->lchild) - get_depth(root->rchild) == -2)
            root = get_depth(root->rchild->lchild) > get_depth(root->rchild->rchild) ? rotateRightLeft(root) : rotateLeft(root);
    } else {
        root->rchild = remove(x, root->rchild, size);
        if (get_depth(root->lchild) - get_depth(root->rchild) == 2)
            root = get_depth(root->lchild->rchild) > get_depth(root->lchild->lchild) ? rotateLeftRight(root) : rotateRight(root);
    }
    return root;
}

9. 查找元素

二叉树是一种递归的定义，因此，二叉树的许多操作都可以通过递归简单地实现，例如遍历二叉树、查找指定元素、销毁二叉树等。

这里使用了迭代方式。

bool find(int x) {
    //查找直接迭代方式即可
    node *f = head;
    while (f != nullptr) {
        if (x == f->val)
            return true;
        else if (x < f->val)
            f = f->lchild;
        else
            f = f->rchild;
    }
    return false;
}

10. 遍历二叉树

我这里只提供了中序遍历的打印，方便验证二叉搜索树的情况。

static void inorder(node *root) {
    if (root != nullptr) {
        inorder(root->lchild);
        printf("%d ", root->val);
        inorder(root->rchild);
    }
}

11. AVL树的销毁

直接利用后序先处理完左右子树再处理根节点。

static void destroy(node *root) {
    if (root == nullptr)
        return;
    destroy(root->lchild);
    destroy(root->rchild);
    delete root;
    root = nullptr;
}

12. 迭代器的设计

关于C++里面的迭代器，其实就是方便遍历容器中的元素，而迭代器需要模拟指针的行为，所以在C++中迭代器其实就是对指针特别包装的类，对其进行一些运算符的重载即可。

内部类充当迭代器

由于需要满足顺序容器的迭代顺序，所以++和--操作对应后继和前驱。

/*iterator part*/
    class iterator { //封装迭代器
        node* head;
        node* root;
    public:
        iterator(node* head, node* root): head(head), root(root) {}
        iterator& operator++() { //直接把root加为当前的后继结点
            root = getNext(head, root);
            return *this;
        }
        bool operator==(const iterator& x) {
            return this->root == x.root;
        }
        bool operator!=(const iterator& x) {
            return this->root != x.root;
        }
        iterator operator++(int) {
            iterator t = *this;
            root = getNext(head, root);
            return t;
        }
        iterator& operator--() { //直接把root赋值为前驱结点
            root = getPre(head, root);
            return *this;
        }
        iterator operator--(int) {
            iterator t = *this;
            root = getPre(head, root);
            return t;
        }
        node& operator*() { //解引用的重载
            return *root;
        }
    };

外部类提供外界begin()和end()接口得到迭代器的始端和末端

    iterator begin() {
        node* min = getMinNode(head);
        return iterator(head, min);
    }
    iterator end() { //end表示结束标记
        return iterator(head, nullptr);
    }

完整代码

我的GitHub

AVLTree.h

//
// Created by Alone on 2021/10/12.
//
#include <algorithm>
#include <cstdio>
#include <cassert>

#ifndef MY_TINY_STL_AVLTREE_H
#define MY_TINY_STL_AVLTREE_H
namespace L_B__ {
    struct node {
        int val;
        int depth;
        node *lchild;
        node *rchild;

        node() : val(0), lchild(nullptr), rchild(nullptr) {}

        node(int x) : val(x), lchild(nullptr), rchild(nullptr) {}
    };

    class AVLTree {
        /*date part*/
        node *head;
        int length;
    public:
        /*construct and destruct part*/
        AVLTree() : head(nullptr), length(0) {}

        AVLTree(int x) : head(new node(x)), length(1) {}

        ~AVLTree() {
            destroy(head);
        }

    public:
        /*iterator part*/
        class iterator {//封装迭代器：内部类--只能调用外部类的静态函数
            node *head;
            node *root;
        public:
            iterator(node *head, node *root) : head(head), root(root) {}

            iterator &operator++();

            bool operator==(const iterator &x);

            bool operator!=(const iterator &x);

            iterator operator++(int);

            iterator &operator--();

            iterator operator--(int);

            int operator*();
        };

    private:
        /*static member function*/
        /*Rotate Part*/
        static node *rotateRight(node *root);

        static node *rotateLeft(node *root);

        static node *rotateLeftRight(node *root);

        static node *rotateRightLeft(node *root);

        /*Destruct*/
        static void destroy(node *root);

        /*Getter*/
        static node *getNext(node *root, node *p);

        static node *getPre(node *root, node *p);

        static node *getMinNode(node *root);

        static node *getMaxNode(node *root);

        static int get_depth(node *root);

        static void update_depth(node *root);

        /*Insert&Remove*/
        static node *Insert(int x, node *root, int &size);

        static node *remove(int x, node *root, int &size);

        /*print_order*/
        static void inorder(node *root);

    public:
        /*public interface*/
        /*clear&empty*/
        void clear();

        bool isEmpty();

        /*find*/
        bool find(int x);

        /*insert&remove*/
        void insert(int x);

        void remove(int x);

        /*size*/
        int size();

        /*begin&end*/
        iterator begin();

        iterator end();

        /*print*/
        void inorder_print();
    };
}


#endif //MY_TINY_STL_AVLTREE_H

AVLTree.cpp

//
// Created by Alone on 2021/10/12.
//

#include "AVLTree.h"

/*Rotate*/
L_B__::node *L_B__::AVLTree::rotateRight(L_B__::node *root) {//右旋
    node *son = root->lchild;
    root->lchild = son->rchild;
    son->rchild = root;
    update_depth(root);//更新深度(右旋只会对这两结点产生影响
    update_depth(son);
    return son;
}

L_B__::node *L_B__::AVLTree::rotateLeft(L_B__::node *root) {
    node *son = root->rchild;
    root->rchild = son->lchild;
    son->lchild = root;
    update_depth(root);
    update_depth(son);
    return son;
}

L_B__::node *L_B__::AVLTree::rotateLeftRight(L_B__::node *root) {
    root->lchild = rotateLeft(root->lchild);
    return rotateRight(root);
}

L_B__::node *L_B__::AVLTree::rotateRightLeft(L_B__::node *root) {
    root->rchild = rotateRight(root->rchild);
    return rotateLeft(root);
}


/*Destruct*/
void L_B__::AVLTree::destroy(L_B__::node *root) {
    if (root == nullptr)
        return;
    destroy(root->lchild);
    destroy(root->rchild);
    delete root;
    root = nullptr;
}


/*Getter*/
L_B__::node *L_B__::AVLTree::getNext(L_B__::node *root, L_B__::node *p) {
    if (root == nullptr || p == nullptr) return nullptr;
    if (p->val >= root->val) {
        return getNext(root->rchild, p);
    } else {
        node *left = getNext(root->lchild, p);
        return left ? left : root;
    }
}

L_B__::node *L_B__::AVLTree::getPre(L_B__::node *root, L_B__::node *p) {
    if (root == nullptr || p == nullptr)return nullptr;
    if (p->val <= root->val) {
        return getPre(root->lchild, p);
    } else {
        node *right = getPre(root->rchild, p);
        return right ? right : root;
    }
}

L_B__::node *L_B__::AVLTree::getMinNode(L_B__::node *root) {
    if (root == nullptr)
        return nullptr;
    while (root->lchild != nullptr)
        root = root->lchild;
    return root;
}

L_B__::node *L_B__::AVLTree::getMaxNode(L_B__::node *root) {
    if (root == nullptr)
        return nullptr;
    while (root->rchild != nullptr)
        root = root->rchild;
    return root;
}

int L_B__::AVLTree::get_depth(L_B__::node *root) {
    if (root == nullptr)
        return 0;
    return root->depth;
}

void L_B__::AVLTree::update_depth(L_B__::node *root) {
    if (root == nullptr)
        return;
    root->depth = std::max(get_depth(root->lchild), get_depth(root->rchild)) + 1;
}


/*Insert&remove*/
L_B__::node *L_B__::AVLTree::Insert(int x, L_B__::node *root, int &size) {
    if (root == nullptr) {
        root = new node(x);
        size++;//创建结点后size++
    } else if (x < root->val) {
        root->lchild = Insert(x, root->lchild, size);
        //由于在更新该root结点之前，当平衡度未达到该要求之前肯定以及是进行了update_depth操作
        if (get_depth(root->lchild) - get_depth(root->rchild) == 2)
            root = x < root->lchild->val ? rotateRight(root) : rotateLeftRight(root);
    } else if (x > root->val) {
        root->rchild = Insert(x, root->rchild, size);
        if (get_depth(root->lchild) - get_depth(root->rchild) == -2)
            root = x > root->rchild->val ? rotateLeft(root) : rotateRightLeft(root);
    }
    update_depth(root);
    return root;
}

L_B__::node *L_B__::AVLTree::remove(int x, L_B__::node *root, int &size) {
    if (root == nullptr)
        return nullptr;

    if (x == root->val) {
        /*左右子树均不为空---用中序的前驱或者后继来进行替换*/
        if (root->lchild != nullptr && root->rchild != nullptr) {
            /*根据左右子树的深度来选择删除替换哪边的*/
            if (get_depth(root->lchild) > get_depth(root->rchild)) {
                node *t = getMaxNode(root->lchild);
                root->val = t->val;
                root->lchild = remove(t->val, root->lchild, size);
            } else {
                node *t = getMinNode(root->rchild);
                root->val = t->val;
                root->rchild = remove(t->val, root->rchild, size);
            }
        }
            /*左右子树至少有一个为空的情况，直接往下走一步即可*/
        else {
            node *tmp = root->lchild == nullptr ? root->rchild : nullptr;
            if (tmp != nullptr) {
                *root = *tmp;
                delete tmp;
            } else {
                delete root;
                root = nullptr;
            }
            //删除时size--
            size--;
        }
    } else if (x < root->val) {
        root->lchild = remove(x, root->lchild, size);
        if (get_depth(root->lchild) - get_depth(root->rchild) == -2)
            root = get_depth(root->rchild->lchild) > get_depth(root->rchild->rchild) ? rotateRightLeft(root)
                                                                                     : rotateLeft(root);
    } else {
        root->rchild = remove(x, root->rchild, size);
        if (get_depth(root->lchild) - get_depth(root->rchild) == 2)
            root = get_depth(root->lchild->rchild) > get_depth(root->lchild->lchild) ? rotateLeftRight(root)
                                                                                     : rotateRight(root);
    }
    return root;
}


/*print part*/
void L_B__::AVLTree::inorder(L_B__::node *root) {
    if (root != nullptr) {
        inorder(root->lchild);
        printf("%d ", root->val);
        inorder(root->rchild);
    }
}


/*clear&isEmpty*/
void L_B__::AVLTree::clear() {
    destroy(head);
}

bool L_B__::AVLTree::isEmpty() {
    return head == nullptr;
}


/*find*/
bool L_B__::AVLTree::find(int x) {
    //查找直接迭代方式即可
    node *f = head;
    while (f != nullptr) {
        if (x == f->val)
            return true;
        else if (x < f->val)
            f = f->lchild;
        else
            f = f->rchild;
    }
    return false;
}


/*insert&remove*/
void L_B__::AVLTree::insert(int x) {
    head = Insert(x, head, length);
}

void L_B__::AVLTree::remove(int x) {
    assert(length != 0);
    head = remove(x, head, length);
}

int L_B__::AVLTree::size() {
    return length;
}


/*begin&end*/
L_B__::AVLTree::iterator L_B__::AVLTree::begin() {
    node *min = getMinNode(head);
    return iterator(head, min);
}

L_B__::AVLTree::iterator L_B__::AVLTree::end() {
    return iterator(head, nullptr);
}

/*print*/
void L_B__::AVLTree::inorder_print() {
    printf("Inorder:# ");
    inorder(head);
}


/*iterator implement*/
bool L_B__::AVLTree::iterator::operator==(const L_B__::AVLTree::iterator &x) {
    return this->root == x.root;
}

bool L_B__::AVLTree::iterator::operator!=(const L_B__::AVLTree::iterator &x) {
    return this->root != x.root;
}

L_B__::AVLTree::iterator L_B__::AVLTree::iterator::operator++(int) {
    iterator t = *this;
    root = getNext(head, root);
    return t;
}

L_B__::AVLTree::iterator &L_B__::AVLTree::iterator::operator--() {
    root = getPre(head, root);
    return *this;
}

L_B__::AVLTree::iterator L_B__::AVLTree::iterator::operator--(int) {
    iterator t = *this;
    root = getPre(head, root);
    return t;
}

int L_B__::AVLTree::iterator::operator*() {
    return root->val;
}

L_B__::AVLTree::iterator &L_B__::AVLTree::iterator::operator++() {
    root = getNext(head, root);
    return *this;
}

测试

注意：以下数据由于存在大量相同的值，而我写的这个AVLTree并未对相同的值进行存储，所以节省了大量插入时候的调整时间，所以才能达到不错的插入性能，实际上只要实际插入的数据够多，和红黑树的差距就越大，我之前试过十亿不重复数据插入AVL和RB的测试，AVL运行几分钟，而RB一分钟内解决。但查找和删除方面AVL仍然是吊打RB(毕竟严格平衡树

与STL中的set（红黑树）进行对比：

测试代码

int main() {
    using namespace std;
    AVLTree x;
    set<int>Q;
    printf("插入测试\n");
    auto start = clock();
    for (int i = 0; i < 100000000; ++i) {
            x.insert(i%10000000);
    }
    std::cout<<"AVLTree"<<clock()-start<<"ms"<<std::endl;
    start = clock();
    for (int i = 0; i < 100000000; ++i) {
        Q.insert(i%10000000);
    }
    std::cout<<"RBTree"<<clock()-start<<"ms"<<std::endl;
    printf("迭代测试\n");
    start = clock();
    for(auto it = x.begin();it!=x.end();++it){
        continue;
    }
    std::cout<<"AVLTree"<<clock()-start<<"ms"<<std::endl;
    start = clock();
    for(auto it = Q.begin();it!=Q.end();++it){
        continue;
    }
    std::cout<<"RBTree"<<clock()-start<<"ms"<<std::endl;
    printf("查找测试\n");
    start = clock();
    for (int i = 0; i < 100000000; ++i) {
        x.find(i);
    }
    std::cout<<"AVLTree"<<clock()-start<<"ms"<<std::endl;
    start = clock();
    for(int i = 0;i<100000000;++i){
        Q.count(i);
    }
    std::cout<<"RBTree"<<clock()-start<<"ms"<<std::endl;
    printf("删除测试\n");
    start = clock();
    for(int i=0;i<10000000;i++){
        x.remove(i);
    }
    std::cout<<"AVLTree"<<clock()-start<<"ms"<<"length"<<x.size()<<std::endl;
    start = clock();
    for(int i=0;i<10000000;i++){
        Q.erase(i);
    }
    std::cout<<"RBTree"<<clock()-start<<"ms"<<"length"<<Q.size()<<std::endl;
    return 0;
}

测试总结

通过不断对比红黑树(RB)和AVL，得出以下结论：

插入操作红黑树比AVL快很多，数据量越大优势越明显。
查找和删除操作红黑树却是比AVL慢很多，同样也是数据量越大越明显。

总的来说，如果所需要管理的数据量很大，并且需要频繁的插入，那么红黑树更适合你，如果只需要插入一次后，对数据进行查找管理，那么AVL更加的适合你！

解题测试

OJ平台

在以上设计的基础上加个get_head方法即可。

#include <bits/stdc++.h>

struct node {
    int val;
    int depth;
    node *lchild;
    node *rchild;

    node() : val(0), lchild(nullptr), rchild(nullptr) {}

    node(int x) : val(x), lchild(nullptr), rchild(nullptr) {}
};

class AVLTree {
    /*date part*/
    node *head;
    int size;
public:
    /*construct and destruct part*/
    AVLTree() : head(nullptr),size(0) {}

    AVLTree(int x) : head(new node(x)),size(1) {}

    ~AVLTree() {
        destroy(head);
    }

private:
    /*static function part*/
    static node *rotateRight(node *root) {//右旋
        node *son = root->lchild;
        root->lchild = son->rchild;
        son->rchild = root;
        update_depth(root);//更新深度(右旋只会对这两结点产生影响
        update_depth(son);
        return son;
    }

    static node *rotateLeft(node *root) {
        node *son = root->rchild;
        root->rchild = son->lchild;
        son->lchild = root;
        update_depth(root);
        update_depth(son);
        return son;
    }

    static node *rotateLeftRight(node *root) {
        root->lchild = rotateLeft(root->lchild);
        return rotateRight(root);
    }

    static node *rotateRightLeft(node *root) {
        root->rchild = rotateRight(root->rchild);
        return rotateLeft(root);
    }

    static void destroy(node *root) {
        if (root == nullptr)
            return;
        destroy(root->lchild);
        destroy(root->rchild);
        delete root;
        root = nullptr;
    }
    static node* getMinNode(node* root){
        if(root== nullptr)
            return nullptr;
        while(root->lchild!= nullptr)
            root = root->lchild;
        return root;
    }
    static node* getMaxNode(node* root){
        if(root== nullptr)
            return nullptr;
        while(root->rchild!= nullptr)
            root = root->rchild;
        return root;
    }
    static int get_depth(node *root) {//得到深度
        if (root == nullptr)
            return 0;
        return root->depth;
    }

    static void update_depth(node *root) {
        if (root == nullptr)
            return;
        root->depth = std::max(get_depth(root->lchild), get_depth(root->rchild)) + 1;
    }

    static node *Insert(int x, node *root) {//所有的deep的更新都在后序遍历后
        if (root == nullptr) {
            root = new node(x);
        } else if (x <= root->val) {
            root->lchild = Insert(x, root->lchild);
            //由于在更新该root结点之前，当平衡度未达到该要求之前肯定以及是进行了update_depth操作
            if (get_depth(root->lchild) - get_depth(root->rchild) == 2)
                root = x <= root->lchild->val ? rotateRight(root) : rotateLeftRight(root);
        } else if (x > root->val) {
            root->rchild = Insert(x, root->rchild);
            if (get_depth(root->lchild) - get_depth(root->rchild) == -2)
                root = x >= root->rchild->val ? rotateLeft(root) : rotateRightLeft(root);
        }
        update_depth(root);
        return root;
    }

    static node *remove(int x, node *root) {
        if (root == nullptr)
            return nullptr;

        if (x == root->val) {
            /*左右子树均不为空---用中序的前驱或者后继来进行替换*/
            if (root->lchild != nullptr && root->rchild != nullptr) {
                /*根据左右子树的深度来选择删除替换哪边的*/
                if(get_depth(root->lchild)>get_depth(root->rchild)){
                    node* t = getMaxNode(root->lchild);
                    root->val = t->val;
                    root->lchild = remove(t->val,root->lchild);
                }else{
                    node* t = getMinNode(root->rchild);
                    root->val = t->val;
                    root->rchild = remove(t->val,root->rchild);
                }
            }
            /*左右子树至少有一个为空的情况，直接往下走一步即可*/
            else{
                node* tmp = root->lchild== nullptr?root->rchild: nullptr;
                if(tmp!= nullptr){
                    *root = *tmp;
                    delete tmp;
                }
                else{
                    delete root;
                    root = nullptr;
                }
            }
        } else if (x < root->val) {
            root->lchild = remove(x, root->lchild);
            if(get_depth(root->lchild)-get_depth(root->rchild)==-2)
                root = get_depth(root->rchild->lchild)>get_depth(root->rchild->rchild)?rotateRightLeft(root): rotateLeft(root);
        } else {
            root->rchild = remove(x, root->rchild);
            if(get_depth(root->lchild)-get_depth(root->rchild)==2)
                root = get_depth(root->lchild->rchild)>get_depth(root->lchild->lchild)?rotateLeftRight(root): rotateRight(root);
        }
        return root;
    }

    static void inorder(node *root) {
        if (root != nullptr) {
            inorder(root->lchild);
            printf("%d ", root->val);
            inorder(root->rchild);
        }
    }

public:
    /*public function part*/
    void insert(int x) {
        //递归方式插入，方便后续处理
        head = Insert(x, head);
        size++;
    }
    void remove(int x){
        assert(size!=0);
        head = remove(x,head);
        size--;
    }
    void clear() {
        destroy(head);
    }

    bool isEmpty() {
        return head == nullptr;
    }

    bool find(int x) {
        //查找直接迭代方式即可
        node *f = head;
        while (f != nullptr) {
            if (x == f->val)
                return true;
            else if (x < f->val)
                f = f->lchild;
            else
                f = f->rchild;
        }
        return false;
    }

    void inorder_print() {
        printf("Inorder:# ");
        inorder(head);
    }
    node* get_head(){
        return head;
    }
};

int main() {
    AVLTree x;
    int n;std::cin>>n;
    while(n--){
        int t;
        std::cin>>t;
        x.insert(t);
    }
    printf("%d",x.get_head()->val);
    return 0;
}

发表于 2021-10-13 01:24:03 回复(0)

NullNameMan

//思路：模拟平衡二叉树 构建

//对于AVL(二叉平衡树)的构建
#include<iostream>
(720)#include<cstdio>
#include<cstdlib>
(895)#include<algorithm>
#define MAX_SIZE 1000
(2562)#define EH 0
#define LH -1
(2563)#define RH 1
using namespace std;
struct Node{
    int value;
    int blance;
    Node* left,* right;
};
Node * Head =NULL;


Node* CreateNode(int value){
    Node * temp = (Node *)malloc(sizeof(Node));
    temp->value = value;
    temp->blance = EH;
    temp->left=temp->right = NULL;
    return temp;
}
int GetHeight(Node *root){
    if(root == NULL){
        return  0;
    }
    int l,r;
    l=GetHeight(root->left);
    r=GetHeight(root->right);
    return max(l,r)+1;
}

bool CheckBlance(Node *&root){
    int left,right;
    left = GetHeight(root->left);
    right = GetHeight(root->right);
    if(left>right) root->blance = LH;
    else if(left<right) root->blance =  RH;
    else root->blance = EH;
    if(abs(left-right)>=2) return true;
    else return false;
}

void TurnLeft(Node *&root){
//    cout<<"TurnLeft "<<root->value<<endl;

    Node *RightRoot = root->right;
 //      cout<<"Left Head : "<<RightRoot->value<<endl;
    root->right = RightRoot->left;
    RightRoot->left =  root;
    CheckBlance(root);
    CheckBlance(RightRoot);
    root=RightRoot;

}
void TurnRight(Node *&root){
 //   cout<<"TurnRight "<<root->value<<endl;
    Node* LeftRoot =  root->left;
    root->left = LeftRoot->right;
    LeftRoot->right = root;
    CheckBlance(root);
    CheckBlance(LeftRoot);
    root = LeftRoot;
}
void BlanceLeft(Node *&root){
  //    cout<<"BlanceLeft "<<root->value<<endl;
    Node* LeftRoot = root->left;
    if(LeftRoot->blance==RH){
   //     cout<<"before"<<root->left->value<<endl;
        TurnLeft(root->left);
   //     cout<<"after "<<LeftRoot->value<<endl;
        TurnRight(root);
    }else{
        TurnRight(root);
    }
}
void BlanceRight(Node * &root){
  //  cout<<"BlanceRight "<<root->value<<endl;
    Node* RightRoot = root->right;
    if(RightRoot->blance==LH){
        TurnRight(root->right);
  //      cout<<"value : "<<root->right->value<<endl;
        TurnLeft(root);
    }else{
   //     cout<<"TurnLeft"<<endl;
        TurnLeft(root);
    }
}

bool InsertNode(Node*& root,int value){
    if(root == NULL){
        Node *now = CreateNode(value);
        root = now;
        return true;
    }
    if(value==root->value){
        return false;
    }else if(value<root->value){
       InsertNode(root->left,value);
       if(CheckBlance(root)){
            BlanceLeft(root);
       }
    }else{
        InsertNode(root->right,value);
        if(CheckBlance(root))
            BlanceRight(root);
    }
}
int main(){
    int M;
    cin>>M;
    for(int i=0;i<M;i++){
        int t;
        cin>>t;
        InsertNode(Head,t);
   //     cout<<"HEAD = "<<Head->value<<endl;
    }
    if(!Head){
        cout<<"error"<<endl;
    }else{
        cout<<Head->value;
    }
    return 0;
}

发表于 2020-03-15 19:13:25 回复(0)

默默丶

//注意三点

//LL，RR,LR,RL。不是代表旋转方向，而是代表其插入新节点的位置，比如，LR是根结点的左子树的右子树上插入了新节点导致不平衡，那么此时应该先右旋再左旋，即先后调用LL（右旋），RR（左旋）。

//对于节点的平衡因子更新问题，个人理解，先递归插入节点，然后回溯的时候先更新其平衡因子（左子树高度-右子树高度），然后判断其是否平衡及应该调整的方式，注意在旋转后也应该更新高度产生变化的节点。

//插入时，根节点可能会变化，这时候需要在插入后返回调整后的根节点，若没有调整的话则返回之前的根节点，以便于下一次插入。

附上AC代码

#include<iostream>
(720)#include<queue>
#include<cstdio>
(802)#include<malloc.h>
using namespace std;
struct AVL {
	int val;
	AVL* left;
	AVL* right;
	int height;//1,0,-1
	AVL() :val(0), left(NULL), right(NULL), height(0) {}
};
int getHeight(AVL* node) {
	if (node == nullptr) return 0;
	return max(getHeight(node->left), getHeight(node->right)) + 1;
}
AVL* LL(AVL * node) {
	AVL* result = node->left;
	node->left = result->right;
	result->right = node;
	node->height = getHeight(node->left) - getHeight(node->right);
	result->height = getHeight(result->left) - getHeight(result->right);
	return result;
}
AVL* RR(AVL * node) {
	AVL* result = node->right;
	node->right = result->left;
	result->left = node;
	node->height = getHeight(node->left) - getHeight(node->right);
	result->height = getHeight(result->left) - getHeight(result->right);
	return result;
}
AVL* LR(AVL * node) {//左子树的右子树上插入了新节点导致不平衡
	node->left = RR(node->left);
	AVL* result = LL(node);
	//可以画图，从图中看出，最终结果只会有三个节点的高度改变
	return result;
}
AVL* RL(AVL * node) {//右子树的左子树上插入了新节点导致不平衡
	node->right = LL(node->right);
	AVL* result = RR(node);
	return result;
}
AVL* insert(AVL * root, int x) {
	if (root == NULL) {
		root = new AVL();
		root->val = x;
	}
	else if (root->val > x) {
		root->left=insert(root->left, x);
		root->height = getHeight(root->left) - getHeight(root->right);
		if (root->height == 2) {//不平衡
			if (root->left->height == 1) {
				return LL(root);
			}
			else if (root->left->height == -1) {//没有root->left->height==0这种情况
				return LR(root);
			}
		}
	}
	else {
		root->right=insert(root->right, x);
		root->height = getHeight(root->left) - getHeight(root->right);
		if (root->height == -2) {//不平衡
			if (root->right->height == -1) {
				return RR(root);
			}
			else if (root->right->height == 1) {//没有root->left->height==0这种情况
				return RL(root);
			}
		}
	}
	return root;
}
int main() {
	//freopen("C:\\Users\\47\\Desktop\\1.txt", "r", stdin);
	AVL* root = NULL;
	int n, x;
	cin >> n;
	while (n--) {
		cin >> x;
		root = insert(root, x);
	}
	printf("%d", root->val);
}

发表于 2020-03-15 15:24:48 回复(0)

learn_er

只看代码量的话我应该是最短的吧...有点过度优化了

#include<iostream>

struct node{
	int data,b;
	node*child[2];
};

int N,i;
node*T=NULL;

void rotate(node*&p,int j)//j=0顺时针，j=1逆时针
{	node*q;
	q=p->child[j];
	p->child[j]=q->child[1-j];
	q->child[1-j]=p;
	p=q;
}

int Insert(node*&p)//返回值表示插入后深度是否增加
{	if(!p){
		p=new node;
		p->data=i;
		p->b=0;
		p->child[0]=p->child[1]=NULL;
		return 1;
	}
	int j=(i>p->data);
	if(Insert(p->child[j])){//子树深度增加
		if(p->b!=j*(-2)+1)return p->b+=j*(-2)+1;//不失衡
		else if(p->child[j]->b==j*(-2)+1){//左-左、右-右失衡
				p->b=p->child[j]->b=0;
				rotate(p,j);
			}
			else{//左-右、右-左失衡
				rotate(p->child[j],1-j);
				rotate(p,j);
				p->child[0]->b=(p->b-1)/(-2);
				p->child[1]->b=(p->b+1)/(-2);
				p->b=0;
			}
	}
	return 0;
}

int main()
{
	std::cin>>N;
	while(N--){
		std::cin>>i;
		Insert(T);
	}
	std::cout<<T->data;
}

编辑于 2020-01-11 16:55:45 回复(0)

我A不出来啊！

不带相等处理地模仿了严蔚敏书里的AVL。

#include <iostream>
#define maxn 100
using namespace std;
int index=0;
struct node
{
	int value,bf;
	int Lchild,Rchild;
} nodes[maxn];
/*int getheight(int root)
{
	if(root==-1)return 0;
	return nodes[root].height;
}*/
/*void updateheight(int root)
{
	nodes[root].height=max(getheight(nodes[root].Lchild),getheight(nodes[root].Rchild))+1;
}*/
void R_rotate(int &root)
{
	int temp=nodes[root].Lchild;
	nodes[root].Lchild=nodes[temp].Rchild;
	nodes[temp].Rchild=root;
	//updateheight(root);
	//updateheight(temp);
	root=temp;
}
void L_rotate(int &root)
{
	int temp=nodes[root].Rchild;
	nodes[root].Rchild=nodes[temp].Lchild;
	nodes[temp].Lchild=root;
//	updateheight(root);
//	updateheight(temp);
	root=temp;
}
/*int getbf(int root)
{
	cout<<nodes[root].Lchild<<":"<<getheight(nodes[root].Lchild)<<"         "<<nodes[root].Rchild<<":"<<getheight(nodes[root].Rchild)<<endl;
	return getheight(nodes[root].Lchild)-getheight(nodes[root].Rchild);
}*/
void LeftBalance(int &root)
{
	int ld=nodes[root].Lchild;
	switch(nodes[ld].bf)
	{
		case 1://LL
		nodes[root].bf=0;
		nodes[ld].bf=0;
		R_rotate(root);
		break;
		case -1://LR
		int rd = nodes[ld].Rchild;
		switch(nodes[rd].bf)
		{
			case 1: nodes[root].bf=-1;nodes[ld].bf=0;break;
			case -1:nodes[root].bf=0;nodes[ld].bf=1;break;
			case 0:nodes[root].bf=0;nodes[ld].bf=0;break;
		}
		nodes[rd].bf=0;
		L_rotate(nodes[root].Lchild);
		R_rotate(root);
	}
}
void RightBalance(int &root)
{
	int rd=nodes[root].Rchild;
	switch(nodes[rd].bf)
	{
		case -1://RR
		nodes[root].bf=0;
		nodes[rd].bf=0;
		L_rotate(root);
		break;
		case 1://RL
		int ld = nodes[rd].Lchild;
		switch(nodes[ld].bf)
		{
			case 1: nodes[root].bf=0;nodes[rd].bf=-1;break;
			case -1:nodes[root].bf=1;nodes[rd].bf=0;break;
			case 0:nodes[root].bf=0;nodes[rd].bf=0;break;
		}
		nodes[ld].bf=0;
		R_rotate(nodes[root].Rchild);
		L_rotate(root);
	}
}
void AVLinsert(int &root,int value,bool &taller)
{
	if(root==-1)
	{
		nodes[index].value=value;
		nodes[index].Lchild=-1;
		nodes[index].Rchild=-1;
		//nodes[index].height=1;
		nodes[index].bf=0;
		root=index++;
		taller=true;
		//cout<<"root:"<<root<<" value:"<<value<<endl;
		return ;
	}
	else
	{
		if(value<nodes[root].value)
		{
			AVLinsert(nodes[root].Lchild,value,taller);
			//cout<<nodes[root].Lchild<<"taller:"<<taller<<endl;
			if(taller)
			{
				switch(nodes[root].bf){
					case 1: 
					 LeftBalance(root);
					 taller = false;break;
					case -1:nodes[root].bf=0; taller=false;break;
					case 0: nodes[root].bf=1; taller =true;break;
				}
			}
			/*updateheight(root);
			if(getbf(root)==2)
			{
				if(getbf(nodes[root].Lchild)==1)//LL
				{
				//	cout<<"LL";
					R_rotate(root);
				}
				else if(getbf(nodes[root].Lchild)==-1)//LR
				{
					//cout<<"LR";
					L_rotate(nodes[root].Lchild);
					R_rotate(root);
				}
			}
			*/	
		}
		else
		{
			AVLinsert(nodes[root].Rchild,value,taller);
			if(taller)
			{
				switch(nodes[root].bf){
					case 1: nodes[root].bf=0;	taller = false;break;
					case -1:RightBalance(root); 	taller=false;break;
					case 0: nodes[root].bf=-1;	taller =true;break;
				}
			}
			/*updateheight(root);
			//cout<<root<<"height:"<<nodes[root].height<<"  bf:"<<getbf(root)<<endl;
			if(getbf(root)==-2)
			{
				if(getbf(nodes[root].Rchild)==1)//RL
				{
					//cout<<"RL";
					R_rotate(nodes[root].Rchild);
					L_rotate(root); 
				}
				else if(getbf(nodes[root].Rchild)==-1)//RR
				{
					//cout<<"RR";
					L_rotate(root);
				}
			}*/
		}
	}
}
int main()
{
	int N;
	cin>>N;
	int root=-1;
	bool taller;
	for(int i=0;i<N;i++)
	{
		taller=false;
		int num;
		cin>>num;
		AVLinsert(root,num,taller);
	}
	//for(int i=0;i<N;i++)
	//cout<<nodes[i].Lchild<<" "<<nodes[i].Rchild<<endl;
	//cout<<root<<" "<<nodes[root].Rchild<<endl;
	cout<<nodes[root].value;
}

发表于 2019-11-22 18:55:14 回复(0)

C/C++

Theturing

#include <stdlib.h>

#include <stdio.h>

#define datatype int

typedef struct Treenode {

intfrst_visit;

datatype data;

struct Treenode *lch;

struct Treenode *rch;

} BiNode, *BiTree;

namespace bin_tree {

intGetHeight(BiTree bt) {

if(bt) {

intl = GetHeight(bt->lch);

intr = GetHeight(bt->rch);

return((l > r) ? l : r)+1;

}

return-1;

}

intGet_Hght_Dffrnce(BiTree bt) {

inthl = GetHeight(bt->lch);

inthr = GetHeight(bt->rch);

returnhl - hr;

}

voidshow(datatype *ord) {

for(;*ord; ord++) {

printf("%c", *ord);//cout<<*ord<<" ";

}

printf("\n");

}

BiTree rotate_R(BiTree root) {

BiTree t = root->lch;

root->lch = t->rch;

t->rch = root;

returnt;

}

BiTree rotate_L(BiTree root) {

BiTree t = root->rch;

root->rch = t->lch;

t->lch = root;

returnt;

}

BiTree rotate_RL(BiTree root) {

root->rch = rotate_R(root->rch);

returnrotate_L(root);

}

BiTree rotate_LR(BiTree root) {

root->lch = rotate_L(root->lch);

returnrotate_R(root);

}

using namespace bin_tree;

namespace ravl{

intN;

BiTree Insert(BiTree root, datatype value) {

if(root == NULL) {

root = (BiTree)malloc(sizeof(BiNode));

root->data = value;

root->frst_visit = 1;

root->lch = NULL;

root->rch = NULL;

}

elseif(value < root->data) {

root->lch = Insert(root->lch, value);

if(Get_Hght_Dffrnce(root) == 2) {

if(value < root->lch->data) root = rotate_R(root);

elseroot = rotate_LR(root);

}

else{

root->rch = Insert(root->rch, value);

if(Get_Hght_Dffrnce(root) == -2) {

if(value >= root->rch->data) root = rotate_L(root);

elseroot = rotate_RL(root);

}

returnroot;

}

voidstart() {

scanf("%d", &N);

BiTree RT = NULL;

for(inti = 0; i < N; i++) {

intv;

scanf("%d", &v);

RT = Insert(RT, v);

}

printf("%d", RT->data);

return;

}

//using namespace ioh;

using namespace ravl;

intmain() {

//Input_from_file("data.txt","r");

start();

//Close_in();

return0;

}

发表于 2019-06-12 01:38:18 回复(0)

C/C++

SylviaShen

AVL树，代码不太长。没有在节点里存高度或者平衡因子，因为节点数太少了，索性现用现算，这样就不必管高度的更新了，少很多事。

# include <cstdio>

#define max(a,b) ((a)>(b)? (a):(b))

struct node {
    int data;
    node *p, *lc, *rc;
};

node *root = NULL;
int N;

int hgt(node* pos) { //节点的高度,空树的高度为-1，单个节点的高度为0，有一个孩子的节点高度为1
    if (pos == NULL) return -1;
    return max(hgt(pos->lc), hgt(pos->rc)) + 1;
}

int balFac(node *pos) { //左孩子高度-右孩子高度
    int lh, rh;
    if (pos->lc == NULL) lh = -1; else lh = hgt(pos->lc);
    if (pos->rc == NULL) rh = -1; else rh = hgt(pos->rc);
    return lh - rh;
}

void insertAsRoot(int n) { //插入 root
    root = new node;
    root->data = n;
    root->lc = NULL;
    root->rc = NULL;
    root->p = NULL;
}

node *insertAsLc(node *pos, int n) { //插入到pos的左孩子
    node *newnode = new node;
    newnode->data = n;
    newnode->lc = NULL;
    newnode->rc = NULL;
    newnode->p = pos;
    pos->lc = newnode;
    return newnode;
}

node *insertAsRc(node *pos, int n) { //插入到pos的右孩子
    node *newnode = new node;
    newnode->data = n;
    newnode->lc = NULL;
    newnode->rc = NULL;
    newnode->p = pos;
    pos->rc = newnode;
    return newnode;
}

void leftRotate(node *pos) {
    node *b = pos->rc, *c = pos->rc->rc, *d = pos->rc->lc, *e = pos->lc;
    if (pos->p) {
        if (pos->p->lc == pos) { //是左孩子
            pos->p->lc = b;
        }
        else if (pos->p->rc == pos) { //是右孩子
            pos->p->rc = b;
        }
    }
    else {
        root = b;
    }
    b->p = pos->p;
    pos->rc = d; if (d) d->p = pos;
    b->lc = pos; pos->p = b;
}

void rightRotate(node *pos) {
    node *b = pos->lc, *c = pos->lc->lc, *d = pos->lc->rc, *e = pos->rc;
    if (pos->p) {
        if (pos->p->lc == pos) { //是左孩子
            pos->p->lc = b;
        }
        else if (pos->p->rc == pos) { //是右孩子
            pos->p->rc = b;
        }
    }
    else { //转的是root
        root = b;
    }
    b->p = pos->p;
    pos->lc = d; if(d) d->p = pos;
    pos->p = b; b->rc = pos;
}

void insert(int n) {
    if (root == NULL) { //空的
        insertAsRoot(n);
    }
    else { //树非空
        node *x = root, *prev = NULL;
        while (x) {
            if (n < x->data) {
                prev = x; x = x->lc;
            }
            else {
                prev = x; x = x->rc;
            }
        }
        if (n < prev->data) x = insertAsLc(prev, n); else x = insertAsRc(prev, n); //插入节点
        x = x->p->p; //爷爷可能开始不平衡
        while (x) { //找最先失衡的祖先
            if (balFac(x) >= 2 || balFac(x) <= -2) {
                if (balFac(x) == -2 && balFac(x->rc) == -1) {
                    leftRotate(x);
                }
                else if (balFac(x) == 2 && balFac(x->lc) == 1) {
                    rightRotate(x);
                }
                else if (balFac(x) == -2 && balFac(x->rc) == 1) {
                    rightRotate(x->rc);
                    leftRotate(x);
                }
                else if(balFac(x) == 2 && balFac(x->lc) == -1) {
                    leftRotate(x->lc);
                    rightRotate(x);
                }
                break;
            }
            x = x->p;
        }
    }
}

int main() {
    scanf("%d", &N);
    int t;
    for (int i = 0; i < N; i++) {
        scanf("%d", &t);
        insert(t);
    }

    printf("%d", root->data);

    return 0;
}

发表于 2018-03-16 22:58:12 回复(0)

C/C++

OFShare

//AVL树的插入实现。
//插入涉及四种旋转，LL,LR,RR,RL。
//递归插入构建AVL，回溯的时候注意更新节点的高度即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn=20+5;
int cnt,n;
struct node{
    int value,height=0;
    node *lch=0,*rch=0;
}A[maxn];
int h(node *rt){
    return rt?rt->height:0;
}
node *LL(node *k2){
    node* k1=k2->lch;
    k2->lch=k1->rch;
    k1->rch=k2;
    k2->height=max(h(k2->lch),h(k2->rch))+1;
    k1->height=max(h(k1->lch),h(k1->rch))+1;
    return k1;
}
 
node *RR(node *k1){
    node *k2=k1->rch;
    k1->rch=k2->lch;
    k2->lch=k1;
    k1->height=max(h(k1->lch),h(k1->rch))+1;
    k2->height=max(h(k2->lch),h(k2->rch))+1;
    return k2;
}
 
node *LR(node *k3){
    k3->lch=RR(k3->lch);
    return LL(k3);
}
 
node *RL(node *k1){
    k1->rch=LL(k1->rch);
    return RR(k1);
}
node *insert(node *rt,int x){
    if(!rt){
        rt=&A[++cnt];
        rt->value=x;
        rt->height=1;
        return rt;
    }
    if(x<rt->value){
        rt->lch=insert(rt->lch,x);
        if(h(rt->lch)-h(rt->rch)==2){
            rt=(x<rt->lch->value)?LL(rt):LR(rt);
        }
    }else{
        rt->rch=insert(rt->rch,x);
        if(h(rt->rch)-h(rt->lch)==2){
            rt=(x>rt->rch->value)?RR(rt):RL(rt);
        }
    }
    rt->height=max(h(rt->lch),h(rt->rch))+1;
    return rt;
}
int main(){
    scanf("%d",&n);node *root=0;
    for(int i=1,x;i<=n;++i){
        scanf("%d",&x);
        root=insert(root,x);
    }
    printf("%d\n",root->value);
    return 0;
}

发表于 2018-03-09 18:02:52 回复(0)

Physicaloser

#include <cstdio>
#include <cstdlib>
#define max(x, y) (((x) > (y)) ? (x) : (y))
typedef struct tnode
{
    int val;
    struct tnode * left;
    struct tnode * right;
} node;

//LL：右旋转
node * rotate_right(node * root) {
    node * lnode = root->left;
    root->left = lnode->right;
    lnode->right = root;
    return lnode;
}

//RR：左旋转
node * rotate_left(node * root) {
    node * rnode = root->right;
    root->right = rnode->left;
    rnode->left = root;
    return rnode;
}

//LR：先左旋转，再右旋转
node * rotate_left_right(node * root) {
    root->left = rotate_left(root->left);
    return rotate_right(root);
}

//RL：先右旋转，再左旋转
node * rotate_right_left(node * root) {
    root->right = rotate_right(root->right);
    return rotate_left(root);
}

//递归求得以root为根节点的树的高度
int get_height(node * root) {
    if (root == NULL)   return 0;
    return max(get_height(root->left), get_height(root->right)) + 1;
}

//在以root为根节点的树中插入值为val的节点
node * insert(node * root, int val) {
    if (root == NULL) {
        root = (node *) malloc(sizeof(node));
        root->val = val;
        root->left = NULL;
        root->right = NULL;
    } else if (val < root->val) {
        root->left = insert(root->left, val);
        if (get_height(root->left) - get_height(root->right) == 2) {
            if (val < root->left->val)      root = rotate_right(root);
            else                            root = rotate_left_right(root);
        }
    } else {
        root->right = insert(root->right, val);
        if (get_height(root->right) - get_height(root->left) == 2) {
            if (val > root->right->val)     root = rotate_left(root);
            else                            root = rotate_right_left(root);
        }
    }

    return root;
}


int main(void) {
    int n, val;
    node * root = NULL;

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &val);
        root = insert(root, val);
    }
    printf("%d\n", root->val);

    return 0;
}

发表于 2018-03-08 11:09:52 回复(0)

RicardoZi

//其实就是最基础的AVL树的模拟题
#include <cstdio>
#include <algorithm>
using namespace std;
struct Node{
    int val, height;
    Node *left, *right;
};

Node* newnode(int v){
    Node* node = new Node;
    node->val = v;
    node->height = 1;
    node->left = node->right = NULL;
    return node;
}

int getHeight(Node* node){
    if(node == NULL) return 0;
    else return node->height;
}

int getBalanceFactor(Node* node){
    return getHeight(node->left) - getHeight(node->right);
}

void updateHeight(Node* node){
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
}

void L(Node* &node){     //左旋操作
    Node* temp = node->right;
    node->right = temp->left;
    temp->left = node;
    updateHeight(node);
    updateHeight(temp);
    node = temp;
}

void R(Node* &node){       //右旋操作
    Node* temp = node->left;
    node->left = temp->right;
    temp->right = node;
    updateHeight(node);
    updateHeight(temp);
    node = temp;
}

void insert(Node* &root, int v){
    if(root == NULL){
        root = newnode(v);
        return;
    }
    if(v < root->val){
        insert(root->left, v);
        updateHeight(root);
        if(getBalanceFactor(root) == 2){
            if(getBalanceFactor(root->left) == 1)
                R(root);
            else if(getBalanceFactor(root->left) == -1){
                L(root->left);
                R(root);
            }
        }
    }else{
        insert(root->right, v);
        updateHeight(root);
        if(getBalanceFactor(root) == -2){
            if(getBalanceFactor(root->right) == -1)
                L(root);
            else if(getBalanceFactor(root->right) == 1){
                R(root->right);
                L(root);
            }
        }
    }
}

int main(){
    int n;
    Node *s = NULL;
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        int v;
        scanf("%d", &v);
        insert(s, v);
    }
    printf("%d\n", s->val);
    return 0;
}

编辑于 2018-03-05 14:05:42 回复(0)

光眸

AVL树结点的插入总体分为几个大步骤：

1.把目标值插入正确的地方。

2.刷新各个结点的平衡因子。

3.根据平衡因子来旋转。

现在贴出单独的插入结点的函数：

bool ins_AVLtree(AVLTree *avlt, KeyType k){
	AVLTreeNode S,A,FA,p,fp,B,C;  //A为记录最后一个平衡因子不为0的结点
	                            //FA为记录最后一个平衡因子不为0的结点的父节点
								//p为用来搜索要插入地方的临时结点，之后作为修改平衡因子的中介结点
								//fp为p的父节点
								//B为需要修改平衡因子的路径的最前面的结点（层数在B之上的结点就不需要改平衡因子了，因为旋转后就平衡了）
								//同时，B也是做旋转变换所涉及的最上层结点
								//C为设计旋转变换三因子的第三个因子
								//S为待插入结点 
	S = (AVLTree)malloc(sizeof(AVLTreeNode));  
	S->LChild = NULL;
	S->RChild = NULL;
	S->bf = 0;
	S->key = k;
	if(*avlt == NULL){              //原树为空树，那S就直接作为根节点就好了，返回 
		*avlt = S;
		return true; 
	} 
	A = *avlt;   FA = NULL;
	p = *avlt;   fp = NULL;
	while(p != NULL){
		if(p->bf!=0){                //若检测到某结点平衡因子不为0，那么用A和FA记录它与他的父节点 
			A = p;
			FA = fp;
		}
		fp = p;                       //fp用来记录搜索的最后一个结点，等价于要插入结点的父结点 
		if(S->key < p->key)           //按条件制定搜索方向 
			p = p->LChild;
		else if(S->key > p->key)
			p = p->RChild;
		else
			return false;             //若原AVL树中已经存在KEY一样的结点，则插入失败，返回 
	}
	if(S->key < fp->key)              //确定应该作为其父结点的左孩子还是右孩子 
		fp->LChild = S;
	else
		fp->RChild = S;
	if(S->key < A->key){              //将B作为旋转三剑客的第二位确定下来，若插入的结点在A的左子树中，那么先变A的平衡因子， 
		B = A->LChild;                //为什么A父结点以上的结点平衡因子不变呢？因为一会儿调整完以后其实A以上的平衡因子是相当于没有变的 
		A->bf = A->bf+1;              //那么如果原来所有结点都是平衡的话，那么A就指向根节点，相当于S到根节点路径上所有结点的平衡因子都变了。 
	} 
	else{
		B = A->RChild;
		A->bf = A->bf-1;
	}
	p = B;
	while(p!=S){
		if(S->key < p->key){               // 因为经过刚才的处理后，A已经是最后一个平衡因子不为0的结点了，所以B（包括B）到S之间的 
			p->bf = 1;					   //结点的平衡因子原来都是0，所以可以直接改成-1或1 
			p = p->LChild;             
		}       
		else{
			p->bf = -1;
			p = p->RChild;
		}
	}
	//========================================
	if(A->bf==2 && B->bf==1){          //说明这是LL型不平衡 
		
		B = A->LChild;                 
		A->LChild = B->RChild;          
		B->RChild = A;
		A->bf = 0;                     //调整后A的平衡因子是0		                            
		B->bf = 0;                     //因为B原来是左子树深度多1，调整后右子树A的平衡因子是0所以B仅仅是右子树多了1平衡后就成0了 
		if(FA == NULL)	*avlt = B;     //如果A是根结点，那么B替代A成为根结点 
		else if(A == FA->LChild)	FA->LChild = B;     //调整旋转域与非旋转域之间的关系 
		else						FA->RChild = B;
	}
	if(A->bf==-2 && B->bf==-1){      //说明这是RR型不平衡 
		B = A->RChild;
		A->RChild = B->LChild;
		B->LChild = A;
		A->bf = 0;
		B->bf = 0;
		if(FA == NULL)				*avlt = B;
		else if(A == FA->LChild)	FA->LChild = B;
		else						FA->RChild = B;
	}
	
	if(A->bf == 2 && B->bf == -1){  //说明这是LR型不平衡 
		B = A->LChild;
		C = B->RChild;
		B->RChild = C->LChild;
		A->LChild = C->RChild;
		C->LChild = B;
		C->RChild = A;
		if(S->key < C->key){         //说明插入结点在C的左子树边，也就是说C的左子树会比右子树深，所以右子树挂载为A的左子树时会少 
			A->bf = -1;              //分配一个深度，所以A的右子树也就会比左子树多一个深度，所以为-1 
			B->bf = 0;
			C->bf = 0;
		}
		else if(S->key > C->key){
			A->bf = 0;
			B->bf = 1;
			C->bf = 0;
		}
		else{
			A->bf = 0;
			B->bf = 0;
		}
		if(FA == NULL)				*avlt = C;
		else if(A == FA->LChild)	FA->LChild = C;
		else						FA->RChild = C;
	}
	if(A->bf == -2 && B->bf == 1){  //说明这是RL型不平衡 
		B = A->RChild;
		C = B->LChild;
		B->LChild = C->RChild;
		A->RChild = C->LChild;
		C->LChild = A;
		C->RChild = B;
		if(S->key < C->key){
			B->bf = -1;
			A->bf = 0;
			C->bf =0; 
		}
		else if(S->key > C->key){
			A->bf = 1;
			B->bf = 0;
			C->bf = 0;
		}
		else{
			A->bf = 0;
			B->bf = 0;
		}
		if(FA == NULL)				*avlt = C;
		else if(A == FA->LChild)	FA->LChild = C;
		else						FA->RChild = C;
	} 

}

然后这是完整程序：

#include<iostream>
#include<cstdlib>
using namespace std;
typedef struct node{
	int bt;
	int key;
	struct node* Lchild;
	struct node* Rchild;
}AVLTNode,*AVLTree;

void Ins_AVLTree(AVLTree *T,int key){
	AVLTNode *S = (AVLTNode *)malloc(sizeof(AVLTNode));
	S->key = key;
	S->bt = 0;
	S->Lchild = NULL;
	S->Rchild = NULL;
	if((*T) == NULL){
		*T = S;
		return;
	}
	AVLTNode *p,*fp,*A,*FA,*B,*C;   //A是指向最后一个平衡因子不为0的结点，ABC构成旋转三剑客. 
	p = (*T);	fp = NULL;
	A = (*T);	FA = NULL;
	B = NULL;	C  = NULL;
	while(p!=NULL){
		if(p->bt != 0){
			A = p;
			FA = fp;
		}
		fp = p;
		if(S->key < p->key){
			p = p->Lchild;
		}
		else if(S->key > p->key){
			p = p->Rchild;
		}
		else 
			return;
	}

	if(S->key < fp->key){
		fp->Lchild = S;
	}
	else{
		fp->Rchild = S;
	}
	if(S->key < A->key){
		B = A->Lchild;
		A->bt = A->bt + 1;
	}
	else{
		B = A->Rchild;
		A->bt = A->bt - 1;
	}
	p = B;
	while(p!=S){          //修改B开始到S之间结点的平衡因子（因为B开始后的结点之前的平衡因子都是0，所以直接置1或-1即可） 
		if(key < p->key){
			p->bt = 1;
			p = p->Lchild;
		}
		else{
			p->bt = -1;
			p = p->Rchild;
		}
	}
	if(A->bt == 2 && B->bt == 1){  //LL旋转 
		A->Lchild = B->Rchild;
		B->Rchild = A;
		B->bt = 0;
		A->bt = 0;
		if(FA == NULL)			(*T) = B;
		else if(A == FA->Lchild) FA->Lchild = B;
		else					FA->Rchild = B;
	}
	if(A->bt == -2 && B->bt == -1){ //RR旋转 
		A->Rchild = B->Lchild;
		B->Lchild = A;
		B->bt = 0;
		A->bt = 0;
		if(FA == NULL)			(*T) = B;
		else if(A == FA->Lchild) FA->Lchild = B;
		else					FA->Rchild = B;
	}
	if(A->bt == 2 && B->bt == -1){  //LR旋转 
		C = B->Rchild;
		B->Rchild = C->Lchild;
		A->Lchild = C->Rchild;
		C->Lchild = B;
		C->Rchild = A;
		if(key < C->key){
			A->bt = -1;
			B->bt = 0;
			C->bt = 0;
		}
		else if(key > C->key){
			B->bt = 1;
			A->bt = 0;
			C->bt = 0;
		}
		else{
			A->bt = 0;
			B->bt = 0;
		}
		if(FA == NULL)			(*T) = C;
		else if(A == FA->Lchild) FA->Lchild = C;
		else					FA->Rchild = C;
	}
	if(A->bt == -2 && B->bt == 1){  //RL旋转 
		C = B->Lchild;
		A->Rchild = C->Lchild;
		B->Lchild = C->Rchild;
		C->Lchild = A;
		C->Rchild = B;
		if(key < C->key){
			A->bt = 0;
			B->bt = -1;
			C->bt = 0;
		} 
		else if(key > C->key){
			A->bt = 1;
			B->bt = 0;
			C->bt = 0;
		}
		else{
			A->bt = 0;
			B->bt = 0;
			C->bt = 0;
		}
		if(FA == NULL)			(*T) = C;
		else if(A == FA->Lchild) FA->Lchild = C;
		else					FA->Rchild = C;
	}
	return;
}

void Crt_AVLTree(AVLTree *T,int N){
	int key;
	for(int i=0; i<N; i++){
		cin>>key;
		Ins_AVLTree(T,key);
	}
	return;
}

int main(){
	int N;
	AVLTree T = NULL;
	cin>>N;
	Crt_AVLTree(&T,N);
	cout<<T->key<<endl;
	return 0;
}

发表于 2017-02-26 18:05:17 回复(0)

周为

  /*由于在插入结点时使用递归查找空结点的方式，故可在递归返回时进行结构调整判断并调整结构，将插入结点后的树调整平衡，需要实现的功能有两个：一是结构调整判断，二是结构调整过程（判断LL，LR，RL，RR四种情况并实现四种调整） 
  要注意的是每次结构调整完都要及时更新高度信息（包括插入和旋转）*/

  #include<cstdio> 

  #include<algorithm> 

  using namespace std; 
     
  struct node{ 

      int data; 

      node* lchild; 

      node* rchild; 

      int height; 

      node(int x):data(x),lchild(NULL),rchild(NULL),height(1){} 

  }; 

  int n; 

  int seq[20]; 

  //**************结构调整判断条件************** 

  int getHeight(node* root){ 

      if(root==NULL) 

          return 0; 

      return root->height; 

  } 

  void updateHeight(node* root){ 

      root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1; 

      return; 

  } 

  int getFactor(node* root){ 

      return getHeight(root->lchild)-getHeight(root->rchild); 

  } 

  //**************结构调整执行过程************** 

  //1、指针调整 2、更新高度信息 3、选择根指针 

  void LL(node* &root){ 

      node* tmp=root->lchild; 

      root->lchild=tmp->rchild; 

      tmp->rchild=root; 

      updateHeight(root); 
      updateHeight(tmp);//高度信息更新顺序一定是tmp最后

      root=tmp;   

  } 

  void LR(node* &root){ 

      node* tmp1=root->lchild; 

      node* tmp2=tmp1->rchild; 

      tmp1->rchild=tmp2->lchild; 

      root->lchild=tmp2->rchild; 

      tmp2->lchild=tmp1; 

      tmp2->rchild=root; 

      updateHeight(root); 

      updateHeight(tmp1); 
      updateHeight(tmp2);//高度信息更新顺序一定是tmp2最后

      root=tmp2;   

  } 

  void RL(node* &root){ 

      node* tmp1=root->rchild; 

      node* tmp2=tmp1->lchild; 

      tmp1->lchild=tmp2->rchild; 

      root->rchild=tmp2->lchild; 

      tmp2->rchild=tmp1; 

      tmp2->lchild=root; 

      updateHeight(root); 

      updateHeight(tmp1); 
      updateHeight(tmp2);//高度信息更新顺序一定是tmp2最后

      root=tmp2;   

  } 

  void RR(node* &root){ 

      node* tmp=root->rchild; 

      root->rchild=tmp->lchild; 

      tmp->lchild=root; 

      updateHeight(root); 
      updateHeight(tmp);//高度信息更新顺序一定是tmp最后

      root=tmp;   

  } 

  //**************结构调整判断过程************** 

  void adjust(node* &root){ 

      if(root==NULL) 

          return; 

      int factor=getFactor(root); 

      if(factor==2){ 

          int lfactor=getFactor(root->lchild); 

          if(lfactor==1) 

              LL(root); 

          else if(lfactor==-1) 

              LR(root); 

          else adjust(root->lchild); 

      } 

      else if(factor==-2){ 

          int rfactor=getFactor(root->rchild); 

          if(rfactor==1) 

              RL(root);        

          else if(rfactor==-1) 

              RR(root); 

          else adjust(root->rchild); 

      } 

      else{ 

          adjust(root->lchild); 

          adjust(root->rchild); 

      } 

      return; 

  } 

  //递归查找插入结点，故返回时调整结构 

  void insert(node* &root,int x){ 

      if(root==NULL){ 

          root=new node(x); 

          return; 

      } 

      if(root->data>x){ 

          insert(root->lchild,x); 

          updateHeight(root); 

          adjust(root);            //插入返回后调整结构 

          updateHeight(root);//注意插入和调整后都要更新高度信息 

      } 

      else{ 

          insert(root->rchild,x); 

          updateHeight(root); 

          adjust(root); 

          updateHeight(root); 

      } 

  } 

  int main(){ 

      node* root=NULL; 

      scanf("%d",&n); 

      for(int i=0;i<n;i++){ 

          scanf("%d",&seq[i]); 

          insert(root,seq[i]); 

      } 

      printf("%d",root->data); 

      return 0; 

  }

发表于 2017-02-25 12:06:55 回复(0)

牛客559967号

#include<iostream>
#include<algorithm>
using namespace std;
template<typename value_t>
struct node
{
	value_t value;
	int height;
	node* left;
	node* right;
	node():height(0),left(nullptr),right(nullptr){}
};
template<typename value_t, typename comparator = std::less<value_t> >
struct tree
{
	using node_t = node<value_t>;
	comparator cmp_;
	tree():cmp_(),root(nullptr){}
	void insert(value_t v)
	{
		root = insert_(v, root);
	}
	value_t top()
	{
		return root->value;
	}
private:
	node_t* root;
	int height(node_t* root)
	{
		if(root==nullptr)
		{
			return -1;
		}else
		{
			return root->height;
		}
	}
	node_t* insert_(value_t v,node_t* root)
	{
		if(root==nullptr)
		{
			root = new node_t();
			root->value = v;
			return root;
		}
		else if(v<root->value)
		{
			root->left = insert_(v, root->left);
			if(height(root->left)-height(root->right)==2)
			{
				if(v<root->left->value)
				{
					root=singleRotateWithLeft(root);
				}else
				{
					root=doubleRotateWithLeft(root);
				}
			}
		}
		else if(v>root->value)
		{
			root->right = insert_(v, root->right);
			if (height(root->right) - height(root->left) == 2)
			{
				if (v > root->right->value)
				{
					root=singleRotateWithRight(root);
				}
				else
				{
					root=doubleRotateWithRight(root);
				}
			}
		}
		root->height = max(height(root->left), height(root->right))+1;
		return root;
	}
	node_t* singleRotateWithLeft(node_t* k2)
	{
		auto k1 = k2->left;
		k2->left = k1->right;
		k1->right = k2;

		k2->height = max(height(k2->left), height(k2->right))+1;
		k1->height = max(height(k1->left), k2->height) + 1;
		return k1;
	}
	node_t* singleRotateWithRight(node_t* k2)
	{
		auto k1 = k2->right;
		k2->right = k1->left;
		k1->left = k2;
		k2->height = max(height(k2->left), height(k2->right)) + 1;
		k1->height = max(height(k1->right), k2->height) + 1;
		return k1;
	}
	node_t* doubleRotateWithLeft(node_t* k2)
	{
		auto k1 = k2->left;
		auto k3 = k1->right;
		k2->left = k3->right;
		k1->right = k3->left;
		k3->right = k2;
		k3->left = k1;
		k2->height = max(height(k2->left), height(k2->right)) + 1;
		k1->height = max(height(k1->left), height(k1->right)) + 1;
		k3->height = max(k1->height, k2->height) + 1;
		return k3;
	}
	node_t* doubleRotateWithRight(node_t* k2)
	{
		auto k1 = k2->right;
		auto k3 = k1->left;
		k2->right = k3->left;
		k1->left = k3->right;
		k3->left = k2;
		k3->right = k1;
		k2->height = max(height(k2->left), height(k2->right)) + 1;
		k1->height = max(height(k1->left), height(k1->right)) + 1;
		k3->height = max(k1->height, k3->height) + 1;
		return k3;
	}
};
int main()
{
	tree<int> t;
	int n;
	std::cin >> n;
	for (int i = 0; i < n;i++)
	{
		int num;
		std::cin >> num;
		t.insert(num);
	}
	std::cout << t.top();
	return 0;
}

发表于 2016-09-04 19:31:56 回复(1)

//

#include<iostream>
using namespace std;
struct Tree {
 int val;
 int height;
 struct Tree *left;
 struct Tree *right;
};
Tree* SingleRotateWithLeft( Tree* k2 );
Tree* SingleRotateWithRight( Tree* k2);
Tree* DoubleRotateWithLeft( Tree* k2 );
Tree* DoubleRotateWithRight( Tree* k2 );
Tree* AVLInsert( Tree* bsearchtree, int num );
int HTree( Tree* bsearchtree );
int Max( int h1, int h2 );
int main  ()
{
 Tree* bsearchtree = NULL;
 int N, i, num;
 cin >> N;
 for( i=0; i<N; ++i )
 {
  cin >> num;
  bsearchtree = AVLInsert(bsearchtree,num);
 } 
 cout << bsearchtree->val <<endl;
 return 0;
}
Tree* AVLInsert( Tree* bsearchtree, int num )
{
 if( bsearchtree == NULL )
 {
  bsearchtree = (Tree*)malloc(sizeof(Tree));
  bsearchtree->val = num;
  bsearchtree->height = 0;
  bsearchtree->left = NULL;
  bsearchtree->right = NULL;
 }
 else if ( num < bsearchtree->val )
 {
  bsearchtree->left = AVLInsert( bsearchtree->left, num );
  if(HTree(bsearchtree->left)-HTree(bsearchtree->right)==2)
   if( num < bsearchtree->left->val )
    bsearchtree = SingleRotateWithLeft(bsearchtree);
   else
    bsearchtree = DoubleRotateWithLeft(bsearchtree);
 }
 else if ( num > bsearchtree->val )
 {
  bsearchtree->right = AVLInsert( bsearchtree->right, num );
  if(HTree(bsearchtree->right)-HTree(bsearchtree->left)==2)
   if( num > bsearchtree->right->val )
    bsearchtree = SingleRotateWithRight(bsearchtree);
   else
    bsearchtree = DoubleRotateWithRight(bsearchtree);
 }
 bsearchtree->height = Max( HTree(bsearchtree->left), HTree(bsearchtree->right) ) + 1;
 return bsearchtree;
}
int HTree( Tree* bsearchtree )
{
 if( bsearchtree == NULL )
  return -1;
 else
  return bsearchtree->height;
}
Tree* SingleRotateWithLeft( Tree* k2 )
{
 Tree* k1;
 k1 = k2->left;
 k2->left = k1->right;
 k1->right = k2;
 k2->height = Max( HTree(k2->left), HTree(k2->right) ) + 1;
 k1->height = Max( HTree(k1->left), k2->height ) + 1;
 return k1;  //return the ROOT
}
Tree* SingleRotateWithRight( Tree* k2)
{
 Tree* k1;
 k1 = k2->right;
 k2->right = k1->left;
 k1->left = k2;
 k2->height = Max( HTree(k2->left), HTree(k2->right)) + 1;
 k1->height = Max( k2->height, HTree(k1->right)) + 1;
 return k1; //return the ROOT
}
Tree* DoubleRotateWithLeft( Tree* k2 )        //（对左子树作双旋转）对根的左子树先进行单右旋转，在对根进行左单旋转
{
 k2->left = SingleRotateWithRight(k2->left);      //先对左子树进行右单旋转
 return SingleRotateWithLeft(k2); //return the ROOT   //再对根进行左单旋转
}
Tree* DoubleRotateWithRight( Tree* k2 )
{
 k2->right = SingleRotateWithLeft(k2->right);
 return SingleRotateWithRight(k2); //return the ROOT
}
int Max( int h1, int h2 )
{
 if( h1 > h2 )
  return h1;
 else
  return h2;
}

发表于 2015-06-13 13:56:57 回复(0)

Root of AVL Tree (25)

输入描述:

输出描述:

输入

输出

ac_code

C++手写AVL树全面详解

AVL树简介

AVL树的相关概念

AVL树的实现详解

1. 结点结构

2. AVL树的抽象数据结构（ADT）

3. AVL树高度相关操作

4. 得到子树中最大/最小结点

5. 得到结点的前驱和后继

6. AVL树失衡的调整

7. 插入新结点

8. 删除结点

9. 查找元素

10. 遍历二叉树

11. AVL树的销毁

12. 迭代器的设计

完整代码

AVLTree.h

AVLTree.cpp

测试

测试代码

测试总结

解题测试

问题信息

热门推荐

通过挑战的用户

相关试题