门户网站建设使用语言,自己做的网站怎么放到网上去,宁波网页设计制作,17网站一起做网店2018本篇讲全面的讲解 AVL 树的插入#xff0c;旋转以及验证 AVL 树的性能#xff08;本篇未实现删除代码#xff09;。至于为什么会有 AVL 树#xff0c;这是因为简单的二叉搜索树并不能直接的保证搜索的效率#xff0c;因为当我们在二叉搜索树中插入一段有序的序列的时候旋转以及验证 AVL 树的性能本篇未实现删除代码。至于为什么会有 AVL 树这是因为简单的二叉搜索树并不能直接的保证搜索的效率因为当我们在二叉搜索树中插入一段有序的序列的时候二叉搜索树就会退化为单枝树这个时候进行搜索的时候时间复杂度就变为了 O(n^2)如下 但是通过 AVL 树的旋转就可以很好的解决这个问题使树近似等于完全二叉树或者满二叉树。 AVL 树代码 先给出代码接着在下文中给出解释 #pragma once
#include iostream
#include assert.husing namespace std;template class K, class V
struct AVLTreeNode {AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _balanceFactor;AVLTreeNode(const pairK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _balanceFactor(0){}
};template class K, class V
class AVLTree {
public:typedef AVLTreeNodeK, V Node;Node* find(const K key) {Node* cur _root;while (cur) {if (cur-_kv.first key)cur cur-_right;else if (cur-_kv.first key)cur cur-_left;elsereturn cur;}return nullptr;}// 插入删除查找遍历bool insert(const pairK, V kv) {if (_root nullptr) {_root new Node(kv);return true;}// 开始查找Node* parent nullptr;Node* cur _root;while (cur) {if (cur-_kv.first kv.first)parent cur, cur cur-_right;else if (cur-_kv.first kv.first)parent cur, cur cur-_left;elsereturn false;}// cur nullptrcur new Node(kv);//if (parent-_left cur)// parent-_left cur;//else// parent-_right cur;if (parent-_kv.first kv.first)parent-_left cur;elseparent-_right cur;cur-_parent parent;// 需要更新平衡因子// 如果是在父亲的左边父亲的平衡因子减一、右边加一if (parent-_left cur)parent-_balanceFactor--;elseparent-_balanceFactor;// 查看爷爷结点是否需要更新while (parent) {if (parent-_balanceFactor 0) {break;}else if (parent-_balanceFactor 1 || parent-_balanceFactor -1) {if (parent _root)break;// 现在的parent就不可能等于nullparent parent-_parent;cur cur-_parent;if (parent-_left cur)parent-_balanceFactor--;elseparent-_balanceFactor;}else if(parent-_balanceFactor 2 || parent-_balanceFactor -2) {if (parent-_balanceFactor 2 cur-_balanceFactor 1)RotateLeft(parent);else if (parent-_balanceFactor -2 cur-_balanceFactor -1)RotateRight(parent);else if (parent-_balanceFactor -2 cur-_balanceFactor 1)RotateLeftRight(parent);else if (parent-_balanceFactor 2 cur-_balanceFactor -1)RotateRightLeft(parent);elseassert(false);break;}else {assert(false);}}return true;}void RotateRight(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;// 将左孩子的右节点链接到原父亲结点if (subLR) subLR-_parent parent;parent-_left subLR;Node* ppNode parent-_parent;// 将左孩子变为原父亲结点的父亲subL-_right parent;parent-_parent subL;// 将爷爷结点重新链接if (ppNode nullptr) {_root subL;_root-_parent nullptr;}else {if (ppNode-_left parent)ppNode-_left subL;elseppNode-_right subL;subL-_parent ppNode;}subL-_balanceFactor parent-_balanceFactor 0;}void RotateLeft(Node* parent) {Node* subR parent-_right;Node* subRL subR-_left;Node* ppNode parent-_parent;parent-_right subRL;if (subRL) subRL-_parent parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr) {_root subR;_root-_parent nullptr;}else {if (ppNode-_left parent)ppNode-_left subR;elseppNode-_right subR;subR-_parent ppNode;}subR-_balanceFactor parent-_balanceFactor 0;}void RotateRightLeft(Node* parent) {Node* subR parent-_right;Node* subRL subR-_left;int balanceFactor subRL-_balanceFactor;RotateRight(subR);RotateLeft(parent);// 更新平衡因子subRL-_balanceFactor 0;if (balanceFactor -1) {parent-_balanceFactor 0;subR-_balanceFactor 1;}else if (balanceFactor 1) {parent-_balanceFactor -1;subR-_balanceFactor 0;}else if (balanceFactor 0) {parent-_balanceFactor 0;subR-_balanceFactor 0;}else {assert(false);}}void RotateLeftRight(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;int balanceFactor subLR-_balanceFactor;// 先左旋后右旋RotateLeft(subL);RotateRight(parent);subLR-_balanceFactor 0;if (balanceFactor -1) {subL-_balanceFactor 0;parent-_balanceFactor 1;}else if (balanceFactor 1) {parent-_balanceFactor 0;subL-_balanceFactor -1;}else if (balanceFactor 0) {parent-_balanceFactor 0;subL-_balanceFactor 0;}else {assert(false);}}void InOrder() {_InOrder(_root);cout endl;}int height() {int h _height(_root);return h;}int size() {int s _size(_root);return s;}bool IsBalance() {return _IsBalance(_root);}private:bool _IsBalance(Node* root) {if (root nullptr)return true;int leftHeight _height(root-_left);int rightHeight _height(root-_right);if (abs(leftHeight - rightHeight) 2)return false;if (abs(root-_balanceFactor) 2)return false;return _IsBalance(root-_left) _IsBalance(root-_right);}int _height(Node* root) {if (root nullptr)return 0;int left _height(root-_left);int right _height(root-_right);int height max(left, right);return height 1;}int _size(Node* root) {if (root nullptr)return 0;return _size(root-_left) _size(root-_right) 1;}void _InOrder(Node* root) {if (root nullptr) return;_InOrder(root-_left);cout root-_kv.first root-_kv.second endl;_InOrder(root-_right);}
private:Node* _root nullptr;
};AVL 树的概念于抽象数据结构 一颗 AVL 树是空树或者是具有以下性质的二叉搜索树 1. 它的左右子树都是 AVL 树 2. 左右子树的高度之差平衡因子的绝对值不超过 1 左右子树的高度差不超过 1可以降低树的高度减少平均搜索长度。如下 关于 AVL 树的抽象数据结构我们首先需要抽象出 AVL 树节点的数据结构在 AVL 树中我们存储的关键数据为键值对 pairAVL 树节点中的平衡因子。然后需要一个指向左子树的指针指向右子树的指针同时还需要一个指向父节点的指针可以让我们便于更新每个节点的平衡因子。如下 template class K, class V
struct AVLTreeNode {AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _balanceFactor;AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _balanceFactor(0){}
}; AVL 树的插入 关于 AVL 树而言只是在二叉搜索树的基础上引入了平衡因子所以 AVL 树也可以看出二叉搜索树左右高度差不大于1的二叉搜索树所以对于 AVL 树的插入可以分为以下两步 1. 按照二叉搜索树的方式插入新节点。 2. 调整节点的平衡因子。 所以我们插入节点只需要找到应该插入的位置然后插入即可寻找插入位置按照键值小于当前节点向左子树搜索键值大于当前节点向右子树搜索的原则直到找到空节点为止就是应该插入的位置。寻找的时候还需要记录下每一次搜索的父节点便于链接指针如下 bool insert(const pairK, V kv) {if (_root nullptr) {_root new Node(kv);return true;}// 开始查找Node* parent nullptr;Node* cur _root;while (cur) {if (cur-_kv.first kv.first)parent cur, cur cur-_right;else if (cur-_kv.first kv.first)parent cur, cur cur-_left;elsereturn false;}// cur nullptrcur new Node(kv);// 链接孩子节点和父节点if (parent-_kv.first kv.first)parent-_left cur;elseparent-_right cur;cur-_parent parent;// 需要更新平衡因子...return true;
}插入成功则返回 true插入失败树中已经存在键值则返回 false。 以上只是完成了插入插入元素之后我们还需要更新节点的平衡因子更新平衡因子按照以下原则进行更新 1. 插入元素位置位于父节点的右边父节点的平衡因子 1 2. 插入元素位置位于父节点的左边父节点的平衡因子 -1。 3. 更新完父节点的平衡因子之后父节点的平衡因子的取值可能为 0、正负1、正负2。 5. 父节点的平衡因子更新完之后为0不会影响父节点的父节点的平衡所以不用在往上更新。 6. 父节点的平衡因子跟新完之后为正负1说明原来父节点的平衡因子为0这时还会影响父节点的父节点的平衡因子所以需要继续向上更新。当某个节点的平衡原则为正负二的时候我们就需要通过选择使树平衡。 如下 // 需要更新平衡因子
// 如果是在父亲的左边父亲的平衡因子减一、右边加一
if (parent-_left cur)parent-_balanceFactor--;
elseparent-_balanceFactor;
// 查看爷爷结点是否需要更新while (parent) {if (parent-_balanceFactor 0) {break;}else if (parent-_balanceFactor 1 || parent-_balanceFactor -1) {if (parent _root)break;// 现在的parent就不可能等于nullparent parent-_parent;cur cur-_parent;if (parent-_left cur)parent-_balanceFactor--;elseparent-_balanceFactor;}else if(parent-_balanceFactor 2 || parent-_balanceFactor -2) {if (parent-_balanceFactor 2 cur-_balanceFactor 1)RotateLeft(parent);else if (parent-_balanceFactor -2 cur-_balanceFactor -1)RotateRight(parent);else if (parent-_balanceFactor -2 cur-_balanceFactor 1)RotateLeftRight(parent);else if (parent-_balanceFactor 2 cur-_balanceFactor -1)RotateRightLeft(parent);elseassert(false);break;}else {assert(false);}
} 对于如上的代码中其中最难的一步就是旋转关于旋转一共会出现四种情况左单旋、右单旋、左右双旋、右左双旋。 AVL 树的旋转 我们首先介绍右单旋当新节点插入导较高左子树的左侧就会出现右单旋关于右单旋出现的情况如下 当出现如上所示的情况时父亲节点的平衡因子等于-2左孩子节点的平衡因子为-1时我们就需要进行右旋也就是将左孩子作为父节点父节点作为右孩子在将左孩子的右节点链接到原父节点上。其中还有需要注意的点右旋时的父节点不一定是根节点所以我们在旋转的时候还需要记录下父节点的父节点最后将其链接到一起。 void RotateRight(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;// 将左孩子的右节点链接到原父亲结点if (subLR) subLR-_parent parent;parent-_left subLR;Node* ppNode parent-_parent;// 将左孩子变为原父亲结点的父亲subL-_right parent;parent-_parent subL;// 将爷爷结点重新链接if (ppNode nullptr) {_root subL;_root-_parent nullptr;}else {if (ppNode-_left parent)ppNode-_left subL;elseppNode-_right subL;subL-_parent ppNode;}subL-_balanceFactor parent-_balanceFactor 0;
} 记得最后将节点的平衡因子设置为0。 接着我们介绍左单旋当新节点插入到较高右子树的右侧关于这种情况如下 关于左单旋其思想和右单旋基本一致不过是将右单旋的给镜像了过来。所以当父节点的平衡因子为2右节点的平衡因子为1的时候我们就需要对树进行左单旋。也就是让右孩子的左节点作为父节点的右孩子左节点作为父节点原父节点作为左孩子的左节点。注意原父节点的父节点是否为 nullptr最后需要更新节点的平衡因子。如下 void RotateLeft(Node* parent) {Node* subR parent-_right;Node* subRL subR-_left;Node* ppNode parent-_parent;parent-_right subRL;if (subRL) subRL-_parent parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr) {_root subR;_root-_parent nullptr;}else {if (ppNode-_left parent)ppNode-_left subR;elseppNode-_right subR;subR-_parent ppNode;}subR-_balanceFactor parent-_balanceFactor 0;
} 第三种情况左右双旋。左右双旋就是分别需要左旋一次然后右旋一次接着更新我们的平衡因子如下 如上图所示当左孩子节点的平衡因子为1父节点的平衡因子为-2的时候我们就需要进行左右双旋当我们旋转之后当前父节点的平衡因子一定为0但原父节点和左孩子节点的平衡因子一共有三种情况分别是0 01 00 -1。当 h 0 的时候插入的节点就是以上的60节点旋转之后所有节点一共就3个节点都是为0当节点插入到60的左边那么30的平衡因子为0如图当节点插入到60的右边90的平衡因子则为0。 因为在单独调用左单选右单旋之后会将所有节点的平衡因子都置为0所以我们需要进行特殊处理。如下 void RotateLeftRight(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;int balanceFactor subLR-_balanceFactor;// 先左旋后右旋RotateLeft(subL);RotateRight(parent);subLR-_balanceFactor 0;if (balanceFactor -1) {subL-_balanceFactor 0;parent-_balanceFactor 1;}else if (balanceFactor 1) {parent-_balanceFactor 0;subL-_balanceFactor -1;}else if (balanceFactor 0) {parent-_balanceFactor 0;subL-_balanceFactor 0;}else {assert(false);}
} 最后一种情况右左双旋。也就是先右旋然后在左旋也就是和以上的情况是堆成的情况如下 对于需要右左旋转的情况为父节点为2右孩子为1.关于转换的细节和以上的左右双旋的情况向对称在这就不细讲了代码如下 void RotateRightLeft(Node* parent) {Node* subR parent-_right;Node* subRL subR-_left;int balanceFactor subRL-_balanceFactor;RotateRight(subR);RotateLeft(parent);// 更新平衡因子subRL-_balanceFactor 0;if (balanceFactor -1) {parent-_balanceFactor 0;subR-_balanceFactor 1;}else if (balanceFactor 1) {parent-_balanceFactor -1;subR-_balanceFactor 0;}else if (balanceFactor 0) {parent-_balanceFactor 0;subR-_balanceFactor 0;}else {assert(false);}
} AVL 树的验证 测试 接下来我们将对我们是新的 AVL 树进行验证也就是看我们写出的代码是否符合 AVL 树的特性其中主要包括特性测试和压力测试。在进行测试之前我们需要先写出一些辅助函数如下 template class K, class V
class AVLTree {
public:typedef AVLTreeNodeK, V Node;void InOrder() {_InOrder(_root);cout endl;}int height() {int h _height(_root);return h;}int size() {int s _size(_root);return s;}bool IsBalance() {return _IsBalance(_root);}private:bool _IsBalance(Node* root) {if (root nullptr)return true;int leftHeight _height(root-_left);int rightHeight _height(root-_right);if (abs(leftHeight - rightHeight) 2)return false;if (abs(root-_balanceFactor) 2)return false;return _IsBalance(root-_left) _IsBalance(root-_right);}int _height(Node* root) {if (root nullptr)return 0;int left _height(root-_left);int right _height(root-_right);int height max(left, right);return height 1;}int _size(Node* root) {if (root nullptr)return 0;return _size(root-_left) _size(root-_right) 1;}void _InOrder(Node* root) {if (root nullptr) return;_InOrder(root-_left);cout root-_kv.first root-_kv.second endl;_InOrder(root-_right);}
private:Node* _root nullptr;
}; 我们先进行特性测试如下 如上所示我们一共验证了两组数据其中包含了左旋、右旋、左右双旋、右左双旋四种情况。 接着进行暴力测试生成一百万个数据主要测试性能和插入是否成功 如上所示插入一百万个数据也可以生成平衡树。 测试源码如下 void TestAVL01() {int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };// {16, 3, 7, 11, 9, 26, 18, 14, 15}AVLTreeint, int avtree;for (auto e : a) {if (e 4) {int i 0;}avtree.insert(make_pair(e, e));}avtree.InOrder();cout avtree.height() endl;cout avtree.size() endl;cout avtree.IsBalance() endl;
}void TestAVL02() {const int N 1000000;vectorint v;v.reserve(N);srand(time(0));for (int i 0; i N; i) {v.push_back(rand() 1);}size_t begin1 clock();AVLTreeint,int tree;for (auto e : v)tree.insert({e, e});size_t end1 clock();cout insert end1 - begin1 endl;cout Height: tree.height() endl;cout Size: tree.size() endl;size_t begin2 clock();for (auto e : v)tree.find(e);size_t end2 clock();cout find: end2 - begin2 endl;cout tree.IsBalance() endl;
}
