AVL Tree (C++版)

一、概念

① AVL tree ∈ BST;

②任意一个节点 需满足abs(childL.heiht - childR.height) <= 1;

二、实现

①avl.h

#include
using namespace std;


struct Node
{
	Node* childL;
	Node* childR;
	int key;
	int val;
	int h; //节点高度
    NodeType(int k, int v) :childL(nullptr), childR(nullptr), key(k), val(v), h(1) {}
}


class AVL
{
public:
    AVL();
    ~AVL(); //析构时，释放节点空间 
    void Add(int key, int val); //添加一个元素
    void Del(int key); //删除一个元素
    Node* find(int key); //查找一个元素
    void Size(); //查询元素数
    void IsEmpty(); //AVL 是否空
private:
	void RotateL(Node* &node); // 左旋
	void RotateR(Node* &node); // 右旋
private:
    int size;
    Node *root; //AVL tree的根节点
}

②avl.c

#include"avl.h"



AVL::AVL()
{
	root = nullptr;
	size = 0;
}  
  

AVL::~AVL()
{

    if(!root) return;
    stack s;
    s.push(root);
    Node *cur = nullptr;
    while(!s.empty()) {
        cur = s.top();         
        if (cur->childL) {
            s.push(cur->childL); 
            cur->childL = nullptr;
        } else if (cur->childR) {
            s.push(cur->childR); 
            cur->childR = nullptr;
        } else {
            s.pop(); 
            delete cur;
        }
    }
}