AVL是平衡搜索二叉树,它的主要特点在于:(1)左子树和右子树的高度差绝对值<1,(2)树中的每个子树都是AVL树,(3)每个节点都有一个平衡因子(-1、0、1),平衡因子的大小等于右子树的高度减左子树的高度
下面就是一个AVL树:
其中,这个树满足左子树和右子树的高度差绝对值小于1,每个节点的平衡因子都满足条件。
下面是AVLTree中节点的结构:
template <class K, class V> struct AVLTreeNode { K _key; V _value; int _bf; //节点的平衡因子 AVLTreeNode<K, V>* _parent; //指向节点的父节点 AVLTreeNode<K, V>* _left; //指向节点的左孩子 AVLTreeNode<K, V>* _right; //指向节点的右孩子 AVLTreeNode(const K& key = K(), const V& value = V()) //构造节点 :_key(key) , _value(value) , _parent(NULL) , _left(NULL) , _right(NULL) , _bf(0) { } };
下面讨论一下AVLTree中插入节点的情况:
当插入一个节点时,如果这个节点的父节点的平衡因子不满足AVLTree的特点,这时就需要对AVLTree进行调整,直到满足AVLTree的条件。
(1)左单旋
(2)右单旋
(3)左右双旋
(4)右左双旋
针对上面的情况,下面是具体的程序实现:
#pragma once #include <assert.h> #include <math.h> //实现平衡搜索二叉树 //构造AVL树的节点(使用三叉链表) template <class K, class V> struct AVLTreeNode { K _key; V _value; int _bf; AVLTreeNode<K, V>* _parent; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode(const K& key = K(), const V& value = V()) //构造节点 :_key(key) , _value(value) , _parent(NULL) , _left(NULL) , _right(NULL) , _bf(0) { } }; template <class K, class V> class AVLTree { typedef AVLTreeNode<K, V> 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; Node* tmp = new Node(key, value); while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } if (parent->_key > key) { parent->_left = tmp; tmp->_parent = parent; } if (parent->_key < key) { parent->_right = tmp; tmp->_parent = parent; } //对树进行调整 cur = tmp; parent = cur->_parent; bool isRotate = false; while (parent) { if (parent->_left == cur) //插入左节点,父亲节点的平衡因子-1 { parent->_bf--; } if (parent->_right == cur) //插入右节点,父亲节点的平衡因子+1 { parent->_bf++; } if (parent->_bf == 0) //调整过程中,若碰到平衡因子为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 //=-2 { if (cur->_bf == -1) //右单旋 { _RotateR(parent); } else //左右单旋 { _RotateLR(parent); } } isRotate = true; } break; } if (isRotate) { if (parent->_parent == NULL) { _root = parent; return true; } } return true; } void InOrder() //后序遍历 { _InOrder(_root); cout << endl; } bool IsBalance() { if (_root == NULL) { cout << "root is null!" << endl; return false; } return _IsBalance(_root); } int Heigth() { int heigthTree = 0; Node* cur = _root; while (cur) { if (cur != NULL) { heigthTree++; } cur = cur->_left; } return _Heigth(_root, heigthTree, 0); } protected: int _Heigth(Node* root, int heigthTree, int countNum) { if (root == NULL) { if (countNum > heigthTree) { heigthTree = countNum; } return heigthTree; } _Heigth(root->_left, heigthTree, countNum++); _Heigth(root->_right, heigthTree, countNum++); } bool _IsBalance(Node* root) { int bf = root->_right->_bf - root->_right->_bf; if (bf == 0 || bf == 1 || bf == -1) { return true; } else { return false; } _IsBalance(root->_left); _IsBalance(root->_right); } void _RotateL(Node*& parent) //左单旋 { Node* SubR = parent->_right; //新建两个节点指针 Node* SubRL = SubR->_left; parent->_right = SubRL; //进行调整 if (SubRL) { SubRL->_parent = parent; } SubR->_left = parent; SubR->_parent = parent->_parent; parent->_parent = SubR; parent->_bf = SubR->_bf = 0; //更改引用计数 parent = SubR; } void _RotateR(Node*& parent) //右单旋 { Node* SubL = parent->_left; //新建两个节点指针 Node* SubLR = SubL->_right; parent->_left = SubLR; //进行调整 if (SubLR) { SubLR->_parent = parent; } SubL->_right = parent; SubL->_parent = parent->_parent; parent->_parent = SubL; parent->_bf = SubL->_bf = 0; parent = SubL; } void _RotateRL(Node*& parent) //右左单旋 { Node* pNode = parent; Node* subRNode = parent->_right; Node* subRLNode = subRNode->_left; int bf = subRLNode->_bf; _RotateR(parent->_right); _RotateL(parent); if (bf == -1) { subRNode->_bf = 0; pNode->_bf = -1; } else if (bf == 1) { subRNode->_bf = 1; pNode->_bf = 0; } else { subRNode->_bf = 0; pNode->_bf = 0; } subRNode->_bf = 0; } void _RotateLR(Node*& parent) //左右单旋 { Node* pNode = parent; Node* subLNode = parent->_left; Node* subLRNode = subLNode->_right; int bf = subLRNode->_bf; _RotateL(parent->_left); _RotateR(parent); if (bf == -1) { subLNode->_bf = 0; pNode->_bf = 1; } else if (bf == 1) { subLNode->_bf = -1; pNode->_bf = 0; } else { subLNode->_bf = 0; pNode->_bf = 0; } subLNode->_bf = 0; } void _InOrder(Node* root) { if (root == NULL) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } protected: Node* _root; }; void Test() { AVLTree<int, int> ht; /*ht.Insert(16, 1); ht.Insert(3, 1); ht.Insert(7, 1); ht.Insert(11, 1); ht.Insert(9, 1); ht.Insert(26, 1); ht.Insert(18, 1); ht.Insert(14, 1); ht.Insert(15, 1);*/ ht.Insert(4, 1); ht.Insert(2, 1); ht.Insert(6, 1); ht.Insert(1, 1); ht.Insert(3, 1); ht.Insert(5, 1); ht.Insert(15, 1); ht.Insert(7, 1); ht.Insert(16, 1); ht.Insert(14, 1); ht.InOrder(); cout<<ht.IsBalance()<<endl; cout << ht.Heigth() << endl; }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。