数据结构作业-d.s期终复习

D.S.复习提纲象第1章：数据，数据结构，基本类型，抽象数据类型，Java语言的面编程、递归的概念与实现。主要能用递归思想写出算法例子：

ppt-----递归例1

求n!递归例2

求a0+a1+a2+……+an-1作业---------

例3

求数组中的最大值例4

求数组元素的平均值例3,例4如果用链表来实现呢？复习例题----例5统计二叉树中的叶结点个数例6

交换每个结点的左

和右例1.

求n!factorial

function

f(n)=n!1n*f(n-1)n<=1 (base)//递归终结条件n>1

(recursive

component)//递归部分f(n)f(5)=5f(4)=5*4f(

3)=5*4*3f(2)=5*4*3*2f(1)=120static

long

factorial

(int

n){ if

(n

<=

1)return

1;else

return

n*

factorial(

n-1

)}例2 computes

thesum

of

the

elements

a[0]

througha[n-1]a[0],

a[1],

…,

a[n-2],

a[n-1]public

static

int Rsum(int[]

a

,

int

n){

if(n>0)return

Rsum(a,n-1)+a[n-1];return0;}例3.

求数组中的最大值public

static

int

findMax(int[]

a,

int

n){//n表示n个元素，它们在数组a中if(n==1){returna[0];}else{int

temp=findMax(a,n-1);return

temp>a

[n-1]?temp:a

[n-1];}}int

max(int

a[],int

n){

if(n==1)returna[0];intm=max(a,n-1);if(m>a[n-1])returnm;elsereturn

a[n-1];}例3.求数组中的最大值如果用链表来实现表：求链表中的最大值int

GetMaxInt(

ListNode

f

){

if(

f.link

=

=

NULL

)

return

f

.data

;else{ int

i

=

GetMaxInt(

f.link);if

(

i

>

f

.data

)

return

i

;else

return

f.data;}}或else

return(f.data)>(GetMaxInt(f.link))?f.data:GetMaxInt(

f

.

link

);例4

.

求数组元素的平均值float

average(

int

a[],intn){ if(n==1)return

a[0];elsereturn

(average(a,n-1)*(n-1)+a[n-1])/n;}如果用链表：float

Average(

ListNode

f,

int

n){ if(

f.link

=

=

NULL

)

return

f.data;else

return

(

Average

(

f.link,

n-1

)

*

(

n-1

)

+

f.data

)

/

n;}i例nt5le.a统fN计um叶(B子in结Tr点eeN个od数e

<Type>*

root){if

(

root

=

=

NULL

)

return

0

;if

(

root->leafchild

=

=

NULL

&&

root->rightchild

=

=

NULL

)return

1;else

return

leafNum(

root->

leftchild

)

+

leafNum

(

root->

rightchild

);}例6.

交换左右子数void

Swapchild

(

BinTreeNode

*

p

){ if

(

p

=

=NULL)

return

;BinTreeNode

*temp

=

p->left

;p->left

=

p->

right;p->

right

=

temp;Swapchild

(

p

->left

);Swapchild

(p->right

);}第2章

算法分析复杂性上界和平均复杂度的渐近分析;最佳、

和平均情况下的复杂度差异;大O、Ω和

θ

符号分析某个语句的执行次数（频度）分析某个程序段执行的时间复杂度（用大O表示，要求写出推导过程）ppt:-----对排序算法与查找算法的分析例1----for

(int

i=1;

i<=n;i++)for

(int

j

=

1;

j<=n;

j++){ c[i][j]

=

0.0;for

(

int

k

=

1;

k

<=

n;

k++)

c[i][j]

=

c[i][j]+a[i][k]*b[k][j];}第2章

算法分析例2. x=0;y=0;for

(inti

=

1;

i

<=

n;i++)for

(intj=

1;

j<=

i;

j++)for

(intk=

1;k<=

j;

k++)

x=

x+y;例3. intx=

91; int

y

=100;while(y>0){ if(x>100)

{x-=10;

y--;

}

else

x++;}1100次、结构栈，和链式结构，应用），表、栈和队列的（基本第概念3章，顺序特殊矩阵的压缩表头结点用链表实现表：逻辑-----（e1,e2,…..en)物理------数组实现链表实现------单链表循环链表双向链表cursor操作------查找、

