标签：avl

java中删除avl树节点方法

    在很多的数据结构书上，关于avl树，都有记录如何进行插入节点以及如何进行树的翻转操作。但对于，如何删除节点，却都是作为练习或者没有提供相应的代码以供参考。笔者，根据插入节点的实现，并部分参考网上其它c++代码，提出一个简单的删除节点的实现，并记录如下。

    删除一个节点的主要步骤如下所示：

  1. 如果是null节点，则直接返回null
  2. 如果删除的值<当前节点，则转入left节点进行递归删除
  3. 如果删除的值>当前节点，则转入right节点进行递归删除
  4. 如果删除的值为当前节点，如果当前节点只有一个子树，则直接返回该子树
  5. 如果删除的值为当前节点，且当前节点有两个子树，则将当前值更改为右子树中最小的节点值，并递归在右子树中删除该节点值
  6. 重新修正该处理节点的height值
  7. 对处理节点进行重新翻转处理，以修正在删除过程中可能出现的树不平衡情况

    经过以上的逻辑，那么实现代码就不那么困难了。简单实现如下所示：

继续阅读“java中删除avl树节点方法”

通过递归建立avl树以及如何删除节点(C++版)转

    本文转自 http://www.asiteof.me/2010/06/avl/
    用到的树的节点如下所示：

struct node{
     int data;
     int bf;
     node *lchild;
     node *rchild;
};

    其中data表示该节点存储数据，bf表示当前节点的高度，lchild指向当前节点的左儿子，rchild指向当前节点的右儿子。

    对于二叉树的建立与节点的插入在本次实验中采用递归的方法，首先找到插入节点，然后递归的判断，如果节点左儿子与右儿子的高度差大于等于2，则对该节点进行平衡调整。
    对于二叉树的删除操作，先递归的搜索要删除的节点A，用该节点的右儿子的最左儿子B代替该节点，以A的右儿子和B当前的数值作为线索继续遍历，只到找到B，删除B。然后递归的对B的祖先节点进行平衡调整，具体调整操作和二叉树的插入操作的平衡调整相同。

    对二叉树的平衡调整过程，主要包含四种旋转操作：LL，LR，RR，RL。
     LR由当前节点左儿子的一次RR旋转和当前节点的一次LL旋转构成。同理， RR由当前节点右儿子的一次LL旋转和当前节点的一次RR旋转构成。

继续阅读“通过递归建立avl树以及如何删除节点(C++版)转”