12.14_黑马数据结构与算法笔记Java
目录
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.key=key就走到后面的代码去了，就不会在着三个if走。?
这一部分的代码意思是，拿原先给的图片来做例子
来一个伪递归
private BSTNode doDelete(BSTNode node,int key){
//比如我要删除的是6 key=6
if(node == null){
return null;
}
if(key < node.key){
node.left = doDelete(node.left,key);
return node;
}
if(key> node.key){ 6>4
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 key=6
if(node == null){
return null;
}
if(key < node.key){
node.left = doDelete(node.left,key);
return node;
}
if(key> node.key){ 6>4
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 key=6
if(node == null){
return null;
}
if(key < node.key){
node.left = doDelete(node.left,key);
return node;
}
if(key> node.key){ 6>4
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 key=6
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 是4，node.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的左孩子。然后拿1，1小于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 旋转
要先更新红色节点才能更新黄色节点，要先将下面的高度算好，才可以算上面的高度，这样才会准确。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！