、删除ppt----多项式相加约瑟夫问题双链表的、删除例题----逆转链表等题第3章

表例1.

逆转链表public void

inverse(

ListNode

f

){ if

(

f

=

=

NULL

)

return;ListNode p

=

f

.

link

;

pr

=

NULL;while

(

p

!

=

NULL

){ f

.

link

=

pr

;pr

=

f

;f

=p

;p

=

p

.

link

;}f

.

link

=

pr

;}第3章例2.

设有如下结构的循环链表和可利用空间表data

linka1….an-1L

a0Avail

…请在常数时间内实现将L链表中的所有结点归还到可利用空间表ListNode

p

=

L.link;L.link

=

Avail;

Avail

=

p;栈、队列（循环队列）定义机内实现------数组单链表应用栈-----对表达式求值。中缀----后缀----对后缀表达式求值递归函数的实现。PPT：第4章中用非递归实现中序,后序遍历(在第4章中讲)队列---循环队列的补充题：已知队尾元素的位置与元素的个数，求队头元素的位置。中缀到后缀：(a+b)*((c-d)/2*e)-----→

ab+cd-2/e**用了什么栈？例2.

队列---循环队列的补充题已知队尾元素的位置与元素的个数，求队头元素的位置。…….情况一:front=rear-length+1front

rear情况二:front=rear-length+1+m合并:front=(rear-length+1+m)%mfront’rearfront…….特殊矩阵的压缩Arrays

and

Matrix1D-ArrayLocation

of

the

elementLoc(a[i])=Loc(a[0])+i352749186054778341021.

One-dimensional

array1D-array

isa

limited

sequence

composed

ofn(n0)elements

whichare

ofthe

same

data

type.Forexample:0

1

2

3

4

5

6

7

8

9aSize-1i2D-ArrayTwo-dimensional

arrays

are

composed

of

nrows

and

mcolumns.a00

a01

a02……a0

m-1a10

a11

a12……a1

m-1a20

a21

a22……a2m-1………….an-10

an-11an-12…..an-1m-1A[n][m]=2D-ArrayThere

are

three

ways

to

implement

a

2D

array1)

map the

2D-array

to

a

1D-arraya00a01…a0

m-1a10a11….an-1

m-1a00

a01

a02……a0

m-1a10

a11

a12……a1

m-1a20

a21

a22……a2

m-1………….an-10

an-11an-12…..an-1

m-1Rowmajororder2D-ArrayLocationmap

:row-majororderLoc(a[i][j])=Loc(a[0][0])+[i*m+j]*l

column-major

orderLoc(a[i][j])=Loc(a[0][0])+[j*n+i]*l2D-ArrayAn

3D-Array:inta[m1][m2][m3]LocationmapLoc(a[i][j][k])=Loc(a[0][0][0])+i*m2*m3+j*m3+kMatrix1.definition:

a

m*nMatrix

is

a

table

with

mrowsandn

columns.

m

andn

are

thedimensionsofthematrix.Forexample: a5*4

matrix347209010564208273Matrix2.Matrix

can

be

implemented

with

a

twodimensional

array

:intx[m][n]

or

Array2D<int>x[m][n]use

x(i,j)

to

index

the

matrix

element,1<=i<=m,

1<=j<=nthe

private

data

member

is

rows,

cols,elementSpecial

Matrixmber

ofA

square

matrix

has

the

sarows

and

columns.Some

special

forms

of square

matrix

thatarise

frequently

are:Diagonal.

M(i,j)=0

for

i!=j;Tridiagonal.

M(i,j)=0

for|i-j|>1;Lower

triangular.

M(i,j)=0

for

i<j;Upper

triangular.

M(i,j)=0

for

i>j;Symmetric.M(i,j)=M(j,i);Special

MatrixFor

example:2000210020000100305270310000600904270(b)Tridiagonal©

Lower

Triangular(a)Diagonal240

0

0

0(d)Upper

Triangular0

5

7

0(e)SymmetricSpecial

Matrix1)Lower

