數(shù)據(jù)結(jié)構(gòu)作業(yè)-d.s期終復(fù)習(xí)

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

ppt-----遞歸例1

求n!遞歸例2

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

例3

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

求數(shù)組元素的平均值例3,例4如果用鏈表來實(shí)現(xiàn)呢？復(fù)習(xí)例題----例5統(tǒng)計(jì)二叉樹中的葉結(jié)點(diǎn)個(gè)數(shù)例6

交換每個(gè)結(jié)點(diǎn)的左

和右例1.

求n!factorial

function

f(n)=n!1n*f(n-1)n<=1 (base)//遞歸終結(jié)條件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個(gè)元素，它們?cè)跀?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ù)組中的最大值如果用鏈表來實(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計(jì)um葉(B子in結(jié)Tr點(diǎn)eeN個(gè)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章

算法分析復(fù)雜性上界和平均復(fù)雜度的漸近分析;最佳、

和平均情況下的復(fù)雜度差異;大O、Ω和

θ

符號(hào)分析某個(gè)語句的執(zhí)行次數(shù)（頻度）分析某個(gè)程序段執(zhí)行的時(shí)間復(fù)雜度（用大O表示，要求寫出推導(dǎo)過程）ppt:-----對(duì)排序算法與查找算法的分析例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次、結(jié)構(gòu)棧，和鏈?zhǔn)浇Y(jié)構(gòu)，應(yīng)用），表、棧和隊(duì)列的（基本第概念3章，順序特殊矩陣的壓縮表頭結(jié)點(diǎn)用鏈表實(shí)現(xiàn)表：邏輯-----（e1,e2,…..en)物理------數(shù)組實(shí)現(xiàn)鏈表實(shí)現(xiàn)------單鏈表循環(huán)鏈表雙向鏈表cursor操作------查找、

、刪除ppt----多項(xiàng)式相加約瑟夫問題雙鏈表的、刪除例題----逆轉(zhuǎn)鏈表等題第3章

表例1.

逆轉(zhuǎn)鏈表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.

設(shè)有如下結(jié)構(gòu)的循環(huán)鏈表和可利用空間表data

linka1….an-1L

a0Avail

…請(qǐng)?jiān)诔?shù)時(shí)間內(nèi)實(shí)現(xiàn)將L鏈表中的所有結(jié)點(diǎn)歸還到可利用空間表ListNode

p

=

L.link;L.link

=

Avail;

Avail

=

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

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

隊(duì)列---循環(huán)隊(duì)列的補(bǔ)充題已知隊(duì)尾元素的位置與元素的個(gè)數(shù)，求隊(duì)頭元素的位置?！?情況一: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),非零元素個(gè)數(shù)(terms),

a,

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

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

Linked

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

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

指向下一個(gè)非零元素結(jié)點(diǎn)*right

指向同一行右面一個(gè)非零元素T是表頭結(jié)點(diǎn)F是非零元素結(jié)點(diǎn)* next

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

非零元素結(jié)點(diǎn)headnextdownright(2)

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

77rows

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

0

211F

1

012F

2

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

，可以只存對(duì)角線及對(duì)角線以上的元素，或者只存對(duì)角線或?qū)蔷€以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。

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

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

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

第4章中用非遞歸實(shí)現(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.利用先序、中序可唯一構(gòu)造一棵樹先序：ABDCEGFHI中序：DBAEGCHFI利用中序、后序可唯一構(gòu)造一棵樹手工畫出一棵樹利用算法生成一棵樹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.

利用廣義表表示來構(gòu)造一棵樹7.

應(yīng)用樹的機(jī)內(nèi)表示：廣義表表示、雙親表示、左---右兄弟表示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;樹-----二叉樹的轉(zhuǎn)換ForestBinary

treeForestAHBCBinarytreeFD

GIJEK7.

Application每棵樹轉(zhuǎn)為二叉樹AFHBGICKJDE把每棵二叉樹根用右鏈相連ABFCGHDIERJBinarytreeForestABFCGHDIERJ7.

Application樹與森林的遍歷樹的遍歷：深度優(yōu)先遍歷，廣度優(yōu)先遍歷深度優(yōu)先遍歷先序次序遍歷（先序）樹的根

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

C

D

對(duì)應(yīng)的二叉樹的先序一致后根：EFBKLGCHIMJDA與對(duì)應(yīng)的二叉樹的中序一致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.

機(jī)內(nèi)如何一個(gè)結(jié)點(diǎn)增加兩個(gè)標(biāo)記域：leftchildleftthreaddatarightthread

rightchildleftchild

指向左leftThread=

=leftchild

指向前驅(qū)（某線性序列）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哈夫曼樹哈夫曼樹的構(gòu)造哈夫曼編碼擴(kuò)充的二叉、三叉、….、t叉樹15,

3,

14,

2,

6,

9,

16,

17

構(gòu)造擴(kuò)充的三叉樹。等價(jià)類問題PPT第8章第4.1章：二叉搜索樹二叉搜索樹的概念帶索引的二叉搜索樹的概念A(yù)VL樹-----平衡的二叉搜索樹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ù)實(shí)現(xiàn)在帶索引的二叉搜索樹（IndexBST)中查找第k個(gè)小的元素。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的右子樹

外側(cè)加高(對(duì)A而言)單旋轉(zhuǎn)(左)調(diào)整后:樹高不變.原h(huán)+2,后h+3,調(diào)整后h+2,不平衡不會(huì)向外傳遞.+AABBCCDDEEhhhhh}}h+1h+1情況1:A121112情況2：C右下旋A左下旋AABBABCCDDEEEDGGFFCF

