参照物 一文读懂 AVL 树(4)

return rl_rotate(node);

return node;

}

void AVL::erase(int key)

{

header->left = erase_real(key, header->left);

}

完整代码

/**

*

* author : 刘毅（Limer）

* date : 2017-08-17

* mode : C++

*/

#include <iostream>

#include <algorithm>

using namespace std;

struct Node

{

int key;

int height;

Node * left;

Node * right;

Node(int key = 0)

{

this->key = key;

this->height = 1;

this->left = this->right = nullptr;

}

};

class AVL

{

private:

Node * header;

private:

Node * ll_rotate(Node * y);

Node * rr_rotate(Node * y);

Node * lr_rotate(Node * y);

Node * rl_rotate(Node * y);

void destroy(Node * node);

int get_height(Node * node);

int get_balance(Node * node);

Node * insert_real(int key, Node * node);

Node * find_real(int key, Node * node);

Node * erase_real(int key, Node * node);

void in_order(Node * node);

public:

AVL();

~AVL();

void insert(int key);

Node * find(int key);

void erase(int key);

void print();

};

Node * AVL::ll_rotate(Node * y)

{

Node * x = y->left;

y->left = x->right;

x->right = y;

y->height = max(get_height(y->left), get_height(y->right)) + 1;

x->height = max(get_height(x->left), get_height(x->right)) + 1;

return x;

}

Node * AVL::rr_rotate(Node * y)

{

Node * x = y->right;

y->right = x->left;

x->left = y;

y->height = max(get_height(y->left), get_height(y->right)) + 1;

x->height = max(get_height(x->left), get_height(x->right)) + 1;

return x;

}

Node * AVL::lr_rotate(Node * y)

{

Node * x = y->left;