Triangulara11a21

a22a31

a32

a33……an1

an2

………annLocation

map

in

row-major

order:Loc(a(i,j))=Loc(a(1,1))+[(1+2+3+……+i-1)+(j-1)]*l=Loc(a(1,1))+(i*(i-1)/2+j-1)*lSpecial

MatrixK=1i-12)Upper

Triangulara11

a12

………a1na22………a2n………..annLocation

map major

order:Loc(a(i,j))=Loc(a(1,1))+[(n-k+1)+j-i]*lSpecial

Matrix3)Tridiagonala11

a12a21

a22

a23a32

a33

a34……………an,n-1

an,nLocation

map

in

row-major

order:Loc(a(i,j))=Loc(a(1,1))+[(i-1)*3-1+(j-i+1)]*lSparse

Matrices1.Definition:An

m*n

matrix

is

said

to

be

sparse

if“many”

of

its

elements

are

zero.number

of

zero

elements>>number

of

non-zeroelementsSparse

MatricesAn

example

of

sparse

matrix:000200060070000900045000Sparse

Matrices2.Array

representation

The

nonzero

entries

of

an

sparse

matrixmay be

mapped

into

a

1D

array

in

rowmajor

order.The

structure

of

each

element

is:rowcolvalueSparse

MatricesFor

example

:9424435row

colvaluea:MaxTerms-1012000200060070000900045000Sparse

Matricesrowcolvalue稀疏矩阵的行数(rows),列数(cols),非零元素个数(terms),

a,

MaxTerms这种表示正如多项式的顺序表示一样，对非零元素个数在具体加,减,乘等运算时会变化，这时采用顺序表示不适合，应该用链表来表示。而它又是二维的，每个非零元素处于某行某列，所以用

(正交)链表表示最好。3.

Linked

Representation1)对每行设置一个带表头结点的循环链表（里面连接该行的非零元素）对每列也设置一个带表头结点的循环链表（里面连接该列的非零元素）Sparse

Matrices*head是布尔型，为了区别head*down

指向下一个非零元素结点*right

指向同一行右面一个非零元素T是表头结点F是非零元素结点* next

是诸表头结点拉链在一起的指针。这里要注意，行,列链表表头元素结点是合用的,因此总个数为max{行数,列数}。headrowcoldownvalueright(1)

非零元素结点headnextdownright(2)

表头元素结点(3)所有表头结点的表头结点headnode例子：四行0011001200000-400000000五列F6

77rows

cols非零元素个数Th0F453TTTTTheadnodeH0H1H2H3H4TTTTH0H1H2H3F

0

211F

1

012F

2

1-4习题：设有一个n*n的对称矩阵A，如下图(a)所示。为了节约

，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。

把它们按行存放于一个一维数组B中，如图(b)和图(c)所示。并称之为对称矩阵A的压缩

方式。试问：存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存上三角部分的情形下(图(b))应存于一维数组的什么下标位置？给出计算公式。若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存下三角部分的情况下*(图(c))应存于一维数组的什么下标位置？给出计算公式。a11

a12

…a1na21

a22

…a2n………..an1

an1

…ann(a)a11

a12

…a1na22

…a2n……….ann(b)a11

a21

a22………an1

an2

…

ann(c)答案：1+2+3+…+n

=

½*(1+n)*nloc(A[i,j]

)

=

loc(B[0])

+

(n+n-1+….+n-i+2

+

j-i

)t=

½*(2*n-i+2)*(i-1)

+

j-it

=½*(2*n-j+2)*(j-1)

+

i-ji<=ji>j3)

