BST和AVL

二叉搜索树binary search tree 和 平衡二叉搜索树 AVL

#include <iostream>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    int height;
    TreeNode(int value):val(value),left(nullptr),right(nullptr){}
};

class BST{
private:
    TreeNode* root;

    TreeNode* insert(TreeNode* node,int value){
        if(!node){
            return new TreeNode(value);
        }
        if(value<node->val){
            node->left=insert(node->left,value);
        }else if(value>node->val){
            node->right=insert(node->right,value);
        }
        return node;
    }

    TreeNode* search(TreeNode* node, int value){
        if(!node||node->val==value){
            return node;
        }
        if(value<node->val){
            return search(node->left,value);
        }else{
            return search(node->right,value);
        }
    }

    TreeNode* deleteNode(TreeNode* node,int value){
        if(!node) return nullptr;
        if(value<node->val)
            node->left=deleteNode(node->left,value);
        else if(value>node->val)
            node->right=deleteNode(node->right,value);
        else{//找到要删除的节点
            if(!node->left)
                return node->right;
            else if(!node->right)
                return node->left;
            else{
                TreeNode* minNode=node->right;
                while(minNode->left){
                    minNode=minNode->left;
                }
                node->val=minNode->val;
                node->right=deleteNode(node->right,minNode->val);
            }
        } 
        return node;   
    }

    void inorder(TreeNode* node){
        if(node){
            inorder(node->left);
            cout<<node->val<<" ";
            inorder(node->right);
        }
    }

public:
BST():root(nullptr){}

    void insert(int value){
        root=insert(root,value);
    }

    TreeNode* search(int value){
        return search(root,value);
    }

    void deleteNode(int value){
        root=deleteNode(root,value);
    }

    void inorder(){
        inorder(root);
    }
};


平衡二叉搜索树AVL

class AVLTree{
private:
     // 获取节点高度
    int getHeight(TreeNode* node) {
        return node ? node->height : 0;
    }

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

    // 获取平衡因子
    int getBalance(TreeNode* node) {
        return node ? getHeight(node->left) - getHeight(node->right) : 0;
    }

    //右旋
    TreeNode* rightRotate(TreeNode* y){
        TreeNode* x=y->left;
        TreeNode* T2=x->right;

        x->right=y;
        y->left=T2;
        return x;
    }
     // 左旋
    TreeNode* leftRotate(TreeNode* x) {
        TreeNode* y = x->right;
        TreeNode* T2 = y->left;
        // 旋转
        y->left = x;
        x->right = T2;

        return y; // 新的根节点
    }

    // 插入节点
    TreeNode* insert(TreeNode* node, int value) {
        if (!node) return new TreeNode(value);

        if (value < node->val) {
            node->left = insert(node->left, value);
        } else if (value > node->val) {
            node->right = insert(node->right, value);
        } else {
            return node; // 不允许重复值
        }
        // 检查平衡
        int balance = getBalance(node);   
        // LL情况
        if (balance > 1 && value < node->left->val) {
            return rightRotate(node);
        }
        // RR情况
        if (balance < -1 && value > node->right->val) {
            return leftRotate(node);
        }
        // LR情况 左旋左孩子，然后根节点右旋
        if (balance > 1 && value > node->left->val) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
        // RL情况 右旋右孩子，然后根节点左旋
        if (balance < -1 && value < node->right->val) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node; // 返回未改变的节点指针
    }
};````