东莞网站建设基本流程,电子商务有什么用,厦门建设局怎么进,江苏固茗建设有限公司网站目录
一、二叉搜索树
二、AVL树
2.1 左单旋
2.2 右单旋
2.3 左右双旋
2.4 右左双旋
三、AVL.h
四、test.cpp 一、二叉搜索树
二叉搜索树#xff0c;又称二叉排序树#xff08;Binary Search Tree#xff09;#xff0c;相比于普通二叉树#xff0c;BST的特性有又称二叉排序树Binary Search Tree相比于普通二叉树BST的特性有
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 二叉搜索树通常在数据插入的时候便会将数据正确排序不允许插入重复值这样在进行数据查询的时候一般情况下时间复杂度是但是如果插入的数据为一个有序或接进有序的序列即退化成了单支树这时时间复杂度退化到。 二、AVL树
AVL树也叫平衡二叉搜索树是二叉搜索树的进化版设计是原理是弥补二叉搜索树的缺陷当插入的数据接近于有序数列时二叉搜索树的性能严重下降。
AVL的节点设计采用三叉链结构(每个节点包含left, right, parent三个节点指针)每个节点中都有平衡因子bf。
AVL树在BST的基础上引入了一个平衡因子bf用于表示左右子树的高度差并控制其不超过1若在数据插入时左右子树的高度差超过1了AVL树会寻找新的节点作为根节点进行调整树的结构这样AVL树进行数据查询的时间复杂度就稳定在了。
AVL的特点是左子树和右子树高度差 2平衡因子bf就是右子树高度 - 左子树高度的差当bf等于2或-2时AVL将根据不同情况进行旋转调节使其始终保持AVL树的特性。
对于一棵AVL树若它的节点数为n则它的深度为。 2.1 左单旋
若数列 1,2,3 按顺序插入AVL树则树的结构为图1 图1 数列{1,2,3}插入AVL树 图1 中parent节点的平衡因子bf为2新节点向上调节时的cur节点的平衡因子为1这种情况需要左单旋cur节点的左子树空变成parent节点的右子树parent节点变成cur节点的左子树。 图2 左单旋后的节点 2.2 右单旋
右单旋与左单旋类似也是根据平衡因子情况进行旋转调整。 图1 向AVL树中插入新节点1 图1 新节点1插入向上调整平衡因子出现parent-bf -2, cur-bf -1此时需要右单旋cur节点的右子树变为parent节点的左子树parent变成cur节点的右子树。 图2 右单旋结果 2.3 左右双旋
左右双旋在设计上可以调用左单旋和右单旋函数但是需要不同情况讨论旋转后的平衡因子。 图1 新插入节点0 图1 新插入节点0后parent-bf -2, cur-bf 1此时需要左右双旋即先以节点-1为父节点进行一次左单旋再以1为父节点进行一次左单旋节点0的左子树空变成节点-1的左子树节点-1变成节点0的左子树。 图2 以节点-1位父节点左单旋结果 图2 完成左单旋之后再以1位父节点进行一次右单旋节点0的右子树空变成节点1的左子树节点1变成节点0的右子树。 图3 完成右单旋同时完成左右双旋 2.4 右左双旋 图1 插入新节点65 图1 中红色数字就是每个节点平衡因子值为65的节点是新插入的节点当其插入之后所有节点的平衡因子更新出现了parent平衡因子为2cur平衡因子为1此时需要进行旋转调节。 图2 观察平衡因子 图2 观察平衡因子决定旋转策略为右左双旋即先进行一次右单旋再进行一次左单旋。右单旋是以节点80为父节点进行即节点60的右子树变成节点80的左子树节点80变成节点60的右子树。 图3 右单旋结果 图3 右单旋结束接下来再一次进行以节点40为父节点的左单旋即节点60的左子树变成节点40的右子树节点40变成节点60的左子树。 图4 右左双旋旋转最终结果 三、AVL.h
#define _CRT_SECURE_NO_WARNINGS 1#pragma once
#include iostreamtemplateclass K, class V
struct AVLTreeNode
{std::pairK, V kv;AVLTreeNode* parent;AVLTreeNode* left;AVLTreeNode* right;int bf;AVLTreeNode(const std::pairK, V x): kv(x), parent(nullptr), left(nullptr), right(nullptr), bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const std::pairK, V x){if (_root nullptr){_root new Node(x);return true;}// 通过二叉搜索树找到需要插入节点的位置Node* parent nullptr;Node* cur _root;while (cur){parent cur;if (cur-kv.first x.first)cur cur-right;else if (cur-kv.first x.first)cur cur-left;elsereturn false;}cur new Node(x);cur-parent parent;if (parent-kv.first x.first)parent-left cur;elseparent-right cur;// 更新平衡因子while (parent){if (parent-left cur)--parent-bf;elseparent-bf;if (parent-bf 0){return true;}else if (parent-bf 1 || parent-bf -1){// 继续向上更新cur parent;parent parent-parent;}else if (parent-bf 2 || parent-bf -2){if (parent-bf 2 cur-bf 1)_RotateLeft(parent);else if (parent-bf -2 cur-bf -1)_RotateRight(parent);else if (parent-bf -2 cur-bf 1)_RotateLeftRight(parent);else if (parent-bf 2 cur-bf -1)_RotateRightLeft(parent);break;}}}void InOrder(){_InOrder(_root);std::cout std::endl;}bool IsBalance(){return _IsBalance(_root);}private:void _RotateLeft(Node* parent){Node* subR parent-right;Node* subRL subR-left;parent-right subRL;if (subRL ! nullptr)subRL-parent parent;subR-left parent;Node* ppNode parent-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;}parent-bf subR-bf 0;}void _RotateRight(Node* parent){Node* subL parent-left;Node* subLR subL-right;parent-left subLR;if (subLR ! nullptr)subLR-parent parent;subL-right parent;Node* ppNode parent-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;}parent-bf subL-bf 0;}void _RotateLeftRight(Node* parent){Node* subL parent-left;Node* subLR subL-right;int bf subLR-bf;_RotateLeft(subL);_RotateRight(parent);if (bf 0){subLR-bf 0;subL-bf 0;parent-bf 0;}else if (bf -1){subLR-bf 0;subL-bf 0;parent-bf 1;}else if (bf 1){subLR-bf 0;subL-bf -1;parent-bf 0;}}void _RotateRightLeft(Node* parent){Node* subR parent-right;Node* subRL subR-left;int bf subRL-bf;_RotateRight(subR);_RotateLeft(parent);if (bf 0){subRL-bf 0;subR-bf 0;parent-bf 0;}else if (bf -1){subRL-bf 0;subR-bf 1;parent-bf 0;}else if (bf 1){subRL-bf 0;subR-bf 0;parent-bf -1;}}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-left);std::cout root-kv.first , root-kv.second ;_InOrder(root-right);}int _Height(Node* root){if (root nullptr)return 0;int leftHeight _Height(root-left);int rightHeight _Height(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}bool _IsBalance(Node* root){if (root nullptr)return true;int leftHeight _Height(root-left);int rightHeight _Height(root-right);if (rightHeight - leftHeight ! root-bf){std::cout 平衡因子异常 std::endl;return false;}return abs(rightHeight - leftHeight) 2 _IsBalance(root-left) _IsBalance(root-right);}private:Node* _root nullptr;
};四、test.cpp
#define _CRT_SECURE_NO_WARNINGS 1#include AVL.hvoid Test1()
{int a[] { 2, 4, 5, 8, 10, 1, 3, 5, 7, 9, 100, 200, -100, 0 };AVLTreeint, int t;for (auto e : a){t.Insert(std::make_pair(e, e * 2));}t.InOrder();std::cout t.IsBalance() std::endl std::endl;
}void Test2()
{int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTreeint, int t;for (auto e : a){t.Insert(std::make_pair(e, e * 2));}t.InOrder();std::cout t.IsBalance() std::endl std::endl;
}void Test3()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTreeint, int t;for (auto e : a){t.Insert(std::make_pair(e, e * 2));}t.InOrder();std::cout t.IsBalance() std::endl std::endl;
}int main()
{Test1();Test2();Test3();return 0;
}