loc(A[i,j]

=

loc(B[0])+

(1+2+3+….+i-1+j-1)t

=

½*i*(i-1)

+

j-1t

=½*j*(j-1)

+

i-1i>=ji<j第4章

树二叉树的定义、性质满二叉树与完全二叉树的概念二叉树的机内数组表示（完全二叉树）、左---右拉链表示、cursor递归先序、中序、后序遍历非递归层次遍历-----用到队列例1.

第4章中用非递归实现中序,后序遍历Inorder,

Postorder

non-recursivealgorithmBCDEFG

H

IInorder

non-recursivealgorithmrootAtemplate<class

T>void

InOrder(BinaryNode<T>*t){

if(t){

InOrder(t→Left);visit(t);InOrder(t→Right);}}Inorder

non-recursivealgorithmvoid

Inorder(BinaryNode

<T>

*

t){

Stack<BinaryNode<T>*>

s(10);BinaryNode<T>

*

p

=

t;for

(

;

;

){

1)

while(p!=NULL){

s.push(p); p

=p->Left;

}2)

if

(!s.IsEmpty(

)){

p

=

s.pop(

);cout

<<p->element;p

=p->Right;}else

return;}}5.利用先序、中序可唯一构造一棵树先序：ABDCEGFHI中序：DBAEGCHFI利用中序、后序可唯一构造一棵树手工画出一棵树利用算法生成一棵树Create

BinaryTree

recursivealgorithmpreorder:ABDCEGFHIinorder:

DBAEGCHFIABCDEFG

H

ICreate

BinaryTree

recursive

algorithm

1void

CreateBT(String

pres,

ins

;

BinaryNode

<Type>*

&

t){ intinpos;String

prestemp,

instemp

;if

(pres.length(

)=

=0)

t=NULL;else

{

t=new

BinaryNode;t->element=pres.ch[0];

inpos=0;while

(ins.ch[inpos]!=t->element)

inpos++;prestemp=pres(1,inpos);instemp=ins(0,inpos-1);CreateBT(prestemp,

instemp,

t->left);prestemp=pres(inpos+1,

pres.length(

)-1);instemp=ins(inpos+1,

pres.length(

)-1);CreateBT(prestemp,

instemp,

t->right);}}Create

BinaryTree

recursive

algorithm

1public:BinaryTree(

string

pre,

string

In

){ createBT(

pre,

In,

root

);}………main(){

BinaryTree t1(

“ABHFDECKG”,

“HBDFAEKCG”

);…….}*6.

利用广义表表示来构造一棵树7.

应用树的机内表示：广义表表示、双亲表示、左---右兄弟表示ab

c

d

ef

g

h

i

jchilddatanextsiblingabcdefghij7.Application树的

方式：三种广义表表示：a(b(f,g),c,d(h,i,j),e)双亲表示法—右兄弟表示法1)

Take

a

tree

as

a

binary

tree7.

Applicationchild,

*nextsibling;class

TreeNode:Tdata;TreeNode

*class

Tree:TreeNode

*root,

*current;树-----二叉树的转换ForestBinary

treeForestAHBCBinarytreeFD

GIJEK7.

Application每棵树转为二叉树AFHBGICKJDE把每棵二叉树根用右链相连ABFCGHDIERJBinarytreeForestABFCGHDIERJ7.

Application树与森林的遍历树的遍历：深度优先遍历，广度优先遍历深度优先遍历先序次序遍历（先序）树的根

按先序遍历根的第一棵子树，第二棵子树，……等。后序次序遍历（后序）按后序遍历根的第一棵子树，第二棵子树，……等树的根。A先根：ABEFCGKLDHIJM与B

C

D

对应的二叉树的先序一致后根：EFBKLGCHIMJDA与对应的二叉树的中序一致E

F

G

H

I

JK

L

M7.

ApplicationDJ广度优先遍历AB

CE

F

G

H

IK

LM分层

：ABCDEFGHIJKLM森林的遍历深度优先遍历*

先根次序遍历F的第一棵树的根按先根遍历第一棵树的子树森林按先根遍历其它树组成的森林*

中根次序遍历按中根遍历第一棵树的子树森林F的第一棵树的根按中根遍历其它树组成的森林*

后根次序遍历按后根遍历第一棵树的子树森林按后根遍历其它树组成的森林F的第一棵树的根二叉树的先序二叉树的中序二叉树的后序AKBCDIHEFGJ先根：ABEFCGDKIHJ中根：EFB

AIJHK后根：FEGDCBJHIKAABKECIF

GDHJ广度优先遍历（层次遍历）线索树Thread

Tree1.Purpose:Thread

Tree

Representationleft

ThreadTree

and

right ThreadTreeThread

