排序二叉树和平衡二叉树.doc

9.2.1 二叉排序树和平衡二叉树 一、二叉排序树及其查找过程 什么是二叉排序树? 二叉排序树(Binary Sort Tree)或者是一棵空树；或者是具有下列性质的二叉树：(1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3)它的左、右子树也分别为二叉排序树。 二叉排序树又称二叉查找树，根据上述定义的结构特点可见，它的查找过程和次优二叉树类似。即当二叉排序树不空时，首先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。 通常，可取二叉链表作为二叉排序树的存储结构，则上述查找过程如算法 9.5(a)所描述。BiTree SearchBST (BiTree T，KeyType key)/在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素/若查找成功，则返回指向该数据元素结点的指针，否则返回空指针 if( (!T)|EQ(key，Tdata.key) return (T)； /查找结束 else if LT(key，Tdata.key) return(SearchBST(Tlchild，key)； /在左子树中继续查找 else return(SearchBST(T rchild，key)；/ 在右子树中继续查找/SearchBST 算法 95(a)图9.7 二叉排序树示例 例如：在图9.7所示的二叉排序树中查找关键字等于100的记录（树中结点内的数均为记录的关键字）。首先以 key=100和根结点的关键字比较，因为key45，则查找以45为根的右子树，此时右子树不空，且key53，则继续查找以53为根的右子树，由于key和53的右子树根的关键字100相等，则查找成功，返回指向结点100的指针值。二、二叉排序树的插入和删除 和次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。为此，需将上一小节的二叉排序树的查找算法改写成算法9.5(b)，以便能在查找不成功时返回插入位置。插入算法如算法9.6所示。Status SearchBST(BiTree T，KeyType key，BiTree f，BiTree &p)/在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，/若查找成功，则指针p指向该数据元素结点，并返回TRUE，/否则指针p指向查找路径上访问的最后一个结点并返回FALSE，/指针f指向T的双亲，其初始调用值为NULL if(!T) p=f；return FALSE； /查找不成功 else if EQ(key, Tdata.key) p=T；return TRUE； /查找成功 else if LT(key，Tdata.key) SearchBST(Tlchild，key，T，p)； /在左子树中继续查找 else SearchBST(Trchild，key，T，p)；/在右子树中继续查找/SearchBST算法 9.5(b)Status Insert BST(BiTree &T，ElemType e)/当二叉排序树T中不存在关键字等于e.key的数据元素时,插入e并返回TRUE，否则返回FALSE if(!SearchBST(T，e.key，NULL，p) /查找不成功 s=(BiTree)malloc(sizeof(BiTNode)； sdata=e； slchild= srchild=NULL； if (!p) T = s； /被插结点*s为新的根结点 ，原树为空 else if LT(e.key，pdata.key) plchild=s； /被插结点*s为左孩子 else prchild=s /被插结点*s为右孩子 return TRUE； else return FALSE; /树中已有关键字相同的结点，不再插入/ Insert BST算法 9.6 若从空树出发，经过一系列的查找插入操作之后，可生成一棵二叉树。设查找的关键字序列为45，24，53，45，12，24，9，则生成的二叉排序树如图9.8所示。 图9.8 二义排序树的构造过程 容易看出，中序遍历二叉排序树可得到一个关键字的有序序列(这个性质是由二叉排序树的定义决定的)。这就是说，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。不仅如此，从上面的插入过程还可以看到，每次插入的新结点都是二叉排序树上新的叶子结点，则在进行插入操作时，不必移动其它结点，仅需改动某个结点的指针，由空变为非空即可。这就相当于在一个有序序列上插入一个记录而不需要移动其它记录。它表明，二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。 同样，在二叉排序树上删去一个结点也很方便。删去树上一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。 那末，如何在二叉排序树上删去一个结点呢? 假设在二叉排序树上被删结点为*p(指向结点的指针为p)，其双亲结点为*f(结点指针为f)，且不失一般性，可设*p是*f的左孩子。 下面分三种情况进行讨论： (1)若*p结点为叶子结点，即PL和PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。 (2)若*p结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树即可。显然，作此修改也不破坏二叉排序树的特性。 (3)若*p结点的左子树和右子树均不空。显然，此时不能如上简单处理。从图9.9 (b)可知，在删去*p结点之前，中序遍历该二叉树得到的序列为CLCQLQSLSPPRF，在删去*p之后，为保持其它元素之间的相对位置不变，可以有两种做法：其一是令*p的左子树为*f的左子树，而*p的右子树为*s的右子树，如图9.9(c)所示；其二是令*p的直接前驱(或直接后继)替代*p，然后再从二叉排序树中删去它的直接前驱(或直接后继)。如图9.9(d)所示，当以直接前驱*s替代*p时，由于*s只有左子树SL，则在删去*s之后，只要令SL为*s的双亲*q的右子树即可。图9.9 在二叉排序树中删除*p(a)*f为根的子树；(b)删除*p之前；(c)删除*p之后，PR作为*s右子树的情形；(d)删除*p之后，*s替代的情形 三、二叉排序树的查找分析 在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程，和给定值比较的关键字个数等于路径长度加1(或结点所在层次数)，因此，和折半查找类似，与给定值比较的关键字个数不超过树的深度。然而，折半查找长度为n的表的判定树是唯一的，而含有n个结点的二叉排序树却不唯一。例如：图9.10中(a)和(b)的两棵二叉排序树中结点的值都相同，但前者由关键字序列(45，24，53，12，37，93)构成，而后者由关键字序列(12，24，37，45，53，93)构成。(a)树的深度为3，而(b)树的深度为6。 因此，含有n个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有序时，构成的二叉树蜕变为单枝树。树的深度为n，其平均查找长度和顺序查找相同，这是最差的情况。显然，最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2n成正比。 四、平衡二叉树 平衡二叉树(Balanced Binary Tree或Height-Balanced Tree)又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF(Balance Factor)定义为该结点的左子树的深度减去它的有子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。如图9.11(a)为两棵平衡二叉树，而图9.11(b)为两棵不平衡的二叉树，结点中的值为该结点的平衡因子。图9.11 平衡与不平衡的二叉树及结点的平衡因子 我们希望由任何初始序列构成的二叉排序树都是AVL树。因为AVL树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的(其中N为结点个数)。由此，它的平均查找长度也和logN同数量级。 如何使构成的二叉排序树成为平衡树呢?先看一个具体例子(参见图9.12)。假设表中关键字序列为(13，24，37，90，53)。 图8.12 一般情况下，假设由于在二叉排序树上插入结点而失去平衡的最小根结点的指针为a(即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点)，则失去平衡后进行调整的规律可归纳为下列四种情况： (1)单向右旋平衡处理：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次向右的顺时针旋转操作。 (2)单向左旋平衡处理：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1增至-2，致使以*a为根结点的子树失去平衡，则需进行一次向左的逆时针旋转操作。 (3)双向旋转(先左后右)平衡处理：由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根结点的子树失去平衡，则需进行两次旋转 (先左旋后右旋)操作。 (4)双向旋转(先右后左)子衡处理：由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1增至-2，致使以*a为根结点的子树失去平衡，则需进行两次旋转(先右旋后左旋)操作。 上述四种情况