广告联盟建设个人网站,中国制造网外贸平台app,湖北建科建设工程有限公司网站,北京微网站制作价格目录 120 二叉搜索树 min max
121 二叉搜索树 put
122 二叉搜索树 前任后任1
123 二叉搜索树 前任后任2
124 二叉搜索树 删除1
125 二叉搜索树 删除2
126 二叉搜索树 删除3
127 二叉搜索树 删除 递归1
128 二叉搜索树 删除 递归2
129 二叉搜索树 范围查询
130 二叉搜…目录 120 二叉搜索树 min max
121 二叉搜索树 put
122 二叉搜索树 前任后任1
123 二叉搜索树 前任后任2
124 二叉搜索树 删除1
125 二叉搜索树 删除2
126 二叉搜索树 删除3
127 二叉搜索树 删除 递归1
128 二叉搜索树 删除 递归2
129 二叉搜索树 范围查询
130 二叉搜索树 e01-e03 删增查
131 二叉搜索树 e04 判断合法 中序非递归
132 二叉搜索树 e04 判断合法 中序递归1
133 二叉搜索树 e04 判断合法 中序递归2
134 二叉搜索树 e04 判断合法 上下界
135 二叉搜索树 e05 求范围和
136 二叉搜索树 e06 根据前序遍历结果建树1
137 二叉搜索树 e06 根据前序遍历结果建树2
138 二叉搜索树 e06 根据前序遍历结果建树3
139 二叉搜索树 e07 最近公共祖先
140 avl树 概述
141 avl树 高度和平衡因子
142 avl 四种失衡情况
143 avl 旋转 120 二叉搜索树 min max
递归代码 非递归代码 121 二叉搜索树 put 122 二叉搜索树 前任后任1 123 二叉搜索树 前任后任2 124 二叉搜索树 删除1 125 二叉搜索树 删除2 126 二叉搜索树 删除3 127 二叉搜索树 删除 递归1 意思是假如我要删除的是6那我现在就要将7返回然后让4指向7这样就断开了4和6的连接那就可以删除6了。
因此通俗来说就是将要删除的节点的孩子返回然后让删除节点的父母指向要删除的节点的孩子。 这一部分的代码是找出要删除的节点。因为如果node.keykey就走到后面的代码去了就不会在着三个if走。 这一部分的代码意思是拿原先给的图片来做例子
来一个伪递归
private BSTNode doDelete(BSTNode node,int key){
//比如我要删除的是6 key6
if(node null){
return null;
}
if(key node.key){
node.left doDelete(node.left,key);
return node;
}
if(key node.key){ 64
node.right private BSTNode doDelete(BSTNode node,int key){//现在传进来的是4的右孩子也就是6而且6没有左孩子因此直接走下面这几行代码
if(node.left null){
return node.right; //这里的意思是返回6的右孩子也就是7
} /return node;
}
if(node.left null){
return node.right;
}
if(node.right null){
return node.left;
}
}
下一步
private BSTNode doDelete(BSTNode node,int key){
//比如我要删除的是6 key6
if(node null){
return null;
}
if(key node.key){
node.left doDelete(node.left,key);
return node;
}
if(key node.key){ 64
node.right private BSTNode doDelete(BSTNode node,int key){//现在传进来的是4的右孩子也就是6而且6没有左孩子因此直接走下面这几行代码
if(node.left null){
return 7/return node;
}
if(node.left null){
return node.right;
}
if(node.right null){
return node.left;
}
}
下一步
private BSTNode doDelete(BSTNode node,int key){
//比如我要删除的是6 key6
if(node null){
return null;
}
if(key node.key){
node.left doDelete(node.left,key);
return node;
}
if(key node.key){ 64
node.right 7/return node;
}
if(node.left null){
return node.right;
}
if(node.right null){
return node.left;
}
} 下一步
private BSTNode doDelete(BSTNode node,int key){
//比如我要删除的是6 key6
if(node null){
return null;
}
if(key node.key){
node.left doDelete(node.left,key);
return node;
}
if(key node.key){
node.right 7
return node;//返回6 这个删除的节点
}
if(node.left null){
return node.right;
}
if(node.right null){
return node.left;
}
}
而这个时候。因为node.right 7了因此树已经连接好就是被删除节点的父母已经找到了要删除节点的孩子也意味着6已经被删除了因为已经没有人和它牵手了。 这里的作用是连接被删除节点的孩子们和被删除节点的父母的关系 128 二叉搜索树 删除 递归2 node是指要删除的节点
node 是4node.right 是5因此s是5进入循环找到node的右孩子的左孩子 让原来node被删除节点的左孩子全部托付给s也就是托付给5 可是如果要删除的节点和根节点之间有距离需要再加一些步骤。
那这个时候就有疑问了那会不会和没有距离的那些情况搞混淆了不会的他这里就是加了一步递归实际上就是做了一次无用功。还是拿刚才的例子做说明。 node 是4 s是5 我这里传进去的都是5而且5只有右孩子因此doDelete这个方法中它直接走下面这行代码 。return的就是6 所以s.right 还是等于6因此没有改变任何东西只是做了无用功。 回归正题如果就是根节点和被删除节点之间就是隔了很多的元素那代码解读应该如下 先解释一下图片的含义4是被删节点5是要后继节点。首先先将5拿开让6和7进行相连接然后再删除4让5替代4的位置。因为如果倒数第二行和倒数第三行的代码调换过来的话就会导致图片1的5那里有两个孩子增加麻烦。
好的我们来解释一下代码
将4的右节点也就是8和4的后继节点也就是5传入doDelete也就是将以8为树根的这棵树传进去删掉5之前的伪代码演示中可以发现doDelete可以删除5操作。因此就从图一转换为图二
node.left是2将这个2这个孩子交给s成为s也就是5的做左孩子。 129 二叉搜索树 范围查询 但是对于greater方法来说如果用正着来遍历的话就得把所有都遍历完但如果采用反向遍历就不需要。因此优化代码 最终完整的代码
因为最后的最后返回的是被删除节点因此要创建一个集合来收集被删除元素而被删除元素又只有一个因此取【0】即可以。 130 二叉搜索树 e01-e03 删增查 递归有一些缺点就是做了一些不必要的操作比如我要新增1但是在递归的过程中又把已经连接好的5和2又连接一次。 131 二叉搜索树 e04 判断合法 中序非递归 Long的最小值小于整数的最小值。 132 二叉搜索树 e04 判断合法 中序递归1 进行优化以下 解释一下为什么是在boolean a 下面添加if判断因为isValidBST node.left 传进去的是6的left也就是传进去的3因此a的真假是说明3是否符合条件。那既然3不符合的话直接返回false就好了就没有必要还去比较6这个值了。 这种行为也叫做剪枝。 如果是这样该怎么遍历呢直接从8开始。 红色的是来黑色深紫色也算黑色当时搞错颜色了而已的是回。
一层层走。
133 二叉搜索树 e04 判断合法 中序递归2
局部变量在一个方法中发生了改变不会影响其他的方法。因此要把它放到全局去看
第一种修改方式 第二种修改方式
创建一个对象而不是一个变量。Long和Integer都不行它们的值不可以发生改变一定要AtomicLong因为它可以改变。 一些小方法 134 二叉搜索树 e04 判断合法 上下界 135 二叉搜索树 e05 求范围和 第二种方法伪递归来一次 红色的是来绿色的是回紫色的是最后一步
136 二叉搜索树 e06 根据前序遍历结果建树1 137 二叉搜索树 e06 根据前序遍历结果建树2 理解
先拿个8过来确立好的左限和右限然后拿5。5小于8可以做为8的左孩子。然后拿11小于5可以做5的左孩子。然后拿7 7大于5因此1的左右孩子为null完毕。然后拿10。10超过了5的上限因此5完毕。。以此类推。。 138 二叉搜索树 e06 根据前序遍历结果建树3 139 二叉搜索树 e07 最近公共祖先 140 avl树 概述 导致失衡的原因删除添加。 141 avl树 高度和平衡因子 142 avl 四种失衡情况 对于LL和RR只要做一次旋转
LL失衡点向右旋转一次
RR失衡点向左旋转一次
对于LR和RL要做两次旋转
LR先让失衡点的右孩子左旋转再让失衡点右旋转
RL先让失衡点的左孩子右旋转再让失衡点左旋转
143 avl 旋转
要先更新红色节点才能更新黄色节点要先将下面的高度算好才可以算上面的高度这样才会准确。