Tree

class1.Purpose:Example：ABCDEFG

H

JThread

TreeABC^DEFGHJ

^Inorder:DBAEGCHFJThread

Treeroot2.

机内如何一个结点增加两个标记域：leftchildleftthreaddatarightthread

rightchildleftchild

指向左leftThread=

=leftchild

指向前驱（某线性序列）rightchild

指向右rightThread

==rightchild

指向后继3.

线索化二叉树的类

。template<

class

Type>

class

ThreadNode{friendclass

ThreadTree;private:intleftThread,rightThread;ThreadNode<Type>*

leftchild,

*rightchild;Typedata;public:ThreadNode(const

Type

item):

data(item),leftchild(0),rihgtchild(0),

rightThread(0),

rihgtThread(0)

{

}};template<

class

Type>

class

ThreadTree{public://

线索二叉树的公共操作private:ThreadNode<Type>

*root;ThreadNode<Type>

*current};ThreadTreeleftthreadTreerightthreadTree哈夫曼树哈夫曼树的构造哈夫曼编码扩充的二叉、三叉、….、t叉树15,

3,

14,

2,

6,

9,

16,

17

构造扩充的三叉树。等价类问题PPT第8章第4.1章：二叉搜索树二叉搜索树的概念带索引的二叉搜索树的概念AVL树-----平衡的二叉搜索树B-树1. Binary

Search

TreesDefinition:

A

binary

search

tree

is

a

binary

tree

that

may

beempty.A

nonempty

binary

search

tree

satisfies

thefollowingproperties:Every

element

hasakey

and

no

two

elements

have

thesamekey;

therefore,all

keys

are

distinct.The

keys(if

any)in

the

left

subtree

of

the

root

are

smallerthan

the

key

intheroot.The

keys(if

any)in

the

right

subtree

of

the

root

are

largerthan

the

key

intheroot.The

left

and

right

subtrees

of

the

root

are

also

binarysearchtrees.Binary Search

TreesExample:45125390781006124373leftelementrightBinary

Search

Trees主要操作：查找、、删除1816

202917

23213230

3533indexed

Binary

Search

TreesAn

indexed

binary

search

tree

is

derivedfroman

ordinary

binary

search

tree

by

adding

thefield leftSize

toeach

treenode.Value

inLeftsize

field=number

of

the

elementsin

the

node’s

left

subtree

+1leftSizeleftelementrightindexedBinary Search

TreesIndexed

binary

search

treeExample:4202151^251^18^1^12^1^30^例子：写一递归函数实现在带索引的二叉搜索树（IndexBST)中查找第k个小的元素。public

Comparable

findK(

BinaryNode

root,

int

k){if(root==null)

return

null;//空if(k<root.leftSize)//在左子树findK(

root.

left,k);else

if(k>root.leftSize)//在右子树findK(

root.

right,

k-root.

leftSize);//注意减去elsereturn

roo

ement;}TL(leftAVL树----平衡的二叉搜索树Definition

of

an

AVL

tree:is

a

binary

searchtreeEvery

nodesatisfies|hL-hR|<=1

where

hL

and

hR

are

theheights

ofsubtree)

and

TR(right

subtree),respectively.1312202224155

+110

18-14

8

11060-1AVL

TreeHeightofan

tree:the

longest

path

from

theroot

toeach

leafnodeBalance

factor

bf(x)

of

a

node

x:height

of

right

subtree

of

x

–

height

of

leftsubtree

of

xLeftdataRight

balance(height)Each

node:AVL

TreeThe

height

of

an

AVL

tree

with

n

elements

isO(log2

n),

so

an

n-elementAVL

search

tree

canbe

searched

in

O(log2

n)time.AVL

Treeinserting

into

an

AVL

treeAVL

Tree•DEhhhA

+C0BC的右子树

外侧加高(对A而言)单旋转(左)调整后:树高不变.原h+2,后h+3,调整后h+2,不平衡不会向外传递.+AABBCCDDEEhhhhh}}h+1h+1情况1:A121112情况2：C右下旋A左下旋AABBABCCDDEEEDGGFFCF

