#pragma once #include <iostream> #include <algorithm> template <typename T> class AVLTreeNode { public: T key; int height; AVLTreeNode* left; AVLTreeNode* right; AVLTreeNode(T value, AVLTreeNode *l, AVLTreeNode* r) : key(value), height(0), left(l), right(r) {} }; template <typename T> class AVLTree { public: typedef AVLTreeNode<T> Node; typedef AVLTreeNode<T>* Node_pointer; public: AVLTree() : rootTree(nullptr) { } ~AVLTree() { clear(); } //查找 //前序遍历 void preOrder() { preOrder(rootTree); } //中序遍历 void inOrder() { inOrder(rootTree); } //后序遍历 void postOrder() { postOrder(rootTree); } //最大值 T max() { Node* x = max(rootTree); if (x == nullptr) return (T)nullptr; return x->key; } //最小值 T min() { Node* x = min(rootTree); if (x == nullptr) return (T)nullptr; return x->key; } //修改 //插入 void insert(T value) { insert(rootTree, value); } //删除 void remove(T value); //清除 void clear(); //获取高度 int height(Node*); private: //LL旋转 右旋转 Node* LL_rotation(Node*); //RR旋转 左旋转 Node* RR_rotation(Node*); //LR旋转 RR ==> LL Node* LR_rotation(Node*); //RL旋转 LL ==> RR Node* RL_rotation(Node*); // Node* insert(Node_pointer&, T); void preOrder(Node *tree); void inOrder(Node *tree); void postOrder(Node *tree); Node * remove(Node_pointer& tree, Node *z); void destroy(Node_pointer& tree); Node* max(Node *tree); Node* min(Node *tree); Node* search(Node* tree, T key); private: Node* rootTree; }; //获取高度 template <typename T> int AVLTree<T>::height(Node* node) { if (node == nullptr) return 0; return node->height; } //LL旋转 template <typename T> typename AVLTree<T>::Node* AVLTree<T>::LL_rotation(Node* k2) { Node* k1; k1 = k2->left; k2->left = k1->right; k1->right = k2; k1->height = std::max(height(k1->left), height(k1->right)) + 1; k2->height = std::max(height(k2->left), height(k2->right)) + 1; return k1; } //RR旋转 template <typename T> typename AVLTree<T>::Node* AVLTree<T>::RR_rotation(Node* k1) { Node* k2; k2 = k1->right; k1->right = k2->left; k2->left = k1; k1->height = std::max(height(k1->left), height(k1->right)) + 1; k2->height = std::max(height(k2->left), height(k2->right)) + 1; return k2; } //LR旋转 RR ==> LL template <typename T> typename AVLTree<T>::Node* AVLTree<T>::LR_rotation(Node* k3) { k3->left = RR_rotation(k3->left); return LL_rotation(k3); } //RL旋转 LL ==> RR template <typename T> typename AVLTree<T>::Node* AVLTree<T>::RL_rotation(Node* k1) { k1->right = LL_rotation(k1->right); return RR_rotation(k1); } template <typename T> typename AVLTree<T>::Node* AVLTree<T>::insert(Node_pointer &tree, T value) { //1. tree is nullptr if (tree == nullptr) { tree = new Node(value, nullptr, nullptr); if (tree == nullptr) { std::cout << "insert error: new node failed! " << std::endl; return nullptr; } } //插到左边 else if (value < tree->key) { tree->left = insert(tree->left, value); //插入节点后,若失去平衡,则需要调整 if (height(tree->left) - height(tree->right) == 2) { if (value < tree->left->key) { tree = LL_rotation(tree); } else { tree = LR_rotation(tree); } } } //插到右边 else if (value > tree->key) { tree->right = insert(tree->right, value); //插入节点后,若失去平衡,则需要调整 if (height(tree->right) - height(tree->left) == 2) { if (value > tree->right->key) { tree = RR_rotation(tree); } else { tree = RL_rotation(tree); } } } else { std::cout << "insert error: same key! " << std::endl; } //更新高度 tree->height = std::max(height(tree->left), height(tree->right)) + 1; return tree; } template <typename T> void AVLTree<T>::preOrder(Node *tree) { if (tree == nullptr) return; std::cout << tree->key << " "; preOrder(tree->left); preOrder(tree->right); } template <typename T> void AVLTree<T>::inOrder(Node *tree) { if (!tree) return; inOrder(tree->left); std::cout << tree->key << " "; inOrder(tree->right); } template <typename T> void AVLTree<T>::postOrder(Node *tree) { if (!tree) return; postOrder(tree->left); postOrder(tree->right); std::cout << tree->key << " "; } //清除 template <typename T> void AVLTree<T>::clear() { destroy(rootTree); } template <typename T> void AVLTree<T>::destroy(Node_pointer&tree) { if (tree == nullptr) return; if (tree->left) destroy(tree->left); if (tree->right) destroy(tree->right); delete tree; tree = nullptr; } template <typename T> typename AVLTree<T>::Node* AVLTree<T>::remove(Node_pointer& tree, Node* z) { if (tree == nullptr || z == nullptr) return nullptr; //左子节点 if (z->key < tree->key) { tree->left = remove(tree->left, z); //插入节点后,若失去平衡,则需要调整 if (height(tree->left) - height(tree->right) == 2) { if (z->key < tree->left->key) { tree = LL_rotation(tree); } else { tree = LR_rotation(tree); } } } //右子节点 else if(z->key > tree->key){ tree->right = remove(tree->right, z); //插入节点后,若失去平衡,则需要调整 if (height(tree->right) - height(tree->left) == 2) { if (z->key > tree->right->key) { tree = RR_rotation(tree); } else { tree = RL_rotation(tree); } } } //当前节点 else { if ((tree->left != nullptr) && (tree->right != nullptr)) { if (height(tree->left) > height(tree->right)) { //找到左边的最大值,删除该节点 //并替换改节点的值 //此时AVL树还是平衡的 Node* maxNode = max(tree->left); tree->key = maxNode->key; tree->left = remove(tree->left, maxNode); } else { //找到右边的最小值,删除该节点 //并替换改节点的值 //此时AVL树还是平衡的 Node* minNode = min(tree->right); tree->key = minNode->key; tree->right = remove(tree->right, minNode); } } else { Node* tmp = tree; tree = (tree->left != nullptr) ? tree->left : tree->right; delete tree; } } return tree; } template <typename T> void AVLTree<T>::remove(T value) { Node* z; if ((z = search(rootTree, value)) != nullptr) { rootTree = remove(rootTree, z); } } template <typename T> typename AVLTree<T>::Node* AVLTree<T>::max(Node *tree) { if (!tree) return nullptr; Node* x = tree; while (x->right) { x = x->right; } return x; } template <typename T> typename AVLTree<T>::Node* AVLTree<T>::min(Node *tree) { if (!tree) return nullptr; Node* x = tree; while (x->left) { x = x->left; } return x; } template <typename T> typename AVLTree<T>::Node* AVLTree<T>::search(Node* tree, T key) { if (tree == nullptr) return nullptr; if (tree->key == key) return tree; if (key < tree->key) { return search(tree->left, key); } else { return search(tree->right, key); } }