说一下这个9.3 动态查找表

01

二叉排序树和平衡二叉树

1、二叉排序树及其查找过程

二叉排序树或者是一棵空树,或者是具有以下性质:

(1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值。

(2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。

(3)它的左、右子树也分别为二叉排序树。

2、二叉排序树的插入和删除

(1)和次优二叉树相对,二叉排序树是一种动态树表。其特点是,树点的结构通常不是一次生成的,而是在查找过程中,当树中不存在关键字等于给定值的结点时再进行插入。

(2)对于一般的二叉树来说,删去树中一个结点是没有意义的。因为它将使以被删结点为根的子树成为森林,破坏了整棵树的结构。然而,对于二叉排序树,删去树上一个结点相当于删去有序序列中的一个记录,只要在删除某个结点之后依旧保持二叉排序树的特性即可。

3、平衡二叉树又称AVL树,它或者是一棵空树,或者它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1.

02

B-树和B+树

1、B-树是一种平衡的多路查找树,它在文件系统中很有用。

2、在B-树上进行查找包含两种基本操作:

(1)在B-树中找结点。

(2)在结点中找关键字。

3、B+树是应文件系统所需而出的一种B-树的变型树,一棵m阶的B+树和m阶的B-树的差异在于:

(1)有n棵子树的结点中含有n个关键字。

(2)所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。

(3)所有的非终端结点可以看成是索引部分,结点中仅含有其子树中的最大关键字。

03

键树

1、键树又称数字查找树(Digital Search Trees)。它是一棵度>=2的树,树中的每个结点中不是包含一个或几个关键字,而是只含有组成关键字的符号。

2、在双链树中插入或删除一个关键字,相当于在树中某个结点上插入或删除一棵子树。

如果您觉得本篇文章对您有作用,请转发给更多的人,点一下好看就是对小编的最大支持!

正文完