数据结构树TREES.docx

数据结构树TREES.docx

《数据结构树TREES.docx》由会员分享，可在线阅读，更多相关《数据结构树TREES.docx（9页珍藏版）》请在冰点文库上搜索。

数据结构树TREES

TREES

Hierarchy-arepresentationfromhighesttolowest（TOP-downSTRUCTURE）

BinaryTree:

Noofchildren<=2

0,1,2

StrictlyBinaryTree-Abinarytreewhereeachnodeexcepttheleafnodeshas（non-emptyleft）andrightchildren

FullBinaryTree–ABinarytreewhereeachnodehasexactly2childrenexcepttheleafnodes.

TraversingaBinaryTree:

1.Inordertraversal–Rootisvisitedin-betweenleftandright

LeftRootRight

2.PreorderTraversal–Pre=Before–Rootisvisitedbeforeleftandright

RootLeftRight

3.PostorderTraversal-Post=After-Rootisvisitedafterleftandright

LeftRightRoot

InaBINARYSEARCHTREE:

LeftSubtreevalues

Algorithmforlocating/searchingavalueofanodeinaBinarySearchTree:

1.current=root

2.ifcurrent=null

display“thesearchvaluenotfound”

exit

3.Comparecurrent.datawithsearch_data

I.ifcurrent.data=search_data

display“valuefound”

exit

II.ifcurrent.data

current=current.right

gotostep2

III.ifcurrent.data>search_data

current=current.left

gotostep2

AlgorithmforlocatingtheparentofthenewnodetobeinsertedinaBST:

1.current=root

2.parent=null

3.repeatstep4,5and6untilcurrent=null

//thenewnodewillbetheleafnode

4.parent=current

5.ifnewnode.data

current=current.left

6.ifnewnode.data>current.data

current=current.right

AlgorithmtoinsertanewnodeinaBinarySearchTree（BST）:

newnodewillalwaysbetheleafnode

1.createnewnode

2.newnode.data=data

3.newnode.left=null

4.newnode.right=null

//thenewnodeistheleafnode

5.locatetheparentofthenewnode

//refertothealgorithmabovetofindtheparentofanewnode

6.ifparent=null

root=newnode

//ifthetreeisempty,thenewnodeistherootofthetree

7.ifparent.data>newnode.data

parent.left=newnode

//thenewnodebecomestheleftchild

8.ifparent.data

parent.right=newnode

//thenewnodebecomestherightchild

DeletinganodefromaBST:

Locatethenodetobedeletedanditsparent

AlgorithmforlocatingthenodetobedeletedanditsparentinaBinarySearchTree:

1.current=root

2.parent=null

3.Repeatsteps4,5and6until

current.data=delete_dataORcurrent=null

4.parent=current

5.ifcurrent.data>delete_data

current=current.left

6.ifcurrent.data

current=current.right

Thereare3possibleconditions:

Case1:

thenodetobedeletedisaleafnode

Case2:

thenodetobedeletedhasonechild（leftorright）

Case3:

thenodetobedeletedhas2children

CaseI:

AlgorithmtodeletealeafnodeinaBST:

1.Locatethenodetobedeleted.CallitCurrent.MarktheparentofCurrentasParent

//refertothealgorithmforlocatingthenodetobedeletedanditsparentinaBST

2.Ifcurrent=root

//thereisonlyonenodeinthetree

root=null

//thetreebecomesempty

gotostep5

3.ifcurrent=parent.right

parent.right=null

goto5

4.ifcurrent=parent.left

parent.left=null

goto5

5.releasecurrent

CaseII:

AlgorithmtodeleteanodewithonechildinaBST:

1.Locatethenodetobedeleted.Callit

current.Marktheparentofcurrentasparent

//refertothealgorithmforlocatingthenodetobedeletedanditsparentinaBST

2.Ifcurrent.left<>null

//thecurrentnode（thenodetobedeleted）hasaleftchild

current.left=child

goto4

3.Ifcurrent.right<>null

//thecurrentnode（thenodetobedeleted）hasarightchild

current.right=child

goto4

4.ifcurrent=root

//thereisonlyonenodeinthetree

child=root

goto7

5.ifcurrent=parent.left

//ifthenodetobedeletedistheleftchildoftheparent

parent.left=child

goto7

6.ifcurrent=parent.right