Ghhhhhhh-1h-1h-1h-1h-1h-1orororAAC的左子树—内侧加高（对A而言）双旋转（先右后左）1AD167D8D8C108

11C107

9

119

1212C109

11125A左旋转7C右旋转7*调整只要在包含结点的最小不平衡子树中进行,即从根到达

结点的路径上,离

结点最近的,并且平衡系数≠0的结点为根的子树。713调整后：树高不变。原h+2,

后h+3,调整后h+2.小结一下：以A为根的子树，调整前后，其高度不变，

调整不会影响到以A为根的子树以外的结点。例如：-1155

+1010

1804

8

1106

9

1207422

524

320

8106

9

11712

没有变化也可这样讲： 一个新结点后，需要从

位置沿通向根的路径回溯，检查各结点左右子树的高度差，如果发现某点高度不平衡则停止回溯。单旋转：外侧—从不平衡结点沿刚才回溯的路径取直接下两层如果三个结点处于一直线A，C，E双旋转：内侧—从不平衡结点沿刚才回溯的路径取直接下两层如果三个结点处于一折线A，C，D*以上以右外侧，右内侧为例，左外侧，左内侧是对称的。与前面对称的情况：左外侧，左内侧左外侧:ABA

BhCCDDEEhhhhhA右下旋hAABBBCCDDDEEEFFAF

GGGhhhhhorh-1h-1h-1h-1h-1h-1orB左下旋A右下旋Cor左内侧:从空的AVL树建树的算法。一个例子：7个关键码发生四种转动

A，

Z，

C，

W，

D，

X，

YA

AZCA右双旋转Z

AZ

A

ZWCC右内DCA

ZW左外右单旋转ACD

ZW左单旋转ACCDZX右外ZA

D

XWW左双旋转Y左内CYCA

DZXA

D

X

ZWWAVL

Tree：正确寻找最小不平衡子树判别外侧（左、右）一次旋转、内侧（左、右）二次旋转前面的例子：A,Ｚ,C,Ｗ,D,Ｘ,YAVL树的删除：方法：与二叉搜索树的删除方法一样。假设被删除结点为W,它的中序后继为X,则用X代替W,并删除X.所不同的是:删除X后,以X为根的子树高度减1,这一高度变化可能影响到从X到根结点上每个结点的平衡因子,因此要进行一系列调整。

WX

例子:bacefd

ghki

lmpo

srj

n

q

t现要删除Cab右内dfe

gh1)db

fhiklme

g

j

nopstrqa右内2)bdhf

i

ljktnpo

qra

e

g

m

s因为删除操作,不平衡要传递，所以设置一个布尔变量shorter来指明子树的高度是否被缩短。在每个结点上的操作取决于shorter的值和结点的平衡因子，有时还要依赖

的平衡因子。AVL树的算法分析具有n个结点的平衡二叉树（AVL），进行一次

或删除的时间

情况≦O（log2

n)证明：实际上要考虑n个结点的平衡二叉树的最大高度≦(3/2)log2

(n+1)设T

h

