|
|
二叉排序树又称为二叉查找树,它或者是一棵空树,或者是满足以下性质的二叉树。
|
|
|
(1)若它的左子树非空,则左子树上所有节点的值均小于根节点的值。
|
|
|
(2)若它的右子树非空,则右子树上所有节点的值均大于根节点的值。
|
|
|
|
二叉排序树的查找过程是:若二叉排序树非空,则将给定值与根节点的关键字值相比较,若相等,则查找成功;若不等,则当根节点的关键字值大于给定值时,到根的左子树中进行查找;否则到根的右子树中进行查找。若找到,则查找过程是走了一条从树根到所找到节点的路径;否则查找过程终止于一棵空树。
|
|
|
二叉排序树中插入节点的操作:每读入一个元素,建立一个新节点,若二叉树非空,则将新节点的值与根节点的值相比较,如果小于根节点的值,则插入到左子树中,否则插入到右子树中;若二叉排序树为空,则新节点作为二叉排序树的根节点。
|
|
|
二叉排序树中删除节点的操作:在二叉树中删除一个节点,不能把以该节点为根的子树都删除,只能删除这个节点并仍旧保持二叉排序树的特性,也就是说,删除二叉排序树上一个节点相当于删除有序数列中的一个元素。假设二叉排序树上的被删除节点为*p(p指针指向被删除节点),*f为其双亲节点,则删除节点*p的过程可分为以下3种情况。
|
|
|
①若*p节点为叶子节点,即p→lchild及p→rchild均为空,则由于删去叶子节点后不破坏整棵树的结构,因此只需修改*p节点的双亲节点*f的相应指针即可,即f→lchild(或f→rchild)=NULL。
|
|
|
②若*p节点只有左子树或者只有右子树,此时只要将*p的左子树或右子树接成其双亲节点*f左子树或右子树,即令f→lchild(或f→rchild)=p→lchild,或f→lchild(或f→rchild)=p→rchild。
|
|
|
③若*p节点的左、右子树均不空,则不能像上面那样简单处理,删除*p节点时应将*p的左子树、右子树连接到适当的位置,并保持二叉排序树的特性。可采用以下两种方法进行处理:一是令*p的左子树为*f的左(或右)子树,而将*p的右子树下接到*p的中序遍历的直接前驱节点*s的右孩子指针上;二是用*p的中序直接前驱(或后继)节点*s代替*p节点,然后删除*s节点。
|
|
|
|
平衡二叉树又称为AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左、右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1;若将二叉树节点的平衡因子定义为该节点的左子树的深度减去其右子树的深度,则平衡树上所有节点的平衡因子只可能是-1、0和1;只要树上有一个节点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。
|
|
|
平衡二叉树上的插入操作。失去平衡后进行调整的规律可归纳为4种情况:①单向右旋平衡处理;②单向左旋平衡处理;③双向旋转(从左到右)平衡处理;④双向旋转(从右到左)平衡处理。
|
|
|
平衡二叉树上的删除操作:若删除节点的两个子树都不为空,就用该节点左子树上的中序遍历的最后一个节点(或其右子树上的第一个节点)替换该节点,将情况转化为待删除的节点只有一个子树后再进行处理。当一个节点被删除后,从被删节点到树根的路径上所有节点的平衡因子都需要更新,对于每一个位于该路径上的平衡因子为±2的节点来说,都要进行平衡处理。
|
|
|
|
B-树的定义:一棵m阶的B-树,或为空树,或为满足下列特性的m叉树。
|
|
|
|
|
(3)除根之外的所有非终端节点至少有棵子树。
|
|
|
|
(n,A0,K1,A1,K2,A2,…,Kn,An)
|
|
|
式中,Ki(i=1,2,…,n)为关键字,且Ki<Ki+1(i=1,2,…,n-1);Ai(i=1,2,…,n)为指向子树根节点的指针,且指针Ai-1,所指子树中所有节点的关键字均小于Ki(i=1,2,…,n),An所指子树中所有节点的关键字均大于Kn,为节点中关键字的个数。
|
|
|
(5)所有的叶子节点都出现在同一层次上,并且不带信息(可以看作外部节点或查找失败的节点,实际上这些节点不存在,指向这些节点的指针为空)。
|
|
|
B-树上进行查找的过程是:首先在根节点所包含的关键字中查找给定的关键字,若找到则成功返回;否则确定待查找的关键字所在的子树并继续进行查找,直到查找成功或查找失败(指针为空)时为止。
|
|
|
B-树上的插入和删除运算较为复杂,因为要保证运算后节点中关键字的个数大于等于,因此涉及节点的"分裂"及"合并"问题。
|
|
|
在B-树中插入一个关键字时,不是在树中加一个叶子节点,而是首先在低层的某个终端节点添加一个关键字,若该节点中关键字的个数不超过m-1,则完成插入;否则,要进行节点的"分裂"处理。"分裂"就是把节点中处于中间位置上的关键字取出来插入到其父节点中,并以该关键字为分界线,把原节点分成两个节点,"分裂"过程可能会一直持续到树根。
|
|
|
在B-树中删除一个节点时,首先找到关键字所在的节点,若该节点在含有信息的最后一层,且其中关键字的数目不少于,则完成删除;否则需进行节点的"合并"运算。若待删除的关键字所在节点不在含有信息的最后一层上,则将该关键字用其在B-树中的后继替代,然后再删除其后继元素,即将需要处理的情况统一转化为在含有信息的最后一层再进行删除运算。
|
|
|