浅析AVL树–AVL树的C++实现

AVL树的C++实现

基于前两篇博文:

浅析AVL树–AVL树的概念及单旋转

浅析AVL树–AVL树的双旋转

可以写出AVL的C++实现如下:
首先是AVL树的定义:
File avltree.h

class AVLTree {
public:
    struct node;
    typedef struct node* NodePointer;
    AVLTree(int d);
    void init(int d);
    //LL单旋转
    NodePointer singleRotateLeft(NodePointer p);
    //RR单旋转
    NodePointer singleRotateRight(NodePointer p);
    //LR双旋转
    NodePointer doubleRotateLeft(NodePointer p);
    //RL双旋转
    NodePointer doubleRotateRight(NodePointer p);
    //插入值为data的新结点
    NodePointer insert(int data);
    //在给定结点p插入值为data的新结点
    NodePointer insert(NodePointer p,int data);
    //二叉树结点寻找
    NodePointer& find(int data);
    //打印出当前AVL树
    void print();
    //取得给定AVL树结点高度
    int height(NodePointer p);
    //取得整棵AVL树高度
    int height();
    void printDetail();
private:
    void printDetail(NodePointer p,NodePointer parent);
    NodePointer headNode;
    //定义AVL结点,注意每个结点有一个height域表示当前结点高度,方便高度计算与查询
    struct node {
        int data;
        struct node* left, * right;
        int height;
    };
};

然后是AVL树操作的具体实现:
File avltree.cpp

#include "avltree.h"
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdexcept>
AVLTree::AVLTree(int d):headNode((NodePointer)malloc(sizeof(struct node)))
{
    init(d);
}
void AVLTree::init(int d)
{
    memset(headNode, 0, sizeof(struct node));
    headNode->data = d;
}
//LL单旋转
AVLTree::NodePointer AVLTree::singleRotateLeft(NodePointer p)
{

    NodePointer q = p->left; //备份当前结点指针的左子树指针
    p->left = q->right; //将备份指针指向的结点的右子树指针赋给当前结点的左指针
    q->right = p;//将当前结点指针赋给备份指针的右指针
    //更新左右子树的高度信息
    p->height=(std::max(height(p->left), height(p->right)) + 1);
    q->height = (std::max(height(q->left), height(q->right)) + 1);
    //返回新的结点指针为备份的指针
    return q;
}
//RR单旋转
AVLTree::NodePointer AVLTree::singleRotateRight(NodePointer p)
{
    NodePointer q = p->right;//备份当前结点指针的右子树指针
    p->right = q->left;//将备份指针指向的结点的左子树指针赋给当前结点的右指针
    q->left = p;//将当前结点指针赋给备份指针的左指针
    //更新左右子树的高度信息
    p->height = (std::max(height(p->left), height(p->right)) + 1);
    q->height = (std::max(height(q->left), height(q->right)) + 1);
    //返回新的结点指针为备份的指针
    return q;
}
//LR双旋转
AVLTree::NodePointer AVLTree::doubleRotateLeft(NodePointer p)
{
    p->left = singleRotateRight(p->left);//对当前结点的左儿子进行RR单旋转
    p = singleRotateLeft(p);//对当前结点进行LL单旋转
    return p;//返回旋转后结果
}
//RL双旋转
AVLTree::NodePointer AVLTree::doubleRotateRight(NodePointer p)
{
    p->right = singleRotateLeft(p->right);//对当前结点的右儿子进行LL单旋转
    p = singleRotateRight(p);//对当前结点进行RR单旋转
    return p;//返回旋转后结果
}

AVLTree::NodePointer AVLTree::insert(int data)
{
    //调用函数,从根节点开始插入
    headNode = insert(headNode, data);
    return headNode;
}

AVLTree::NodePointer AVLTree::insert(NodePointer p, int data)
{
//p == NULL 说明当前结点指针指向需要插入结点的位置,直接生成新结点,并返回
    if (p == NULL)
    {
        p = (NodePointer)malloc(sizeof(struct node));
        if (!p)
            throw std::runtime_error("Memory out of space");
        else {
            p->left = p->right = 0;
            p->height = 0;
            p->data = data;
            return p;
        }

    }//如果待插入的结点应该插入到左儿子上
    else if (data < p->data)
    {
        p->left=insert(p->left, data);//执行插入
        if (height(p->left) - height(p->right) == 2)//如果插入后该节点失衡,注意,平衡时左右子树高度差1,插入一个结点引起的失衡左右子树高度必定差2
        {
            if (data < p->left->data)//如果待插入结点应该插入到左儿子的左子树(LL),执行LL单旋转
                p = singleRotateLeft(p);
            else
            //否则待插入结点必定会被插入到左儿子的右子树(LR),执行LR双旋转
                p = doubleRotateLeft(p);
        }
    }
    //如果待插入的结点应该插入到右儿子上
    else if (data > p->data)
    {
        p->right = insert(p->right, data);//插入哇
        if (height(p->right) - height(p->left) == 2)
        {
        //如果待插入结点应该插入到右儿子的右子树(RR),执行RR单旋转
            if (data > p->right->data)
                p = singleRotateRight(p);
            else
            //否则待插入结点必定会被插入到右儿子的左子树(RL),执行RL双旋转
                p = doubleRotateRight(p);
        }
    }
    p->height = std::max(height(p->left), height(p->right)) + 1;
    return p;
}

//很普通的查找函数,,,,,,,,,,,
AVLTree::NodePointer& AVLTree::find(int data)
{
    NodePointer &p = headNode;
    while (p)
    {
        if (data > p->data)
            p = p->right;
        else if (data < p->data)
            p = p->left;
        else
            break;
    }
    return p;
}
//以下是我写的平淡无奇的辅助函数,,,不用看了
//,,,,,,,,,,,,,,,,,,,我写的很烂的,,,,,,
void AVLTree::print()
{
    using namespace std;
    queue<NodePointer> q;
    q.push(headNode);
    while (!q.empty()) {
        NodePointer p = q.front();
        q.pop();
        cout << p->data << " ";
        if (p->left)
            q.push(p->left);
        if (p->right)
            q.push(p->right);
    }
    cout << endl;
}
//说你呢,,,,你还看???
int AVLTree::height(NodePointer p)
{
    if (!p)
        return -1;
    else
        return p->height;
}

int AVLTree::height()
{
    return height(headNode);
}
//呜呜放我一马吧,,,,真的写的很烂,,,,,
void AVLTree::printDetail()
{
    std::cout << "=======INFO=======" << std::endl;
    std::cout << "Height: " << height() << "\nDetail:\n";
    printDetail(headNode, nullptr);
}

void AVLTree::printDetail(NodePointer p, NodePointer parent)
{
    if (!p)
        return;
    if (parent && parent->left == p)
        std::cout << parent->data << "-L->" << p->data << std::endl;
    else if (parent && parent->right == p)
        std::cout << parent->data << "-R->" << p->data << std::endl;
    else if(parent == nullptr)
        std::cout << "[ROOT]:" << p->data << std::endl;
    printDetail(p->left, p);
    printDetail(p->right, p);
}
//好吧你赢了QAQ,你看到了最后wwwwwww

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据