avl树c++

AVL树是一种自平衡二叉搜索树，它的每个节点存储一个键值对，且每个节点的左子树和右子树的高度差不超过1。这种平衡特性使得AVL树在查找、插入和删除操作方面都有很好的性能表现。

下面是一个简单的AVL树的C++实现：

#include <iostream>

using namespace std;

// AVL树节点
struct Node {
    int key;
    int height;
    Node *left;
    Node *right;

    Node(int k) : key(k), height(1), left(NULL), right(NULL) {}
};

// 获取节点高度
int height(Node *node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 获取节点平衡因子
int balanceFactor(Node *node) {
    if (node == NULL) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

// 更新节点高度
void updateHeight(Node *node) {
    node->height = max(height(node->left), height(node->right)) + 1;
}

// 右旋操作
Node* rightRotate(Node *node) {
    Node *leftChild = node->left;
    Node *rightChild = leftChild->right;
    leftChild->right = node;
    node->left = rightChild;
    updateHeight(node);
    updateHeight(leftChild);
    return leftChild;
}

// 左旋操作
Node* leftRotate(Node *node) {
    Node *rightChild = node->right;
    Node *leftChild = rightChild->left;
    rightChild->left = node;
    node->right = leftChild;
    updateHeight(node);
    updateHeight(rightChild);
    return rightChild;
}

// 插入节点
Node* insert(Node *node, int key) {
    if (node == NULL) {
        return new Node(key);
    }
    if (key < node->key) {
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        node->right = insert(node->right, key);
    } else {
        return node;
    }
    updateHeight(node);
    int bf = balanceFactor(node);
    if (bf > 1) {
        if (balanceFactor(node->left) >= 0) {
            return rightRotate(node);
        } else {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
    } else if (bf < -1) {
        if (balanceFactor(node->right) <= 0) {
            return leftRotate(node);
        } else {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
    }
    return node;
}

// 中序遍历AVL树
void inOrder(Node *node) {
    if (node == NULL) {
        return;
    }
    inOrder(node->left);
    cout << node->key << " ";
    inOrder(node->right);
}

int main() {
    Node *root = NULL;

    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    inOrder(root);
    cout << endl;

    return 0;
}

在上面的实现中，我们使用了递归插入节点，并在插入节点后更新了节点的高度和平衡因子。当节点的平衡因子大于1或小于-1时，我们进行相应的旋转操作来保持树的平衡。最后，我们在main函数中插入一些节点，并进行中序遍历来检查树是否正确构建。