回 帖 发 新 帖 刷新版面

主题:求B-树的删除算法

题目五:图书管理系统(查找应用)
[问题描述]
图书管理基本业务活动包括:对一本书的采编入库、清除库存、借阅和归还等等。试设计一个图书管理系统,将上述业务活动借助于计算机系统完成。
[实现提示]
1、    每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。
2、    由于图书管理的基本业务活动都是通过书号(即关键字)进行的,所以要用B树(2-3树)对书号 索引,以获得高效率。
3、    系统应实现的基本功能有:
。采编入库:新购入一种书,经分类和确定书号之后登记到图书帐目中去。如果这两种书在帐中已有,则只将总库存量增加。
。清除库存:某种书已无保留价值,将它从图书帐目中注销。
。借阅:如果一种书的现存量大于零,则借出一本,登记借阅者的图书证号和归还期限。
。归还:注销对借阅者的登记,改变该书的现存量。
。显示:以凹入表的形式显示B树。这个操作是为了调试和维护的目的而设置的。

以上是我们课程设计的题目,因为要求用B树优化查找,所以看了些资料,但只找到查找和插入的算法,没有删除的算法..如果哪位朋友有B-树的删除算法,请跟贴回复.感激不尽

回复列表 (共1个回复)

沙发


删除:从二树里删除一个结点时,不能把以这个结点为根的子树都删除掉,只能删除掉这一个结点,并且还要保持二叉搜索树原来的性质。
      设p,p1,r是指针变量,p↑表示要删除的结点,p1↑表示p↑的父母结点,则删除可以按如下规定进行:若结点p↑没有左子树,则用右子树的根代替被删除的结点p↑。若结点p↑有左子树,则在左子树里找按中序周游的最后一个结点r↑,将r↑的右指针置成指向p↑的右子树的根,然后用结点p↑的左子树的根去代替被删除的结点p↑。
      改进的删除算法:设p,p1,r是指针变量,p↑表示s要删除的结点, p1↑表示p↑的父母结点,则删除可以按如下规定进行。若结点p↑没有左子树,则用右子树的根代替被删除的结点p↑。若结点p↑有左子树,则在左子树里找按中序周游的最后一个结点r↑,将r↑的右指针置成指向p↑的右子树的根,然后用结点r↑去代替被删除的结点p↑。

我来回复

您尚未登录,请登录后再回复。点此登录或注册