數(shù)據(jù)結構作業(yè)-d.s期終復習

D.S.復習提綱象第1章：數(shù)據(jù)，數(shù)據(jù)結構，基本類型，抽象數(shù)據(jù)類型，Java語言的面編程、遞歸的概念與實現(xiàn)。主要能用遞歸思想寫出算法例子：

ppt-----遞歸例1

求n!遞歸例2

求a0+a1+a2+……+an-1作業(yè)---------

例3

求數(shù)組中的最大值例4

求數(shù)組元素的平均值例3,例4如果用鏈表來實現(xiàn)呢？復習例題----例5統(tǒng)計二叉樹中的葉結點個數(shù)例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.

求數(shù)組中的最大值public

static

int

findMax(int[]

a,

int

n){//n表示n個元素，它們在數(shù)組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.求數(shù)組中的最大值如果用鏈表來實現(xiàn)表：求鏈表中的最大值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

.

求數(shù)組元素的平均值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統(tǒng)fN計um葉(B子in結Tr點eeN個od數(shù)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.

交換左右子數(shù)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、Ω和

θ

符號分析某個語句的執(zhí)行次數(shù)（頻度）分析某個程序段執(zhí)行的時間復雜度（用大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章，順序特殊矩陣的壓縮表頭結點用鏈表實現(xiàn)表：邏輯-----（e1,e2,…..en)物理------數(shù)組實現(xiàn)鏈表實現(xiàn)------單鏈表循環(huán)鏈表雙向鏈表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.

設有如下結構的循環(huán)鏈表和可利用空間表data

linka1….an-1L

a0Avail

…請在常數(shù)時間內實現(xiàn)將L鏈表中的所有結點歸還到可利用空間表ListNode

p

=

L.link;L.link

=

Avail;

Avail

=

p;棧、隊列（循環(huán)隊列）定義機內實現(xiàn)------數(shù)組單鏈表應用棧-----對表達式求值。中綴----后綴----對后綴表達式求值遞歸函數(shù)的實現(xiàn)。PPT：第4章中用非遞歸實現(xiàn)中序,后序遍歷(在第4章中講)隊列---循環(huán)隊列的補充題：已知隊尾元素的位置與元素的個數(shù)，求隊頭元素的位置。中綴到后綴：(a+b)*((c-d)/2*e)-----→

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

隊列---循環(huán)隊列的補充題已知隊尾元素的位置與元素的個數(shù)，求隊頭元素的位置?！?情況一: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稀疏矩陣的行數(shù)(rows),列數(shù)(cols),非零元素個數(shù)(terms),

a,

MaxTerms這種表示正如多項式的順序表示一樣，對非零元素個數(shù)在具體加,減,乘等運算時會變化，這時采用順序表示不適合，應該用鏈表來表示。而它又是二維的，每個非零元素處于某行某列，所以用

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

Linked

Representation1)對每行設置一個帶表頭結點的循環(huán)鏈表（里面連接該行的非零元素）對每列也設置一個帶表頭結點的循環(huán)鏈表（里面連接該列的非零元素）Sparse

Matrices*head是布爾型，為了區(qū)別head*down

指向下一個非零元素結點*right

指向同一行右面一個非零元素T是表頭結點F是非零元素結點* next

是諸表頭結點拉鏈在一起的指針。這里要注意，行,列鏈表表頭元素結點是合用的,因此總個數(shù)為max{行數(shù),列數(shù)}。headrowcoldownvalueright(1)

非零元素結點headnextdownright(2)

表頭元素結點(3)所有表頭結點的表頭結點headnode例子：四行0011001200000-400000000五列F6

77rows

cols非零元素個數(shù)Th0F453TTTTTheadnodeH0H1H2H3H4TTTTH0H1H2H3F

0

211F

1

012F

2

1-4習題：設有一個n*n的對稱矩陣A，如下圖(a)所示。為了節(jié)約

，可以只存對角線及對角線以上的元素，或者只存對角線或對角線以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。

把它們按行存放于一個一維數(shù)組B中，如圖(b)和圖(c)所示。并稱之為對稱矩陣A的壓縮

方式。試問：存放對稱矩陣A上三角部分或下三角部分的一維數(shù)組B有多少元素？若在一維數(shù)組B中從0號位置開始存放，則如圖(a)所示的對稱矩陣中的任一元素aij在只存上三角部分的情形下(圖(b))應存于一維數(shù)組的什么下標位置？給出計算公式。若在一維數(shù)組B中從0號位置開始存放，則如圖(a)所示的對稱矩陣中的任一元素aij在只存下三角部分的情況下*(圖(c))應存于一維數(shù)組的什么下標位置？給出計算公式。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章