为一棵高度为h，且结点个数最少的平衡二叉树。}h-1h-2{h假设右子树高度为h-1因结点个数最少,左子树高度只能是h-2这两棵左子树,右子树高度分别为h-2,

h-1,也一定是结点数最少的:T

3n

=7T

1n

=2

T

2n

=4h

=2

h

=3

h

=4T

4

n

=12

h

=0

h

=1

T

0n

=1以上五棵平衡二叉树，又称为Fibonacci树。也可以这样说一棵高度为h的树，其右子树高度为h-1的Fibonacci树，左子树是高度为h-2的Fibonacci树，即Th-2

Th-1假设N

h表示一棵高度为h的Fibonacci树的结点个数，则N

h=Nh-1+

Nh-2+

1N

0

=1,N

1=2,N

2=4,N

3=7,N4

=12, ...N

0

+1=2

,N

1+1=

3,N2

+1=

5,N

3+1=

8,N4

+1=

13, ...

N

h+1满足费波那契数的定义，并且N

h+1=

F

h+3f

0

f

1

f

2

f

3

f

4

f

5

f

6

...0

1

1

2

3

5

8 .

..费波那契数F

i

满足下列公式F

i

=

——(———)

-——(

———)1 1-

√5√5

2iii——(

———)相当小1-√521

1+√5√5

2∵

|1—-√—5

—

|

<1,

∴

12

√5iN

h

+1=

——

(———) +

O

(1)∵费波那契数树是具有相同高度的所有平衡二叉树中结点个数最少的log

—1+—√521+√52(

1+√5——2

—

) +

O(

1

)1√5n

+1≥Nh

+1=

——1√51∴ h≤————

log(n+1)+0(1)≈—3

log

(n+1)2h+3222h+3AVL

Tree关键码为{16，3，7，11，9，28，18，例子：对一棵空的AVL树，分别画出14，15}后的AVL树。4.

B-树（外查找）B-Trees

oforder

m70年

R.Bayer

。Definition

:

AB-treeof

ordermis

anm-way

searchtree.

If

the

B-tree

is

not

empty,

thecorrespondingextended tree

satisfies

the

followingproperties:the

roothas

atleast

twochildren

all

internal

nodes

other

than

the

root

haveat

least

m/2

childrenall

external

nodes

are

at

the

samelevelB-treesexample10

802

4

62030

40506070 82848688123a

B-tree

of

order

7B-treesexample30204010

152535

45

50h-1levelsLevel

hA

B-tree

of

order

3B-treesB-TREES

Properties:all

external

nodes

are

on

thesame

levelnumber

of

external

nodes=number

of

keywords

+1proof:B-treesSearching

a

B-Tree

AB-tree

is

searched

using

the

same

algorithm

asused

for

an

m-way

search

tree.

Algorithm ysis:

the

numberof

disk

access

isat

mosth(h

is

the

height

of

the

B-Tree).proof:

T

is

a

B-Tree

of

order

m

with

height

h,

numberof

elementsin

Tis

n,each

timewe

read

a

nodeintomemory.

The

n+1

external

nodesare

on

level

h.B-treesNumber

ofnodes

on

the

each

level

oftheB-Treeis:…………….Level

0

1Level

1

>=2Level

2

>=2m/2Level

3

>=2m/22Level

h >=

2m/2h-1B-treesn+1>=

2m/2h-1

,(n+1)/2>=m/2h-1

,h-1<=log

m/2

(n+1)/2,logm(n+1)<=h<=1+logm/2

(n+1)/2In

thecase

that

eachnode

has

m

childrenExample:n=2*106,

m=199thenh<=1+log100(102)3=4search

one

from

200

branchesB-trees2)

Inserting

into

a

B-Treealways

happenatonelevel

above

theexternalnodesB-treesCase

1:number

ofchildren

inthe

node<m,insert

into

the

node

as

ordered10

802

4

62030

4050607082848688A

B-Tree

of

order

7Insert

3B-trees10

802

3

4

62030

405060

70828486

88B-treesCase2.Insert

into

a

node

with

m

children

(also

called a

fullnode), like

insert

25into

theB-Tree

in

the

lastexample,the

full

node

is

split

into

two

nodes.A

new

pointer

will

be

added

to

the

parent

of

the

fullnode

.Because

km/2

is

inserted

into

parent

node,

it

may

causenew

split.

If

the

root

is

split,the

height

of

the

tree

willincreased

by

1.B-treesExample:Insert

4430802050609010253540

55708285

95A

B-Tree

of

order

3B-trees802060901055708285

9525

35

44403050B-treesAnother

example:aB-tree

of

order

5

:insert

k,m,j,e,s,i,r,x,c,……a

b

f

gAlgorithm

yses:If

theinsert

operation

causes

s

node

tosplit,the

number

ofdisk

access

ish

(to

read

in

the

nodes

on

the

search

path)+2s

(to

write

out

the

two

split

parts

ofeachnode

that

issplit)+1

(to

write

the

new

node).B-trees3)deletion

froma

B-TreeTwocases:

The

element

to

be

deleted

is

in

a

node

whosechildrenare

external

nodes(i.e.the

element

is

in

aleaf)The

element

is

to

be

deleted

from

anonleaf.B-treesa)

the

elementto

be

deletedis

