《《数据结构》陈慧南_第07章搜索树》由会员分享，可在线阅读，更多相关《《数据结构》陈慧南_第07章搜索树（66页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构 Data Structures in C+Data Structures in C+第第7 7章章 动态集和搜索树动态集和搜索树 7.1 二叉搜索树 7.2 二叉平衡树 7.3 B-树7.1 7.1 二叉搜索树二叉搜索树7.1.17.1.1 二叉搜索树的定义二叉搜索树的定义定义定义7.1 7.1 设结点由关键字值表征，假定所有 结点的关键字值各不相同，二叉搜索树或 者是一棵空二叉树，或者是具有下列性质 的二叉树： （1）若左子树不空，则左子树上所有结点 的关键字值均小于根结点的关键字值； （2）若右子树不空，则右子树上所有结点 的关键字值均大于根结点的关键字值； （3）左、右
2、子树也分别是二叉搜索树。 性质性质7.17.1 若以中序遍历一棵二叉搜索树，将 得到一个以关键字值递增排列的有序序列 。二叉搜索树类二叉搜索树类 templatetemplateclass class BSTree BSTree:public:public DynamicSet DynamicSet public: public:BSTree()root=NULL; ResultCode Search(TResultCode Insert(TResultCode Remove(Tprotected:BTNode* root;private: private:ResultCode Search(
3、BTNode *p,T; ; 7.1.2 二叉搜索树的搜索 二叉搜索树搜索递归算法 template ResultCode BSTree:Search(T template ResultCode BSTree:Search(BTNode *p,T else if (xelement) return Search(p-lChild,x);else if(xp-element) return Search(p-rChild,x);else x=p-element;return Success; 二叉搜索树搜索迭代算法 template ResultCode BSTree:Search(Twhile
4、 (p) if ( xelement) p=p-lChild;else if(xp-element) p=p-rChild;else x=p-element; return Success;return NotPresent; 7.1.37.1.3 二叉搜索树的插入二叉搜索树的插入template ResultCode BSTree:Insert(T while (p) q=p; if (xelement) p=p-lChild; else if(xp-element) p=p-rChild;else x=p-element;return Duplicate; p=newp=new BTNod
5、e BTNode(x);(x); if(!root!root) root=p; else if(xelement) q-lChild=p; else q-rChild=p; return Success; 7.1.4 二叉搜索树的删除l l若结点若结点* *p p有两棵非空子树有两棵非空子树需搜索*p的中序遍历次序下的直接后继（ 或直接前驱）结点，设为*s，将*s的值复 制到*p中，称为替代替代，因为*s最多只有一 棵非空子树，这样一来，问题转化为“被 删除的结点最多只有一棵非空子树”的情 形。若结点若结点* *p p 只有一棵非空子树或只有一棵非空子树或* *p p是叶子是叶子 以*p的惟一
6、孩子（设为*c）或空子树（c NULL）取代*p，链接至*p的双亲结点*q。若被删除的结点*p是根结点，则删除后，结 点*c成为新的根；若*p是其双亲*q的左孩子 ，则*c也应成为*q的左孩子，否则*c成为*q 的右孩子。最后释放结点*p所占用的空间。删除删除2828template ResultCode BSTree:Remove(Twhile (p if (xelement) p=p-lChild;else p=p-rChild;if(!p) return NotPresent;x=p-element; if (p-lChild r=p;while (s-lChild) r=s;s=s-l
7、Child;p-element=s-element; p=s;q=r;p=s;q=r; if (p-lChild) c=p-lChild; /删除结点else c=p-rChild; if(p=root) root=c; else if (p=q-lChild) q-lChild=c; else q-rChild=c;delete p;return Success; 7.1.57.1.5 平均情况时间分析平均情况时间分析l二叉搜索树搜索的平均时间为O(log2n)。 l最坏情况搜索时间为O(n)。l假设在一个有n(nn(n 1)1)个关键字的序列，有i 个关键字小于第一个关键字，n-i-1个关
8、键 字大于第一个关键字。由此序列构成的二 叉搜索树，其左子树上有i个结点，而右子 树上有n-i-1个结点。l设p pi i(n)(n)是在一棵有n结点，其左子树上有i 个结点，而右子树上有n-i-1个结点的二叉 搜索树上以等概率进行搜索，成功搜索一 个关键字的平均比较次数。 设p(n)是在一棵有n个结点的二叉搜索树上 成功搜索一个关键字的平均比较次数 。可用归纳法证明：可用归纳法证明：随机情况下，二叉搜索树树操作的平均时间为时间为 O(log2n)。7.2 7.2 二叉平衡树二叉平衡树7.2.17.2.1 二叉平衡树的定义二叉平衡树的定义定义定义7.27.2 二叉平衡树又称二叉平衡树又称AVL
9、AVL树树它或者是一棵空二叉树，或者是具有下列性质的二 叉树：（1）其根的左、右子树高度之差的绝对值不超过1；（2）其根的左、右子树都是二叉平衡树。 结点的平衡因子定义为该结点的左子树的高度减去 右子树的高度。 AVLAVL二叉搜索树二叉搜索树既是二叉搜索树又是AVL树。在下 面的讨论中，二叉平衡树（AVL树）是指AVL二叉 搜索树。9.2.29.2.2 二叉平衡树类二叉平衡树类template struct AVLNode AVLNode(const T lChild=rChild=NULL; bFbF=0;=0;T element;int bFint bF; ; AVLNode* lChi
10、ld,*rChild; ;templatetemplate classclass AVLTree AVLTree:public:public DynamicSet DynamicSet public:public:AVLTree()root=NULL; ResultCode Search(T ResultCode Insert(TResultCode Remove(Tprivate:private:AVLNode* root;ResultCode Insert(AVLNode* void LRotation(AVLNode* void RRotation(AVLNode* ;7.2.3 二叉平
11、衡树的平衡旋转 分别插入：25，35，14，44l 插入插入2525：从根到25的路径上，所有结点的平衡 因子均为0。插入新元素25后，这棵树仍然是二 叉平衡树，但整棵树高度加1。 l 插入插入3535：从根到35的路径上，36的平衡因子不 为0，新元素35被插在36的较矮的子树上。插入 后，该树仍然是二叉平衡树。插入插入1414：从根到14的路径上，12的平衡因子不为0，新 元素14被插在12的较高的子树上，即14被插在12的右 子树的左子树上，插入后，该树不再是二叉平衡树。插入插入4444：从根到44的路径上，43和56的平衡因子都不 为0，其中56是离44最近的，平衡因子值不为零的结点
12、。新元素44被插在56的较高的那棵子树上，即44被插 在56的左子树的左子树上。插入后，该树不再是二叉 平衡树。假定新结点*q插在结点*s的左子树上的情况 （1）新结点*q已按二叉搜索树方式插入树中；（2）结点*s是新结点*q的具有非零平衡因 子值(插入前的值)的最近的祖先；（3）结点*q插在结点*s的左子树上；（4）从结点*s到新结点*q的路径上所有结 点（不含*s）的平衡因子值均已作修正。情况一若插入前，从根结点到新结点q的插入位置 的路径上，所有结点的平衡因子值均为0，插入q 后，只需将根结点的平衡因子改为1，并且AVL树 的高度加1，插入操作完成。 情况二若新结点q插在结点s较矮的子树
13、上（s的 平衡因子bF为-1，并假定q插在s的左子树上） ，则插入后只需令s的平衡因子bF为0，插入算 法终止。 情况三: 插在较高的子树上（s-bF=+1） LL-旋转（r-bF=+1）LR-旋转（r-bF=-1）switch(u-u-bFbF)case 1:s-bF=-1;r-bF=0;break;case 0:s-bF=r-bF=0;break;case -1:s-bF=0;r-bF=1; template void AVLTree:LRotation(AVLNode* if (r-bF=1) / LL / LL 旋转旋转s-lChild=r-rChild; r-rChild=s;s-b
14、F=0;s=r; else / LR/ LR旋转旋转u=r-rChild;r-rChild=u-lChild;u-lChild=r;s-lChild=u-rChild;u-rChild=s;switch(u-bF)case 1:s-bF=-1;r-bF=0;break;case 0:s-bF=r-bF=0;break;case -1:s-bF=0;r-bF=1;s=u; /s指示新子树的根 s-bF=0; /结点s的平衡因子为0unBalanced=false; /结束重新平衡操作 7.2.4 二叉平衡树的插入 二叉平衡树的插入template ResultCode AVLTree:Insert(AVLNode* if (p=NULL) /插入新结点p=new AVLNode(x);unBalanced=true; elseif (xelement) /（ 续）result=Insert(p-lChild,x,unBalanced);if (unBalanced)switch (p-bF)case -1:p-bF=0; unBalanced=false;break;case 0:p-bF=1;break;case 1:LRotation(p,unBalanced);else if (x=p-elemen