//ifthenodetobedeletedistherightchildoftheparent

parent.right=child

goto7

7.releasecurrent

CaseIII:

Algorithmtodeleteanodewith2childreninaBST:

1.Locatethenodetobedeleted.CallitCurrent.MarktheparentofCurrentasParent

//refertothealgorithmforlocatingthenodetobedeletedanditsparentinaBST

2.Locatethe“Inorder_successor”ofthecurrent（nodetobedeletedwith2children）

a）current.right=Inorder_Successor

b）repeatuntilInorder_Successor.left=null

i）Inorder_Successor=Inorder_Successor.left

3.current.data=Inorder_Successor.data

//replacethevalueofthenodetobedeletedwiththevalueoftheinorder_successor

4.ifInorder_SuccessorisLeafNode,UseCaseItodeleteInorder_Successor

5.ifInorder_Successorhasonechild,UseCaseIItodeleteInorder_Successor

Successor:

onewhichcomesafter

12345678910

14581017

Inordersuccessorof1is4above（basedontheorderofnumbers）

Predecessor–onewhichcomesbefore

10987654321

10741

Inorderpredecessorof10is7is4is1

ForfindingtheInorderSuccessor:

1sttakearight

ThenkeeptakingaleftuntilNULL

ForfindingtheInorderPredecessor:

1sttakealeft

Thenkeeptakingarightuntilnull

Leftchildwillbethepredecessor

MemoryLeak–MemoryOverflow–thespaceinthememoryrunsout!

HeightBalancedTree（AVLTREE）

LeftHeavytree:

wheretheheightoftheleftsubtreeisgreaterthanthanheightoftherightsubtreeby1

RightHeavyTree:

wheretheheightoftherightsubtreeisgreaterthanthanheightoftheleftsubtreeby-1

PIVOTNODE:

Anodewhichisnearesttothenewnodeandhasavalueotherthan0,1or-1.

OnceyouhavechoosenaPIVOT,thatvaluewillstayasaPivotuntiltheprocessofDoublerotationiscomplete.

CasesforRotation:

CaseI:

Whenyouinsertanewnodeinarightheavysubtree

I（a）:

Insertthenewnodeastherightchildoftherightheavyrightsubtree

（Inserttotherightofrightheavy）

I（b）:

Insertthenewnodeastheleftchildoftherightheavyrightsubtree

（Inserttotheleftofrightheavy）

CaseII:

Whenyouinsertanewnodeinaleftheavysubtree

II（a）:

Insertthenewnodeastheleftchildoftheleftheavyleftsubtree

（Inserttotheleftofleftheavy）

II（b）:

Insertthenewnodeastherightchildoftheleftheavyleftsubtree

（Inserttotherightofleftheavy）

CaseforSingleRotation:

CaseI（a）-Inserttotherightofrightheavy

CaseII（a）-Inserttotheleftofleftheavy

TheresultofSingleRotation:

ResultI:

SingleLeftRotation:

TherightchildofPIVOTnodebecomestheparentofthepivotandtheleftchild（ifany）ofthenewparentbecomestherightchildofthepivot.

ResultII:

SingleRightRotation:

TheleftchildofthePIVOTnodebecomestheparentofthepivotandtherightchild（ifany）ofthenewparentbecomestheleftchildofthepivot.

CaseforDOUBLEROTATION:

CaseI（b）–Insertintheleftofrightheavy

CaseII（b）–Insertintherightofleftheavy

Remember:

LeftHeavy:

Alwayspositive

RightHeavy:

Alwaysnegative

Forbalancingtherightheavytree:

rotateLEFT

Forbalancingtheleftheavytree:

rotateRIGHT

Youneedasingleleftrotationwhenthebalancefactor=-2

Youneedasinglerightrotationwhenthebalancefactor=2

Youneedadoublerotationwhenthebalancefactor=（-1with2）OR（1with-2）

Whenyouhave-1with2:

FirstrotateLEFT（tobalancetherightheavysubtree）andtherotateRIGHT（tobalancetheleftheavysubtree）

Whenyouhave1with-2:

FirstrotateRIGHT（tobalancetheleftheavysubtree）andtherotateLEFT（tobalancetherightheavysubtree）

AnewnodecannotbeinsertedinaTREEifitisunbalanced.

Anodecannotbedeletedfromthetreeifthetreeisunbalanced