- 使用 Spring Initializr 创建 Spring Boot 应用程序
- 在Spring Boot中配置Cassandra
- 在 Spring Boot 上配置 Tomcat 连接池
- 将Camel消息路由到嵌入WildFly的Artemis上
之前提到的二叉搜索树效率为logN
,但是当插入节点有序的时候效率退化为O(N)
,这可就很致命了。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:
当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
一棵AVL树是具有以下特点的二叉搜索树:
因为涉及到了大量的平衡因子调节,所以需要保存父节点的指针,选择用三叉链的结构。
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K,V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0)
{}
AVLTreeNode<K, V>* _left;//该结点的左孩子
AVLTreeNode<K, V>* _right;//该结点的右孩子
AVLTreeNode<K, V>* _parent;//该结点的双亲
pair<K, V> _kv;
int _bf;//该结点的平衡因子
};
AVL树的查找跟搜索树一样
1.若为空树,返回空
2.key值比当前结点的key值大就到右边找
3.key值比当前结点的key值大就到左边找
4.key值和当前结点的key值相等或者没找到返回false
Node* Find(const K& key)
{
//根据二叉搜索树的性质,从根节点出发,比根节点大则查找右子树,比根节点小则查找左子树
Node* cur = _root;
while (cur)
{
//比根节点大则查找右子树
if (key > cur->_kv.first)
{
cur = cur->_right;
}
//比根节点小则查找左子树
else if (key < cur->_kv.first)
{
cur = cur->_left;
}
//相同则返回
else
{
return cur;
}
}
//遍历完则说明查找不到,返回false
return nullptr;
}
**平衡因子,其实就是左右子树的高度差。AVL树通过控制高度差不超过1,来实现平衡。**当插入一个新的结点它祖先的平衡因子都会收到影响。
平衡因子的更新规则:
1.新增结点在parent的右边,平衡因子++
2.新增结点在parent的左边,平衡因子- -
例如:
右子树插入一个90,根节点平衡因子+1
每更新完一个结点的平衡因子后,都需要进行判断:
1.parent的平衡因子等于1或者-1则继续往上更新
2.parent的平衡因子等于0,则停止更新
3.parent的平衡因子等于2或者-2,说明已经不平衡了需要进行旋转处理
分析:
1.parent更新后的平衡因子为1或-1,则说明在parent的右边或者左边新增了结点,从而影响了parent的父亲结点所以要继续往上更新平衡因子。
2.parent更新后的平衡因子为0,1或-1经过++或- -变成0,说明新增结点在parent高的一侧使得parent的左右子树一样高,不会影响parent的父亲结点,就不用往上更新平衡因子。
3.parent更新后的平衡因子为2或-2,parent的左右子树差的绝对值大于1,已经不满足AVL树,需要旋转处理。
旋转分为四种情景,简单点总结的话就是如果节点呈直线则单旋,折线则双旋,下面一一分析。
具象图:
具象图情况太多,上面就举一个例子便于理解,下面用抽象图概括:
需要注意的细节:
1.subLR可能为空
2.先把30的右给60的左,在让60整棵树左30的右子树。因为是三叉链实现的,所以还要注意修改动的结点的父亲结点
3.60可能是子树,也有可能是单独的树
右旋的步骤:
//右旋
void RotateR(Node* parent)
{
//步骤1 让不平衡的结点parent的左子树变为其原本左子树subL的右节点subLR
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
//如果subLR存在,则让他的父节点指向parent。
if (subLR)
{
subLR->_parent = parent;
}
//步骤2 让parent变为subL的右子树
subL->_right = parent;
//步骤3 调整新的父节点subL与祖父节点的关系,并调整旋转后的平衡因子
Node* ppNode = parent->_parent;//保存原本的祖父节点
parent->_parent = subL;//更新parent的父节点
//两种情况
//如果parent为根节点,则让subL成为新的根节点
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
//如果不是根节点,则改变subL与其祖父节点的指向关系
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
//左旋完成后平衡,平衡因子归零。
subL->_bf = parent->_bf = 0;
}
左旋的思路和右旋一样,只是将顺序翻了过来。
当右边不平衡,并且节点呈直线时(右节点的右边偏重),说明需要左旋处理。
具象图
抽象图
左旋的步骤:
//左旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
Node* ppNode = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
subR->_bf = parent->_bf = 0;
}
分类讨论
情况1:新增节点在C
情况2:新增节点在b
情况3:本身就是新增节点
右左双旋的步骤:
1.首先因为不平衡那个方向的子树的反方向偏重,呈折现状态,所以需要对其右旋转,让树恢复到直线状态
2.直线状态时就和一开始的单旋思路一样,按照单旋处理
3.调节平衡因子,根据subRL一开始的平衡因子进行调节,有两种情况,为-1时subR结束后为1,为1时parent结束后为-1。
总结上面的情况:需记录subRL的平衡因子,保存subR,subRL。根据subRL的平衡因子在更新其他需要更新的平衡因子
情况一:当subRL的平衡因子=1时,subR,subRL,parent的平衡因子分别是0,0,-1
情况二:当subRL的平衡因子=-1时,subR,subRL,parent的平衡因子分别是1,0,0
情况三:当subRL的平衡因子=0时,subR,subRL,parent的平衡因子的都是0
//右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//这里需要保存subRL的平衡因子,来调节旋转完后的平衡因子
int bf = subRL->_bf;
//先右单旋将折线结构转换为直线结构,也就是前面单旋就可以解决的问题。
RotateR(subR);
//然后再左单旋即可
RotateL(parent);
//根据subRL的bf来调节旋转后的平衡因子
if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
}
与右左类似,图片不再细化了,读者可以尝试自己画画。
总结平衡因子的变化:根据subLR的平衡因子在更新其他需要更新的平衡因子
1.当subLR的平衡因子=1时,subL,subLR,parent的平衡因子分别是-1,0.0;
2.当subLR的平衡因子=-1时,subL,subLRL,parent的平衡因子分别是0,0,1;
3.当subLR的平衡因子=0时,subL,subLR,parent的平衡因子的都是0
//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
}
插入分为三个步骤
有了前面旋转的基础,这里直接复用代码就行,具体步骤也写在注释里
bool insert(const pair<K, V>& kv)
{ //树为空,new一个新节点
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = cur;
while (cur)
{
if (cur->_kv.first > kv.first)//插入结点的key值小于当前结点,往左走
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)//插入结点的key值大于当前结点,往右走
{
parent = cur;
cur = cur->_right;
}
else
{
return false;//没有找到,返回false
}
}
//插入节点
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
//注意是三叉链,还要链接上parent
parent->_right = cur;
cur->_parent = parent;
}
else
{
//要链接上parent
parent->_left = cur;
cur->_parent = parent;
}
//控制平衡
//1.更新平衡因子
//2.如果出现不平衡则需要旋转处理
while (parent)
{
//在父亲结点左边插入平衡因子--,右边则++
if (parent->_left == cur)
parent->_bf--;
else
parent->_bf++;
//1.平衡因子=0就不要更新平衡因子了
//2.=1或-1则要继续往上调整
//3.=2或-2则要旋转处理
if (parent->_bf == 0)
{
break;
}
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)
{
if (cur->_bf == -1)
{
//左边不平衡,并且子节点也是左边偏重,右单旋
RotateR(parent);
}
else
{
//左右双旋
RotateLR(parent);
}
}
else //parent->_bf == 2
{
if (cur->_bf == 1)
{
//如果右边不平衡,并且子节点也是右边偏重,则左单旋
RotateL(parent);
}
else
{
//如果右边不平衡,而子节点是左边偏重,此时需要先转换为上面的状态,先右单旋再左单旋。但是不能直接右单旋再左单旋,还需要根据情况处理平衡因子。
RotateRL(parent);
}
}
break;
}
else
{
//走到这里就不是旋转的问题,你要检查别的问题
assert(false);
}
}
return true;
}
AVL树的删除极为复杂,可以不要求掌握,了解即可,但是其实删除的思路和插入类似,分为以下几步。
1.按照二叉搜索树的规则删除
2.更新平衡因子,并且进行旋转来调整(最坏情况下可能会一直调整到根节点)。
这里就直接复用上面平衡因子更新的代码以及之前博客实现的二叉搜索树的删除。
bool erase(const K& key)
{
//删除直接按照二叉搜索树的规则删除,然后再进行平衡因子的更新即可
Node* cur = _root;
Node* parent = cur;
/*
删除有三种情况,一种是删除叶子节点,可以直接删除
第二种情况,如果删除的节点只有一个子树,那么删除这个节点后,就让父节点指向他的这一子树
前两种情况可以合并处理
第三种情况则是左右子树都不为空,此时选择一个来节点来替换他后,再删除,就可以不破坏原有结构
如果要保持原有结构不变化,那么选择的节点必须要和删除节点在中序遍历中是连续的,而满足的只有两个节点,一个是其左子树的最大值,一个是其右子树的最小值。
*/
//删除部分
while (cur)
{
//找到删除的位置
if (key > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
//前两种情况合并处理,如果当前结点只有一个子树,则让父节点指向他的子树
//处理只有右子树时
if (cur->_left == nullptr)
{
//如果当前节点为根节点,则让右子树成为新的根节点
if (cur == _root)
{
_root = cur->_left;
}
else
{
//判断当前节点是他父节点的哪一个子树
if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
}
//处理只有左子树时
else if (cur->_right == nullptr)
{
//如果当前节点为根节点,则让左子树成为新的根节点
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
}
//处理左右子树都不为空时,选取左子树的最右节点或者右子树的最左节点
else
{
//这里我选取的是左子树的最右节点
Node* LeftMax = cur->_left;
Node* LeftMaxParent = cur;
//找到左子树的最右节点
while (LeftMax->_right)
{
LeftMaxParent = LeftMax;
LeftMax = LeftMax->_right;
}
//替换节点
std::swap(cur->_kv, LeftMax->_kv);
//判断当前节点是他父节点的哪一个子树, 因为已经是最右子树了,所以这个节点的右子树为空,但是左子树可能还有数据,所以让父节点指向他的左子树
//并且删除最右节点
if (LeftMax == LeftMaxParent->_left)
{
LeftMaxParent->_left = LeftMax->_left;
}
else
{
LeftMaxParent->_right = LeftMax->_left;
}
delete LeftMax;
}
//删除成功,中断
break;
}
}
//查找不到
if (cur == nullptr)
return false;
//更新平衡因子
while (parent)
{
//更新父节点的平衡因子,注意这里和插入是反过来的,因为是删除
if (cur == parent->_left)
{
parent->_bf++;
}
else
{
parent->_bf--;
}
//判断更新后父节点是否平衡
//平衡
if (parent->_bf == 0)
{
break;
}
//高度发生变化,要继续往上判断
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)
{
//如果右边不平衡,并且子节点也是右边偏重,则左单旋
if (cur->_bf == 1)
{
RotateL(parent);
}
//如果右边不平衡,而子节点是左边偏重,此时需要先转换为上面的状态,先右单旋再左单旋。但是不能直接右单旋再左单旋,还需要根据情况处理平衡因子
else
{
RotateRL(parent);
}
}
else
{
//左边不平衡,并且子节点也是左边偏重,右单旋
if (cur->_bf == -1)
{
RotateR(parent);
}
//同上,左右双旋
else
{
RotateLR(parent);
}
}
//旋转完后恢复平衡,更新结束。
break;
}
}
return true;
}
AVL树有两点需要验证:二叉搜索和高度平衡
1.二叉搜索树的特性,可以通过中序遍历来看看是否有序来判断。
2.高度平衡可以通过判断他所有的子树是否两边高度平衡,来判断其是否具有平衡的特性。
中序遍历
void _InOrderTravel(Node* root) const
{
if (root == nullptr)
return;
_InOrderTravel(root->_left);
std::cout << root->_kv.first << ':' << root->_kv.second << std::endl;
_InOrderTravel(root->_right);
}
void InOrderTravel() const
{
_InOrderTravel(_root);
}
int main()
{
int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14};
//int arr{ 16, 3, 7, 11, 9, 26, 18, 14, 15 };
AVLTree<int, int> t;
for (auto e : arr)
{
t.insert(make_pair(e,e));
}
t.InOrderTravel();
return 0;
}
到这里验证通过只能说明是搜索树没有问题。我们还要验证树是否平衡。
1.先计算出左右子树的高度
2.再检测每课子树的平衡因子
int countHeight(Node* root) const
{
if (root == nullptr)
return 0;
int leftHeight = countHeight(root->_left);
int rightHeight = countHeight(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool _IsBalance(Node* root) const
{
if (root == nullptr)
return true;
int leftHeight = countHeight(root->_left);
int rightHeight = countHeight(root->_right);
return abs(leftHeight - rightHeight) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
bool IsBalance() const
{
return _IsBalance(_root);
}
这里再推荐一道题,可以顺便去AC了:验证平衡二叉树
修改可以直接调用insert,最后直接返回pair对象。
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return make_pair(_root, true);
}
// 找到存储位置,把数据插入进去
Node* parent = _root, * cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(cur, true);
}
}
cur = new Node(kv);
Node* newnode = cur;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
// 控制平衡
// 1、更新平衡因子
// 2、如果出现不平衡,则需要旋转
//while (parent)
while (cur != _root)
{
if (parent->_left == cur)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
// parent所在的子树高度变了,会影响parent->parent
// 继续往上更新
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//parent所在子树已经不平衡,需要旋转处理一下
if (parent->_bf == -2)
{
if (cur->_bf == -1)
{
// 右单旋
RotateR(parent);
}
else // cur->_bf == 1
{
RotateLR(parent);
}
}
else // parent->_bf == 2
{
if (cur->_bf == 1)
{
// 左单旋
RotateL(parent);
}
else // cur->_bf == -1
{
RotateRL(parent);
}
}
break;
}
else
{
// 插入节点之前,树已经不平衡了,需要检查
assert(false);
}
}
return make_pair(newnode, true);
}
CSDN 社区图书馆,开张营业!
深读计划,写书评领图书福利~
背景: 我最近一直在使用 JPA,我为相当大的关系数据库项目生成持久层的轻松程度给我留下了深刻的印象。 我们公司使用大量非 SQL 数据库,特别是面向列的数据库。我对可能对这些数据库使用 JPA 有一
我已经在我的 maven pom 中添加了这些构建配置,因为我希望将 Apache Solr 依赖项与 Jar 捆绑在一起。否则我得到了 SolarServerException: ClassNotF
interface ITurtle { void Fight(); void EatPizza(); } interface ILeonardo : ITurtle {
我希望可用于 Java 的对象/关系映射 (ORM) 工具之一能够满足这些要求: 使用 JPA 或 native SQL 查询获取大量行并将其作为实体对象返回。 允许在行(实体)中进行迭代,并在对当前
好像没有,因为我有实现From for 的代码, 我可以转换 A到 B与 .into() , 但同样的事情不适用于 Vec .into()一个Vec . 要么我搞砸了阻止实现派生的事情,要么这不应该发
在 C# 中,如果 A 实现 IX 并且 B 继承自 A ,是否必然遵循 B 实现 IX?如果是,是因为 LSP 吗?之间有什么区别吗: 1. Interface IX; Class A : IX;
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
我正在阅读标准haskell库的(^)的实现代码: (^) :: (Num a, Integral b) => a -> b -> a x0 ^ y0 | y0 a -> b ->a expo x0
我将把国际象棋游戏表示为 C++ 结构。我认为,最好的选择是树结构(因为在每个深度我们都有几个可能的移动)。 这是一个好的方法吗? struct TreeElement{ SomeMoveType
我正在为用户名数据库实现字符串匹配算法。我的方法采用现有的用户名数据库和用户想要的新用户名,然后检查用户名是否已被占用。如果采用该方法,则该方法应该返回带有数据库中未采用的数字的用户名。 例子: “贾
我正在尝试实现 Breadth-first search algorithm , 为了找到两个顶点之间的最短距离。我开发了一个 Queue 对象来保存和检索对象,并且我有一个二维数组来保存两个给定顶点
我目前正在 ika 中开发我的 Python 游戏,它使用 python 2.5 我决定为 AI 使用 A* 寻路。然而,我发现它对我的需要来说太慢了(3-4 个敌人可能会落后于游戏,但我想供应 4-
我正在寻找 Kademlia 的开源实现C/C++ 中的分布式哈希表。它必须是轻量级和跨平台的(win/linux/mac)。 它必须能够将信息发布到 DHT 并检索它。 最佳答案 OpenDHT是
我在一本书中读到这一行:-“当我们要求 C++ 实现运行程序时,它会通过调用此函数来实现。” 而且我想知道“C++ 实现”是什么意思或具体是什么。帮忙!? 最佳答案 “C++ 实现”是指编译器加上链接
我正在尝试使用分支定界的 C++ 实现这个背包问题。此网站上有一个 Java 版本:Implementing branch and bound for knapsack 我试图让我的 C++ 版本打印
在很多情况下,我需要在 C# 中访问合适的哈希算法,从重写 GetHashCode 到对数据执行快速比较/查找。 我发现 FNV 哈希是一种非常简单/好/快速的哈希算法。但是,我从未见过 C# 实现的
目录 LRU缓存替换策略 核心思想 不适用场景 算法基本实现 算法优化
1. 绪论 在前面文章中提到 空间直角坐标系相互转换 ,测绘坐标转换时,一般涉及到的情况是:两个直角坐标系的小角度转换。这个就是我们经常在测绘数据处理中,WGS-84坐标系、54北京坐标系
在软件开发过程中,有时候我们需要定时地检查数据库中的数据,并在发现新增数据时触发一个动作。为了实现这个需求,我们在 .Net 7 下进行一次简单的演示. PeriodicTimer .
二分查找 二分查找算法,说白了就是在有序的数组里面给予一个存在数组里面的值key,然后将其先和数组中间的比较,如果key大于中间值,进行下一次mid后面的比较,直到找到相等的,就可以得到它的位置。
我是一名优秀的程序员,十分优秀!