Overview
知识点：
1. delete函数的signature
public AVLTreeNode Delete(AVLTreeNode node, int key)
2. 算法，如何删除节点：
// 如果左右节点都为空，node = null // 如果一个为空，另一个字节点不为空，把node节点替换成不为空的字节点 // 如果两个节点都不为空，则要找到中序后继节点，然后去其值，再递归删掉右侧子树的后继节点
3. 旋转：
左旋和右旋逻辑和插入是一致的。
Source Code
private int GetMinValue(AVLTreeNode node)
{
if (node ==
null)
{
throw new Exception(
"node is null.");
}
if (node.rightChild !=
null)
{
AVLTreeNode temp =
node.rightChild;
while (temp.leftChild !=
null)
{
temp =
temp.leftChild;
}
// don't write it like temp.leftChild.data
return temp.data;
}
else
{
throw new Exception(
"successor node is not found");
}
}
public AVLTreeNode Delete(AVLTreeNode node,
int key)
{
// STEP 1: standard BST deletion
if (node ==
null)
{
return node;
}
if (key <
node.data)
{
node.leftChild =
Delete(node.leftChild, key);
}
else if (key >
node.data)
{
node.rightChild =
Delete(node.rightChild, key);
}
else
{ // 如果左右节点都为空，node = null // 如果一个为空，另一个字节点不为空，把node节点替换成不为空的字节点 // 如果两个节点都不为空，则要找到中序后继节点，然后去其值，再递归删掉右侧子树的后继节点if (node.leftChild ==
null || node.rightChild ==
null)
{
AVLTreeNode temp =
null;
if (node.leftChild ==
null)
{
temp =
node.rightChild;
}
else
{
temp =
node.leftChild;
}
if (temp ==
null)
{
// no child at all
node =
null;
}
// has one child
else
{
node =
temp;
}
}
else
{
// has two children
node.data =
GetMinValue(node);
node.rightChild =
Delete(node.rightChild, node.data);
}
}
// 下面这个逻辑很重要，如果node是叶子节点，直接返回，没有必要继续下去
if (node ==
null)
{
return node;
}
// STEP 2: update height， 下面逻辑和插入是一样的
node.height =
1 +
Math.Max(Height(node.leftChild), Height(node.rightChild));
// STEP 3: calculate balance factor
// after insertion, calculate the balance
int balance =
GetBalance(node);
// left left case
if (balance >
1 && node.leftChild.data >
key)
{
// right rotation
return RightRotation(node);
}
// left right case
if (balance >
1 && node.leftChild.data <=
key)
{
// left rotation first
node.leftChild =
LeftRotation(node.leftChild);
// then do right rotation
return RightRotation(node);
}
// right right case
if (balance < -
1 && node.rightChild.data <=
key)
{
// left rotation
return LeftRotation(node);
}
// right left case
if (balance < -
1 && node.rightChild.data >
key)
{
// right rotation
node.rightChild =
RightRotation(node.rightChild);
// left rotation
return LeftRotation(node);
}
return node;
}
转载于:https://www.cnblogs.com/xuyanran/p/8471325.html
相关资源：JAVA上百实例源码以及开源项目