樹二叉樹的定義、性質滿二叉樹與完全二叉樹的概念二叉樹的機內數(shù)組表示（完全二叉樹）、左---右拉鏈表示、cursor遞歸先序、中序、后序遍歷非遞歸層次遍歷-----用到隊列例1.

第4章中用非遞歸實現(xiàn)中序,后序遍歷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樹與森林的遍歷樹的遍歷：深度優(yōu)先遍歷，廣度優(yōu)先遍歷深度優(yōu)先遍歷先序次序遍歷（先序）樹的根

按先序遍歷根的第一棵子樹，第二棵子樹，……等。后序次序遍歷（后序）按后序遍歷根的第一棵子樹，第二棵子樹，……等樹的根。A先根：ABEFCGKLDHIJM與B

C

D

對應的二叉樹的先序一致后根：EFBKLGCHIMJDA與對應的二叉樹的中序一致E

F

G

H

I

JK

L

M7.

ApplicationDJ廣度優(yōu)先遍歷AB

CE

F

G

H

IK

LM分層

：ABCDEFGHIJKLM森林的遍歷深度優(yōu)先遍歷*

先根次序遍歷F的第一棵樹的根按先根遍歷第一棵樹的子樹森林按先根遍歷其它樹組成的森林*

中根次序遍歷按中根遍歷第一棵樹的子樹森林F的第一棵樹的根按中根遍歷其它樹組成的森林*

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

AIJHK后根：FEGDCBJHIKAABKECIF

GDHJ廣度優(yōu)先遍歷（層次遍歷）線索樹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^例子：寫一遞歸函數(shù)實現(xiàn)在帶索引的二叉搜索樹（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(huán)+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*調整只要在包含結點的最小不平衡子樹中進行,即從根到達

結點的路徑上,離

結點最近的,并且平衡系數(shù)≠0的結點為根的子樹。713調整后：樹高不變。原h(huán)+2,

后h+3,調整后h+2.小結一下：以A為根的子樹，調整前后，其高度不變，

調整不會影響到以A為根的子樹以外的結點。例如：-1155

+1010

1804

8

1106

9

1207422

524

320

8106

9

11712

沒有變化也可這樣講： 一個新結點后，需要從

位置沿通向根的路徑回溯，檢查各結點左右子樹的高度差，如果發(fā)現(xiàn)某點高度不平衡則停止回溯。單旋轉：外側—從不平衡結點沿剛才回溯的路徑取直接下兩層如果三個結點處于一直線A，C，E雙旋轉：內側—從不平衡結點沿剛才回溯的路徑取直接下兩層如果三個結點處于一折線A，C，D*以上以右外側，右內側為例，左外側，左內側是對稱的。與前面對稱的情況：左外側，左內側左外側:ABA

BhCCDDEEhhhhhA右下旋hAABBBCCDDDEEEFFAF

GGGhhhhhorh-1h-1h-1h-1h-1h-1orB左下旋A右下旋Cor左內側:從空的AVL樹建樹的算法。一個例子：7個關鍵碼發(fā)生四種轉動

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現(xiàn)要刪除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，且結點個數(shù)最少的平衡二叉樹。}h-1h-2{h假設右子樹高度為h-1因結點個數(shù)最少,左子樹高度只能是h-2這兩棵左子樹,右子樹高度分別為h-2,

h-1,也一定是結點數(shù)最少的: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樹的結點個數(shù)，則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滿足費波那契數(shù)的定義，并且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 .

..費波那契數(shù)F

i

滿足下列公式F

i

=

——(———)

-——(

———)1 1-

√5√5

2iii——(

———)相當小1-√521

1+√5√5

2∵

|1—-√—5

—

|

<1,

∴

12

√5iN

h

+1=

——

(———) +

O

(1)∵費波那契數(shù)樹是具有相同高度的所有平衡二叉樹中結點個數(shù)最少的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章：散列散列函數(shù)的選擇解決

的方法開地址法：線性探查法平方探查法二次散列鏈地址法HashFunction散列函數(shù)的選擇取余法H(

Key

)

=

Key

%

M其中：M<=基本區(qū)長度的最大質數(shù)為什么取最大質數(shù)？平方取中法H(

Key)=Key2

的中間部分，其長度取決于表的大小。設表長=29=

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

乘法雜湊函數(shù)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個字符的詞典的不同組合數(shù)只有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)//函數(shù)允許溢出，這可能會引進負數(shù)hashVal

+=

tableSize;return

hashVal;}solve

acollision1.

Open

Addressing1)

linear

ProbingIf

hash(key)=d and

the

bucket

is

alreadyoccupied then

we

will

examinesuccess