AA树中节点的插入或删除

AA树是在一般的二叉树结点中增加了level这一属性。同时规定:
  1、每个叶子的level是1;
  2、每个左孩子的level是其父结点的level减1;
  3、每个右孩子的level等于其父结点的level或等于其父结点的level减1;
  4、每个右孙子的level一定比其祖父的level小;
  5、每个level大于1的结点有两个孩子。
当对AA树进行节点插入或节点删除时,根据以上条件可以用来标记和调整AA树的结构,使其每个结点满足level值的规定。
左旋和右旋是用于调整AA树结构的方法,当连续三个右孩子level值相同时使用左旋操作,当连续两个左孩子level值相同时使用右旋操作。(验证时间约为 3560sec)

[Back to Index]

验证特点:AA树,内置谓词 \tree,自定义谓词,引理,逻辑变量,幽灵形参,\assert断言

标注说明:
  这里只给出插入和删除函数的简单说明,其他函数请参见各函数的标注。
  (1)插入函数 AAinsert。
    函数前条件:t是一个AA树,t和它右子树的高度(level)分别为m和n,要插入的数据为data。
        逻辑变量 oldt 记录函数入口处根节点实参的值。
    函数后条件:返回值 \result 为一个AA树。描述新节点插入后AA树的各种情况,\result 为空树、
        节点插在树根或其他中间或叶子节点。
  (2)删除函数 AAdelete。
    函数前条件:t是一个AA树,要删除节点的数据为data。
    函数后条件:返回值 \result 为一个AA树。描述节点删除后AA树的各种情况:原树为空树,
        原树只有一个节点且被删除,根节点或其它节点被删除等。


程序样例  程序下载

前往验证