二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(25)

平衡因子和平衡二叉树(L树)

平衡因子：左子树深度 ? 右子树深度。

平衡二叉树中各个结点的平衡因子只能是0，1，-1。

构造平衡二叉排序树

思路：按照建立二叉排序树的方法逐个插入结点，失去平衡时作调整。

23

失去平衡时的调整方法：

1) 确定性结点。(A是失去平衡的最小子树的根；B是A的孩子；C是B的孩子，也是新插入结点的子树)。关键是找到失去平衡的最小子树。

2) 根据性结点的相对位置(C和A的相对位置)判断是哪种类型(LL, LR, RL, RR)。 3) 平衡化。“先摆好性结点(居中者为根)，再接好其余子树(根据大小)”。

例：给定关键字的序列{13，24，37，90，53，40}，建立平衡二叉排序树。 注意：失去平衡时先确定失去平衡的最小子树，这是关键，然后判断类型（LL，LR，RL，RR），再平衡化处理。

分析

查找 (同二叉排序树) 平均查找长度ASL

结论：平均查找性能O(log n)。 23

这里没有使用课本上“旋转”的概念，这只是做题的方法，并不是正规的算法描述。

为求得n个结点的平衡二叉树的最大高度，考虑高度为h的平衡二叉树的最少结点数。

? 0, h?0 ? Nh?? 1, h?1

? N?N?1, h?2

k-2?k-1

部分结果如下，Fh表示斐波纳契数列第h项。

表 错误！文档中没有指定样式的文字。.13 平衡二叉树的高度和结点个数

观察可以得出Nh = Fh+2 ? 1, h≥0。解得

h?log?((n?1))?2?1.44 log (n?1)-0.328

其中??(?1)/2。

时间复杂度

一次查找经过根到某结点的路径，所以查找的时间复杂度是O(log n)。

+

B-树和B树

B-树

一棵m阶B-树，或为空树，或满足： (1) 每个结点至多有m棵子树；

(2) 若根结点不是叶子，则至少有两棵子树； (3) 除根之外的所有非终端结点至少有?m/2?棵子树；

(4) 所有非终端结点包含n个关键字和n+1棵子树：(n, A0, K1, A1, ..., Kn, An)，其中关键字满足A0<K1<A1<...<Kn<An，关键字的个数?m/2??1?n?m?1。 (5) 所有叶子在同一层，不含信息，表示查找失败。

B树

B+树和B-树的差异：n棵子树的结点中含有n个关键字；所有叶子结点中包含了全部关键字，且按大小顺序排列；所有非终端结点都是索引。 对B+树既可以进行顺序查找又可以进行随机查找。 键树

又叫数字查找树。

常见的两种存储结构：孩子兄弟链表，多重链表。 哈希表

24

+

解斐波纳契递推式代入得

?1???Nh?n?

????

?1??

??

h?2

?

?????1??

??

h?2

?1?n?????1?????

????

?1??

??

h?2

?1?

1?

h?2

?1,其中??

?1

然后整理，取对数可解得h。

哈希表(散列表，杂凑表)

根据设定的哈希函数和处理冲突的方法，将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的象作为记录在表中的存储位置，这种表称为哈希表，又叫散列表，杂凑表。

哈希函数

常用除留余数法。H(key) = key MOD p。

冲突

什么是冲突？H(key1)=H(key2)，且key1≠key2，称冲突。

处理冲突的方法：当H(key)处已有记录，出现冲突，如何处理？

开放定址法

试用H(key)?di，常见以下三种。

(1) 线形探测再散列：试用H(key)?1，H(key)?2，...

2222(2) 二次探测再散列：试用H(key)?1，H(key)?-1，H(key)?2，H(key)?-2，...

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-25.html