在很多的数据结构书上，关于avl树，都有记录如何进行插入节点以及如何进行树的翻转操作。但对于，如何删除节点，却都是作为练习或者没有提供相应的代码以供参考。笔者，根据插入节点的实现，并部分参考网上其它c++代码，提出一个简单的删除节点的实现，并记录如下。
删除一个节点的主要步骤如下所示：
- 如果是null节点，则直接返回null
- 如果删除的值<当前节点，则转入left节点进行递归删除
- 如果删除的值>当前节点，则转入right节点进行递归删除
- 如果删除的值为当前节点，如果当前节点只有一个子树，则直接返回该子树
- 如果删除的值为当前节点，且当前节点有两个子树，则将当前值更改为右子树中最小的节点值，并递归在右子树中删除该节点值
- 重新修正该处理节点的height值
- 对处理节点进行重新翻转处理，以修正在删除过程中可能出现的树不平衡情况
经过以上的逻辑，那么实现代码就不那么困难了。简单实现如下所示：
private Node remove(T t, Node node) {
//第1步
if(node == null)
return null;
int cmp = t.compareTo(node.t);
//第2步
if(cmp < 0) {
node.left = remove(t, node.left);
//第3步
} else if(cmp > 0) {
node.right = remove(t, node.right);
//第5步
} else if(node.left != null && node.right != null) {
node.t = findMin(node.right);
node.right = remove(node.t, node.right);
//第4步
} else {
node = node.left == null ? node.right : node.left;
}
//第6步
if(node != null)
node.height = Math.max(height(node.left),height(node.right)) + 1;
//第7步
node = rotate(node);
return node;
}
对一个节点进行翻转的代码如下所示：
private Node rotate(Node node) {
if(node == null)
return null;
if(height(node.left) - height(node.right) == 2) {
if(height(node.left.left) >= height(node.left.right))
return singleLeft(node);
else
return doubleLeft(node);
} else if(height(node.right) - height(node.left) == 2) {
if(height(node.right.right) >= height(node.right.left))
return singleRight(node);
else
return doubleRight(node);
}
return node;
}
其余代码就不再列出，如findMin方法，以及左翻转(singleLeft)，左双翻转(doubleLeft)，这些代码在《数据结构与算法 java》中均有相应实现。
ps:在前一篇 http://www.iflym.com/index.php/code/201109040001.html 有一个类似的删除c++版，但原实现相比本实现，有点复杂了。经过仔细的分析，本文中的实现，相对简单。但正确性还未验证，如果有不正确的地方，还请来信指出。
转载请标明出处:i flym
本文地址:https://www.iflym.com/index.php/code/201109040002.html