数据结构课件-5-AA树.pptx

数据结构计算机领域本科教育教学改革试点工作计划（“101计划”）研究成果俞勇、张铭、陈越、韩文弢上海交通大学、北京大学、浙江大学、清华大学101

12.5AA树第12章高级查找戴波电子科技大学

12.5.1AA树的定义12.5.2AA树的旋转12.5.3AA树的插入12.5.4AA树的删除12.5.5AA树的作业

12.5.1AA树的定义12.5.1AA树的定义数据结构AA树具有如下性质：1.“红”结点只能作为父结点的右孩结点，“黑”结点可以作为父结点的左孩结点或者右孩结点；2.结点中的level相当于红黑树中的结点的黑高度；3.“红”结点的level与其父结点的level相同；4.“黑”结点的level比其父结点的level小1；由于红结点的level和父结点的level相同，可将双亲指向红结点的右指针画为从左向右的水平箭头，称为水平链AA树是红黑树的一种变种，每个结点没有颜色信息，而是存储的level信息（一个短整数）。

12.5.1AA树的定义12.5.1AA树的定义数据结构红黑树AA树

12.5.1AA树的定义12.5.1AA树的定义数据结构AA树是不是平衡树？AA树不可能出现哪些情况？为什么？AA树是平衡二叉树！他是红黑树的变形，且保留了红黑树的性质，所以是平衡二叉树！因为左孩子的level比父结点的level小1，所以左孩子只可能是黑色的，AA树不可能出现红左孩子。红黑树的红结点的孩子不能是红结点，因此AA树不可能有连续的红右孩子。

12.5.1AA树的定义12.5.1AA树的定义数据结构左红孩连续右红孩AA树不可能情况AA树不可能的两种情况：左红孩和连续右红孩

12.5.2AA树的旋转12.5.2AA树的旋转数据结构左红孩的处理AA树不可能情况1的处理：左红孩右旋

12.5.2AA树的旋转12.5.2AA树的旋转数据结构连续右红孩的处理：左旋AA树不可能情况2的处理：连续右红孩左旋

12.5.2AA树的旋转12.5.2AA树的旋转数据结构//算法：AA树右旋伪代码（左红孩）Skew(t)输入：AA树结点t输出：旋转后的新根结点//空树，或者无左子树，或者左子树不是红色ift=NILort.left=NILort.left.level≠t.levelthenreturntendlt←t.leftt.left←lt.rightlt.right←treturnlt

12.5.2AA树的旋转12.5.2AA树的旋转数据结构//算法：AA树左旋伪代码（连续右红孩）Skew(t)输入：AA树结点t输出：旋转后的新根结点//空树，或者没有右子树，或者没有连续右子树，//或者连续右子树都不是红色ift=NILort.right=NILort.right.right=NILort.right.right.level≠t.levelthenreturntendrt←t.rightt.right←rt.leftrt.left←trt.level←rt.level+1returnrt

1空树2结点存在3插入红左孩4插入红右孩红黑树是删除分析12.5.3AA树的插入

1空树2结点存在3插入红左孩4插入红右孩红黑树是删除分析12.5.3AA树的插入父亲是红色父亲是红色父亲是黑色父亲是黑色

12.5.3AA树的插入12.5.3AA树的插入数据结构

12.5.3AA树的插入12.5.3AA树的插入数据结构例：插入10，85，15，70，20，60，30，50，65，建立一颗AA树。

12.5.3AA树的插入12.5.3AA树的插入数据结构例：插入10，85，15，70，20，60，30，50，65，建立一颗AA树。

请写出AA树插入操作的算法描述/伪代码/代码作答主观题10分

12.5.3AA树的插入12.5.3AA树的插入数据结构//算法12-6：AA树插入操作伪代码1.InsertRecur(t,key,value)2.输入：AA树结点t，键key，值value3.输出：插入并调整后的新根结点4.ift=NILthen5.t←AANode()6.t.key←key7.t.value←value8.returnt9.elseifkey=t.keythen//key已存在，修改value10.t.va