AVL树 |
您所在的位置：网站首页 › 旋的右边组字是什么 › AVL树 |
AVL树
|
本篇文章主要介绍AVL树的四种旋转方法。 首先，右单旋： 插入节点位于根节点的左子节点的左子树。 左单旋： 插入节点位于根节点的右子节点的右子树。 左右双旋： 插入节点位于根节点的左子节点的右子树。 右左双旋： 插入节点位于根节点的右子节点的左子树。 接下来是AVL树的代码： #pragma once #include using namespace std; template struct AVLTreeNode { AVLTreeNode(const K& key,const V& value) :_left(NULL) , _right(NULL) ,_parent(NULL) , _key(key) , _value(value) , _bf(0) {} AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; K _key; V _value; int _bf; }; template class AVLTree { typedef AVLTreeNode Node; public: AVLTree() :_root(NULL) {} bool Insert(const K& key,const V& value) { if (_root == NULL) { _root = new Node(key, value); return true; } //找插入位置 Node* cur = _root; Node* parent = NULL; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else return false; } //插入 cur = new Node(key, value); if (key < parent->_key) parent->_left = cur; else parent->_right = cur; cur->_parent = parent; //更新双亲的平衡因子 while (parent) { if (parent->_left == cur) parent->_bf--; else parent->_bf++; if (parent->_bf == 0) break; else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = cur->_parent; } else { if (parent->_bf == 2) { if (cur->_bf == 1) _RotateL(parent); else _RotateRL(parent); } else { if (cur->_bf == -1) _RotateR(parent); else _RotateLR(parent); } break; } } return true; } void InOreder() { return _InOrder(_root); } bool IsBalance() { return _IsBalance(_root); } private: bool _IsBalance(Node* root) { if (_root == NULL) return true; int LeftHight = _Hight(_root->_left); int RightHight = _Hight(_root->_right); if (abs(LeftHight - RightHight) >= 2) return false; return _IsBalance(_root->_left) && _IsBalance(_root->_right); } int _Hight(Node* _root) { if (_root == NULL) return 0; int LeftHight = _Hight(_root->_left)+1; int RightHight = _Hight(_root->_right)+1; return LeftHight > RightHight ? LeftHight+1 : RightHight+1; } void _RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; //处理节点 parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; Node* pparent = parent->_parent; subR->_parent = pparent; parent->_parent = subR; if (parent == _root) _root = subR; else { if (pparent->_left == parent) pparent->_left = subR; else pparent->_right = subR; } parent->_bf = subR->_bf = 0; } void _RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; Node* pparent = parent->_parent; subL->_parent = pparent; parent->_parent = subL; if (pparent == NULL) _root = subL; else { if (parent = pparent->_left) pparent->_left = subL; else pparent->_right = subL; } parent->_bf = subL->_bf = 0; } void _RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; _RotateR(subR); _RotateL(parent); if (bf == 1) parent->_bf = -1; else if (bf == -1) subR->_bf = 1; } void _RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; _RotateL(subL); _RotateR(parent); if (bf == 1) subL->_bf = -1; if (bf == -1) parent->_bf = 1; } void _InOrder(Node* _root) { if (_root) { _InOrder(_root->_left); cout |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |