01二叉排序树和平衡二叉树
1、二叉排序树及其查找过程
二叉排序树或者是一棵空树,或者是具有以下性质:
(1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值。
(2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。
(3)它的左、右子树也分别为二叉排序树。
2、二叉排序树的插入和删除
(1)和次优二叉树相对,二叉排序树是一种动态树表。其特点是,树点的结构通常不是一次生成的,而是在查找过程中,当树中不存在关键字等于给定值的结点时再进行插入。
(2)对于一般的二叉树来说,删去树中一个结点是没有意义的。因为它将使以被删结点为根的子树成为森林,破坏了整棵树的结构。然而,对于二叉排序树,删去树上一个结点相当于删去有序序列中的一个记录,只要在删除某个结点之后依旧保持二叉排序树的特性即可。
3、平衡二叉树又称AVL树,它或者是一棵空树,或者它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1.
02B-树和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、在双链树中插入或删除一个关键字,相当于在树中某个结点上插入或删除一棵子树。
热门跟贴