C++数据结构--AVL树

一.什么是AVL树AVL树也叫二叉平衡搜索树就是在BST树的基础上加了平衡操作平衡的定义是任意节点的左右子树的高度差不超过1。其基本框架与BST树相同不过为了保证其平衡添加了节点的旋转操作templatetypename T class AVLTree { public: AVLTree() :root(nullptr) { } ~AVLTree(){} private: struct Node { Node(T dataT()) :m_data(data) ,left(nullptr) ,right(nullptr) ,height(1) { } T m_data; Node* left; Node* right; int height;//节点高度用于旋转操作 }; Node* root; }; //获取节点高度 int getHeight(Node* node) { return node nullptr ? 0 : node-height; }二.常见操作实现1.平衡操作1.右旋转操作如果添加一个元素后左孩子的左子树太高了那么需要进行右旋转如图。这里的节点node与节点child的孩子节点都发生了变化它们的高度需要进行更新。//右旋转操作 Node* rightRotate(Node* node) { Node* child node-left; node-left child-right; child-right node; node-height max(getHeight(node-left), getHeight(node-right)) 1; child-height max(getHeight(child-left), getHeight(child-right)) 1; return child; }2.左旋转操作如果添加一个元素后右孩子的右子树太高了那么需要进行左旋转如图这里的节点node与节点child的孩子节点都发生了变化它们的高度需要进行更新。//左旋转操作 Node* leftRotate(Node* node) { Node* child node-right; node-right child-left; child-left node; node-height max(getHeight(node-left), getHeight(node-right)) 1; child-height max(getHeight(child-left), getHeight(child-right)) 1; return child; }3左平衡操作如果添加一个元素后左孩子的右子树太高了那么需要进行左平衡如图//左平衡操作(左-右) Node* leftBalance(Node* node) { node-left leftRotate(node-left); return rightRotate(node); }4右平衡操作如果添加一个元素后右孩子的左子树太高了那么需要进行右平衡如图//右平衡操作(右-左) Node* rightBalance(Node* node) { node-right rightRotate(node-right); return leftRotate(node); }2.插入操作Node* insert(const T val,Node* node) { if (node nullptr) { return new Node(val); } if (node-m_data val) { return node; } else if (node-m_data val) { node-left insert(val, node-left); if ((getHeight(node-left) - getHeight(node-right))1) { if (getHeight(node-left-left) getHeight(node-left-right)) { node rightRotate(node); } else { node rightBalance(node); } } } else { node-right insert(val, node-right); if ((getHeight(node-right) - getHeight(node-left)) 1) { if (getHeight(node-right-right) getHeight(node-right-left)) { node leftRotate(node); } else { node leftBalance(node); } } } node-height max(getHeight(node-left), getHeight(node-right)) 1; return node; }3.删除操作Node* remove(const T val, Node* node) { if (node nullptr) { return nullptr; } if (node-m_data val) { node-left remove(val, node-left); if ((getHeight(node-right) - getHeight(node-left)) 1) { if (getHeight(node-right-right) getHeight(node-right-left)) { node leftRotate(node); } else { node leftBalance(node); } } } else if(node-m_data val) { node-right remove(val, node-right); if ((getHeight(node-left) - getHeight(node-right)) 1) { if (getHeight(node-left-left) getHeight(node-left-right)) { node rightRotate(node); } else { node rightBalance(node); } } } else { if (node-left ! nullptr node-right ! nullptr) { if (getHeight(node-left) getHeight(node-right)) { Node* pre node-left; while (pre-right ! nullptr) { pre pre-right; } node-m_data pre-m_data; node-left remove( pre-m_data, node-left); } else { Node* last node-right; while (last-left ! nullptr) { last last-left; } node-m_data last-m_data; node-right remove( last-m_data, node-right); } } else { if (node-left ! nullptr) { Node* left node-left; delete node; return left; } else if (node-right ! nullptr) { Node* right node-right; delete node; return right; } else { delete node; return nullptr; } } } node-height max(getHeight(node-left), getHeight(node-right)) 1; return node; }