Ghhhhhhh-1h-1h-1h-1h-1h-1orororAAC的左子樹—內(nèi)側(cè)加高（對(duì)A而言）雙旋轉(zhuǎn)（先右后左）1AD167D8D8C108

11C107

9

119

1212C109

11125A左旋轉(zhuǎn)7C右旋轉(zhuǎn)7*調(diào)整只要在包含結(jié)點(diǎn)的最小不平衡子樹中進(jìn)行,即從根到達(dá)

結(jié)點(diǎn)的路徑上,離

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

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

調(diào)整不會(huì)影響到以A為根的子樹以外的結(jié)點(diǎn)。例如：-1155

+1010

1804

8

1106

9

1207422

524

320

8106

9

11712

沒有變化也可這樣講： 一個(gè)新結(jié)點(diǎn)后，需要從

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

BhCCDDEEhhhhhA右下旋hAABBBCCDDDEEEFFAF

GGGhhhhhorh-1h-1h-1h-1h-1h-1orB左下旋A右下旋Cor左內(nèi)側(cè):從空的AVL樹建樹的算法。一個(gè)例子：7個(gè)關(guān)鍵碼發(fā)生四種轉(zhuǎn)動(dòng)

A，

Z，

C，

W，

D，

X，

YA

AZCA右雙旋轉(zhuǎn)Z

AZ

A

ZWCC右內(nèi)DCA

ZW左外右單旋轉(zhuǎn)ACD

ZW左單旋轉(zhuǎn)ACCDZX右外ZA

D

XWW左雙旋轉(zhuǎn)Y左內(nèi)CYCA

DZXA

D

X

ZWWAVL

Tree：正確尋找最小不平衡子樹判別外側(cè)（左、右）一次旋轉(zhuǎn)、內(nèi)側(cè)（左、右）二次旋轉(zhuǎn)前面的例子：A,Ｚ,C,Ｗ,D,Ｘ,YAVL樹的刪除：方法：與二叉搜索樹的刪除方法一樣。假設(shè)被刪除結(jié)點(diǎn)為W,它的中序后繼為X,則用X代替W,并刪除X.所不同的是:刪除X后,以X為根的子樹高度減1,這一高度變化可能影響到從X到根結(jié)點(diǎn)上每個(gè)結(jié)點(diǎn)的平衡因子,因此要進(jìn)行一系列調(diào)整。

WX

例子:bacefd

ghki

lmpo

srj

n

q

t現(xiàn)要?jiǎng)h除Cab右內(nèi)dfe

gh1)db

fhiklme

g

j

nopstrqa右內(nèi)2)bdhf

i

ljktnpo

qra

e

g

m

s因?yàn)閯h除操作,不平衡要傳遞，所以設(shè)置一個(gè)布爾變量shorter來指明子樹的高度是否被縮短。在每個(gè)結(jié)點(diǎn)上的操作取決于shorter的值和結(jié)點(diǎn)的平衡因子，有時(shí)還要依賴

的平衡因子。AVL樹的算法分析具有n個(gè)結(jié)點(diǎn)的平衡二叉樹（AVL），進(jìn)行一次

或刪除的時(shí)間

情況≦O（log2

n)證明：實(shí)際上要考慮n個(gè)結(jié)點(diǎn)的平衡二叉樹的最大高度≦(3/2)log2

(n+1)設(shè)T

h

為一棵高度為h，且結(jié)點(diǎn)個(gè)數(shù)最少的平衡二叉樹。}h-1h-2{h假設(shè)右子樹高度為h-1因結(jié)點(diǎn)個(gè)數(shù)最少,左子樹高度只能是h-2這兩棵左子樹,右子樹高度分別為h-2,

h-1,也一定是結(jié)點(diǎn)數(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假設(shè)N

h表示一棵高度為h的Fibonacci樹的結(jié)點(diǎn)個(gè)數(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滿足費(fèi)波那契數(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 .

..費(fèi)波那契數(shù)F

i

滿足下列公式F

i

=

——(———)

-——(

———)1 1-

√5√5

2iii——(

———)相當(dāng)小1-√521

1+√5√5

2∵

|1—-√—5

—

|

<1,

∴

12

√5iN

h

+1=

——

(———) +

O

(1)∵費(fèi)波那契數(shù)樹是具有相同高度的所有平衡二叉樹中結(jié)點(diǎn)個(gè)數(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關(guān)鍵碼為{16，3，7，11，9，28，18，例子：對(duì)一棵空的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ū)長(zhǎng)度的最大質(zhì)數(shù)為什么取最大質(zhì)數(shù)？平方取中法H(

Key)=Key2

的中間部分，其長(zhǎng)度取決于表的大小。設(shè)表長(zhǎng)=29=

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

乘法雜湊函數(shù)H(

Key

)

=

M

*

((

*

Key

)

%

1

)

例：設(shè)表長(zhǎng)

=

29

=

(512)10

地址

000~777(八進(jìn)制），則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引起浪費(fèi)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個(gè)字符的詞典的不同組合數(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ù)允許溢出，這可能會(huì)引進(jìn)負(fù)數(shù)hashVal

+=

tableSize;return

hashVal;}solve

acollision1.

Open

Addressing1)

linear

ProbingIf

hash(key)=d and

the

bucket

is

alreadyoccupied then

we

will

examinesuccess