in

aleafCase1: delete

it

directly

if

it

is

in

a

nodewhich

has

morethan

m/2

childrenCase2:

if

it

is

in

a

node

which

has

m/2children,after

deletion,the

number

of

children(m/2-1)

isnot

suitable

for

a

B-Tree①

borrow

an

element

from

the

its

nearestsibling

ifcan, and

do

some

adjusting.B-treesExample:

delete

379283

353

401307

313

331

347 367

379

389283

347

401307

313

331353

367

389A

B-TREE

of

order

7B-trees②

If

nearest

left

or

right

sibling

both

onlyhasm/2

children,

then

merge

themAfter

deletion

,merge

the

node

and

itssiblingwith

the

element

between

them

inthe

parentinto

a

single

nodeMaybe

cause

new

merge

in

parent

nodesThe

height

of

the

tree

will

deceased

by

one

ifrootismerged.B-treesExample:a

B-Tree

oforder

7,delete

431283353

401367379

389419

431

439B-treesdelete

a

key

in

a

node

in

the

above

levelDelete

itReplace

it

with

the

smallest

key

in

the

rightsubtree

or

the

largest

key

in

the

leftsubtreeBecause

delete

a

key

in

the

leaf

node

,

dotheadjust

mentionedin

a)B-treesExample:3080205060851025354055

70

82

90A

B-TREE

of

order

3Delete

80,

then

replace

it

with

82

or

70,

delete

82

or

70

at

lastB-tree例子：1.

分别delete

50

,40

in

the

following

3阶B-树.503060802040

55

70

95B-tree2.

分别画出65,

15,

40,

30后的3阶B-树。554580

9025

3550

60

708595第5章：散列散列函数的选择解决

的方法开地址法：线性探查法平方探查法二次散列链地址法HashFunction散列函数的选择取余法H(

Key

)

=

Key

%

M其中：M<=基本区长度的最大质数为什么取最大质数？平方取中法H(

Key)=Key2

的中间部分，其长度取决于表的大小。设表长=29=

(512)10地址000~777(八进制）(2061)84310541(2062)84314704(2161)84734741(2162)84741304(1100)81210000HashFunction3.

乘法杂凑函数H(

Key

)

=

M

*

((

*

Key

)

%

1

)

例：设表长

=

29

=

(512)10

地址

000~777(八进制），则H(

1

)

=

29

*

(

0.618

)10

=

29

*

(

0.4743…)8

=

474HashFunction书中

1.

Hash1:to

add

up

the

ASCII(

or

Unicode

)

value

of

the

characters

inthe

string.public

static

int

hash(

String

Key,

int

tableSize

){ int

hashVal

=

0;for(

int

i

=

0;

i

<

Key.length(

);

i++

)hashVal

+=

Key.charAt(

i

);return

hashVal

%

tableSize;}Example:Suppose TableSize

=

10007,Suppose

all

the

keys

are

eight

or

fewer

characters

long,hash

function

typically

can

only

assume

value

between

0~1016引起浪费HashFunction2.

Hash2:hkey

=

k0

+

27*k1

+

272*k2public

static

int

hash(

String

key,

int

tableSize

){ return

(

key.charAt(

0

)

+

27

*

key.charAt(

1

)

+729

*

key.

charAt(

2

)

)

%

tableSize;}TableSize

=

10007example:key

=

“abcmnxyz”

;H(“abc”)

=

?因3个字符的词典的不同组合数只有2851，因此真正用到表的28%Hash

Function3.

Hash3:hkey

=

k0

+

37k1

+

372k2+…..public

static

int

hash(

String

key,

int

tableSize

)

//

good

hash

fanction{ int

hashVal

=

0;for(

int

i

=

0;

i

<

key.length(

);

i++

)

hashVal

=

37

*

hashVal

+

key.charAt(

i

);hashVal

%=

tableSize;if(

hashVal<0)//函数允许溢出，这可能会引进负数hashVal

+=

tableSize;return

hashVal;}solve

acollision1.

Open

Addressing1)

linear

ProbingIf

hash(key)=d and

the

bucket

is

alreadyoccupied then

we

will

examinesuccess