صفحه 1:
رشته علوم کامپیوتر
ناصر آیت
صفحه 2:
در مور
##ساختمان داده روشی است برای معرفی و دستکاری داده
#و کلیه برنامه های معرفی داده
#برای معرفی داده نیازمند یک الگوریتم ميباشد.
صفحه 3:
در مورد ساختمان داده
سس
روش های طراحی الگوریتم نیازمند پیشرفت برنامه هایی است که برای
نگهداری داده است.
_ در علوم کامپیوتر مطالعه ساختمان داده ها مهم وضروری میبا شد.
صفحه 4:
۳5 Perequisites
++O0
ig ob ; theta ced pee ye ootatize
صفحه 5:
سوه [
ترئیب زیر را در نظر بگیرید:
ها 07اه
پس از مرتب سازی صعودی داریم:
[0-]ه->.... -> [0]مد> [0]ه
,9,8,0 << 02,6 9 ه, 6:ج موجمج
صفحه 6:
Gon wetods
desertion sort
(ubble sort
او ماوق
9
Gkoker sort
Ghell sort
او مورا
Oerye sort
Quick sort
صفحه 7:
اسان كرون يكقصسطه ددا [
لیست ترتیبی زیر را در نظر بگیرید:
,9 ,9 ,9 :نز
عنصر 6 را به لیست فوق اضافه کنید.
,9 ,9۱ ,9 ,9 :من
صفحه 8:
dasert Bu Cleweut
[
df 9 9,9 9 سس
عدد 6 را با آخرین عنصر ليست مقايسه كنيد .
, ,9 ,9 ,9 عن right to 062 بع
ادا
Gh © rightio yet 9, 9, , 9,
062 ,9 ,9 , ,29 عو ص كوم © ع
با اضافه كردن © خروجى:
Ghi
,9 ,9 ,9 ,9 سود
صفحه 9:
۳ dasert Bu Cleweut
fosert tot ۱]:
اكاك
Por (FHO 5 P=O && 1 <af [ رز
OL i+] = of]
; OL id] = 1
صفحه 10:
[ asertiva sort
لیستی با سایز) در نظر بگیرید."اولین عنصر را _
داخل ليست قرار. دهید.*
ج. عمل ووشقوئ را تكرار كنيد بطوريكه ترتيب داده
ها حفظ شود
صفحه 11:
۱ aseriiva sort
Gm ?,9,S,9,4
Gro wi Pod set O=> 9,7
م6 ,© ,9<-© ووم
م6 ,© ,© ,9<-9 نووم"
م6 ,9 ,9 ,9 ,12<6) بصووا؛
صفحه 12:
۳ ۱ asention sort
Por (FC 5 i<atecrgh 5 it +)
ioert afi] ist o[O:i-] //}
pode to insert powEs kere//
{
صفحه 13:
Por (FC : ایک ; i++)
iupert uff] ict o[O C1] /}
code to eer cower herel/
۱۱ 2۰] [
ألما
(-ز : <af i] 1 && 0 << ر )حر ) ع2
of] = [0 ]©
, ©] +0[ > ١
صفحه 14:
پیچیدگی مکانی /حافظه ای
پیچیدگی زمانی
شمارش یک عملگر خاص
شمارش تعداد مراحل
پیچیدگی امس رد9)
صفحه 15:
Cowprativa pow
as
Por (FC : ایک ; i++)
iupert uff] ict o[O C1] /}
code to eer cower herel/
iat t =o[ i]
زار
)< ) عح : مرح && 1 <af i] : (-ز
Ltd] = of i]
, ©] 20[ >
صفحه 16:
Cowprativd vowet
a
" يك نمونه كاراكترى از » ريا در نظر بكيريد» كه در
آن > طول ليستى باشد كه مى خواهيم روى آن
Tesentioa sort 5\ لنجام دهيم.
* و نعداد توابع اين نمونه کاراکتری را بشمارید.؟؟؟؟
ماو Onterwiue pouat os 0 Puontion oF this
.chorunteristic ?22
صفحه 17:
] هسسسس |
(حز [ز امک ۱ 86 ©0-<ز: 0سح) عو
[ ]۰ < [۱۳۵ ]0):
8 چند مقایسه انجام شده است ؟
صفحه 18:
] هسسسس |
Por (FHA ; PHO 86 ۱ رز [ امک
0] ۳4[ < ۰] [
شمارش تعداد مقایسات وابسته ty [fray با توجه به ز
صفحه 19:
Cowprativd vowet
امه روهام Oorstouse
Ors —cuse pow wick امه
a
صفحه 20:
Por (Fr ; P=O && t <af j] --)
O[ +] = fi]
®=[4,0C,9,¢] لوو FO => cowpures
@=[0,0,9.,..,i] od HO =>i cowpares
صفحه 21:
Por (iat FR; i< ot 5 i++)
or (FH ; P=O && 1 <of i] si)
OL itd] = fi]
: تعداد کل مقایسات
وروی او =(+O+0+...+(o-()
WO (o-)=
صفحه 22:
4
Gtep vownt
" یک مرحله از محاسبات وابسته است به مقادیر -
8 برای مثال :
uh , (OO subtracts, (DOO watipties 000
فقط یک ,و محسوب میشود .
وبه این مفهوم نمی باشد که با افزایش ج یک مرحله
نيز به تعداد مرو اضافه شود.
صفحه 23:
[ Gtep vownt
ole
Por (FC 5 i<c.tecrhy 5 r++)
ieeert of] ict o[D-]
pode to iwsent vowes here
rat Sof i]
iti;
Por (HO 5 P=O && 1 <af i] : (حز
©] *0[ < fi]
©] +0[ >
1
صفحه 24:
[wm sd
OD Ate cle " يايكنموياشد
ی (دره) مه همع )(
۱( iusteae churapteristic hus o ole
cow oP >
صفحه 25:
0
0
al
0 ۳0
[ Gtep count
(+۱ : یاک : 0ع) و
[ :اه صد ناه نع
code to tasert cowes here
wt =f]
inti;
or (FH; P=O && 1 <of i] (سز:
Ld] = of i]
OL itd] =1;
{
صفحه 26:
Gtep vownt
4
Por (ict 20: ایکا ۱+(
)6+۵(
Gtep vowt Por
Por (tot FC; i<ctecreyhs;; r++)
dso
Gtep cout Por body oF Por top is
O(rd)+(H +... 404+ +9 JC
و +9 (4-)(o)=
(st9)(or)=
صفحه 27:
ِ محاسبه پیچیدگی در مرتب سازی درجی [
۵)(
به چه معنی می باشد؟
صفحه 28:
ِ محاسبه پیچیدگی در مرتب سازی سى] -
" بدترين حالت:(5)©
" بهترين حالت: (6)0
" بنابراين انتظار ميرود بدترين حالت زمانى است كه -
دوبل ميشود(تكرار ميشود).
صفحه 29:
محاسبه بيجيدكى در مرتب سازى سى] -
* آيا (©») مخيلى زياد ۳ ا
" الكوريتم تجربى(1--8---م) جه مب
صفحه 30:
Cowpputer Os Ortter Okyorithe سم
" پیشرفت الگوریتم ها مفید تر از پیشرفت سخت افزار
Cul
صفحه 31:
۳ Oata Structure ساختمان داده ْ
ae 3 گیرند(در ارتباط).
عه قرار مى كي 2
" داده هايى كه در يك مجموعه قرار
Ox: totecer= {D, +0,-0,48,-8,....}
days oP week = {6,0,1,0,PW,GO}
صفحه 32:
[ont |
* داده هایی که نامربوط با هم هستند.
عامممعج):
ار سول 9 ره رازه0
صفحه 33:
۳ Dara Circe
+ Duta vievt
روابطی که وجود دارد برای مقایسه میان عناصر
0م >> ©6956
2
صفحه 34:
۳ Dara Circe
" ميان عناصری که مقایسه میشوند در یک مثال:
99
is wore siqePicativd thot O O
howwediutely to the fePt pO O دز
© © خام جاعم هذا ما برإعاد]لص وص دز
صفحه 35:
|] Dara Circe
" روابط خاص معمولا توسط عملگر های خاص روی
چندین نمونه داده ایجاد می شود عبارتند از:
ضرب » تفریق » جمع
صفحه 36:
(or Ordered) bots سا
astacaves ure oP the Pore
((O,e4,e0,....,20-)
Okere نو decodes نصا هد plexed o> =O is Pictite
List size is >
صفحه 37:
| تمس
(دس,.. . ., م عم ادر (اك) حرا
روابط زير بر قرار است:
: )ج عنصر جلوی لیست میباشد. "ام امسر"
:)مج عنصر آخرلیست مییاشد. . "واه “host
: )+ع دقيقا بعدازیم قرار می گیرد.
صفحه 38:
مثالهايى از ليست های خطی: ۳
Onna tt COPOSSO= (jack, Phe بصك 3 ,تصدم ماكر
esi)
@xnvs in COPSSSO=(rxall, exar G, ex)
Oas oF Oeck=(6,0,1,0,0, GO)
Oveths=(da0,Peb Dar ,pr,...,0ov,Der)
صفحه 39:
۱ موی نوا مسوا
& اندازه گیری سایز لیست
‘Exanvple
L=(x,b,7,4,)
وحمو
صفحه 40:
* یک عنصر را میگیرد و اندیس آن را بعنوان خروجی می دهد.
عا 2):
قمع مدنا
@e(D)=a
@e(@)=r
بح(
@et(-)=error
@et(O)=error
صفحه 41:
اندیس هر عنصر را برمی گرداند.
(درطرل,طرم) عرا
(9
P(a)=
endo oP(z)=-4
eden oI
eden oI
صفحه 42:
حذ ف را انجام داده و محتوای اندیس مورد نظر را برمی گرداند.
بر ,رل راره) عرا
ص عضو Rewove(©)
ead b bere (ub,deP x)
iotex DP d,e,P ood y devreuse by 0
صفحه 43:
Opratizcs-reernve (the iercex) ۱ او رس
حذ ف را انجام داده و محتوای اندیس مورد نظر را برمی گرداند.
L=(a,b,7,4,e,P)
Rewove(-)=> error
Rewme(CO)=>err7r
صفحه 44:
همطل مورا
Obstract Data Pppe
ava
Obstarant chaise
صفحه 45:
List Obstarant Duta Type راز
ObstranData Pype Lbicear List
سر 1 ©
Ordered Prat oolevtiog oP واه و مه مود
عملكر ها
( \Ewpy
نتيجه درست را بر می گرداند اگر و فقط اگر ليست خالى باشد »در غيرنتيجه
:) )\Gize
اندازه لیست را بر می گرداند.بعبارتی تعداد عناصر داخل لیست را بر می
داند.
صفحه 46:
9 وم رومب)
Licked---chapter 9
Gioukited
صفحه 47:
< | ٩1 | ع | ۲
L=(ab,0,d,e)
صفحه 48:
صفحه 49:
نوم ان تمورظ وا rat |
صفحه 50:
صفحه 51:
| ممص Osed Ia Text
ع | 8 اج
صفحه 52:
|
۳ (®u Cleweut _0
Gte=S
صفحه 53:
[coc (Rewove (ua Clewent_O
cd (1, «)
size-=O
بدك | ۲ | 2 | 1 | <
صفحه 54:
اوسم of Onw elecwest
چون نمی دانیم چه تعداد عنصر در لیست وجود خواهد
داشت ببنابراین باید یک مقدار اولیه برای آن فرض
.کرد.و سپس بر حسب نيان آن را افزايش داد
صفحه 55:
Licer List Pbstaract Duta Type
:Get (iertex)
خروجی آن اندیس عنصر میباشد بر طبق جایگاه آن ودرصورتی مقدار()
را برمی گرداند که عخصر مورد نظر در لیست نباشد
Basen: (eles)
عنصر را حذف کرده و محتوای عنصر را برمی گرداند.
‘dt (jeder, x)
عنصر ,د را در بعلم داده شده اضافه كرده و يس از آن شماره انديس ما
بقى عناصر از موقعيت جارى يك واحد افزايش ميابد.
:) ای(
خروجى ليست است که از چپ به راست مرتب می شود.
صفحه 56:
@s dave ubstract Class سس
ble obsiructchss Lineur ListDs@bsiratOkes
}
{Q@ublic obstarct Oovleod ibCwpiy
[Q@ublic obstarct ict size
JP blir obstarct objevt opi(int tert)
{@ublic obstarct iat idexOP(Objert the eleweut)
{@ublic obstarnt ماه recover iat ierdex)
{@ublic obstarct void odd (fat ide, Object the elewent)
[Q@ublic obstarct striag to باس
1
صفحه 57:
عناصر لیست در
نگهداری می شوند.
ui fists) تصانی) مشاه تلو
اطلاعات صریح که لینک نامیده می شوند
برای رفتن از یک عنصر به عنصر دیگر
استفاده میشوند
صفحه 58:
براى نمإيش ليست ها از آرايه ها انتتفاده مین شتو5 0
(عبكرصرطه) = L
.هرلینک از یک جدول دلخواه استفاده می کند
A linked representation uses an
T Tal TT وها ساف
صفحه 59:
firstNode
تهی می باشد. (<) اشاره گر عنصر
علد ناص
براى اشاره به عنصر شروع استفاده ميشود.
صفحه 60:
Ow To Orav © Licked List
5 8 5 8
فيلد اشاره كر
۳
۳ ou
صفحه 61:
دریک زنجير يا در یک لیست از اشاره گر هاهر نود نشان دهنده یک
از يك نود به نود ديكر يك اشاره كر وجود دارد.
اشاره كر آخرين ليست تهى ميباشد.
صفحه 62:
لط
اوه زان
{CkoinOode text
صفحه 63:
ChainNode(Object element)
{this.element = element; }
ChainNode(Object element,
ChainNode next) 5
{this.element = element;
this.next = next;}
صفحه 64:
cher ledex(D)
sdesiredDode = Pirst(Dode
Sreturca desired ode.cleweut
صفحه 65:
صفحه 66:
(2) سداد
idesiredDode = PirstDode.cext.cext
desired(Dode.cleweut ما
صفحه 67:
صفحه 68:
desiredDode =
it
صفحه 69:
firstNode = firstNode.next;
صفحه 70:
beforeNod
ابتدا نود قبل 0 نودی را که بخواهد حذف شودوا انتخاب کنید
1
Pirst " 'يعنى
beforeNode = firstNode.next;
صفحه 71:
beforeNod
e ۳
اکنون اشاره گرآن را تغییر دهید. )در
beforeNode.next =
beforeNode.next.next;
صفحه 72:
. گام اول: نود جدید را انتخاب کنید که حتما دارای فیلد داده واشاره گرباشد
ام اول: نو ار - ار واشار
ChainNode newNode =
new ChainNode(new Character(‘f’),
firstNode);
صفحه 73:
.گام اول: آن را بعنوان نود آغاز انتخاب کنید
firstNode = newNode;
صفحه 74:
صفحه 75:
beforeNod
گام اول:ابتدا نود با اندیس 2راآگتخاب کنید.
گام دوم: حال نود جدید را ایجاد کرده بطوریکه دارای فیلد داده و فیلد اشاره گر داشته
با
ChainNode newNode = new ChainNode(new oe
Character(‘f’),
* finally link beforeNode to newepdeede nex”):
beforeNode.next = newNode;
صفحه 76:
) ۳۴۳ ,9۰ وتو نا
ode newNod—> ۱
beforeNod
e
beforeNode = firstNode.next.next;
beforeNode.next = new ChainNode(new
Character(‘f’),
beforeNode.next);
صفحه 77:
88 88 88 5 5 5 8
“لجا
oe
se Re BRB
88 ۶ 85 85 5 ٩5 8
رم | ۶
صفحه 78:
e=
تعدادعناصر لیست میباشد. شمارش
6 )کار برد
((/0۳۵۰) )مس | |
a element (datatype Object)
صفحه 79:
dota wewbers ||
iprotevied Okcin@Mode Pirst(Dode
Iprvtevted fot size
weeds of Oboe coe here /|
{
صفحه 80:
۹
۰
{
()publir Obie
{itkio(D)}
صفحه 81:
صفحه 82:
صفحه 83:
برگرداند به اين مفهوم است که آن عنصر در لیست و
(صلمد مسا امن اج
}
B (trdex < @ || trex >= size)
teow ve ‘ledexOuORBrudsPxcepion
‘(ecb =" beckon +" stm =" + ope")
{
صفحه 84:
/ نود دلخواه راتغییر دهید
{CkanO@ode coredQDode = PirstDode
Por (iat i = O; i < index; i++)
jouredDode = cored ode.cext
wet ای لاه مساو
1
صفحه 85:
&& white (rureutDode |= cul
(eenQDode.clewed.equis(theClewen)!
1
// به نود بعدى تغيير دهيد
مه )مه < jouredDode
عبر
{
صفحه 86:
Pie لم ۱ 1
[=
له مور
{
صفحه 87:
صفحه 88:
جمد )جر مس وان
(dex == O) ۱ نود شروع را حذف كنيد
}
jrewovedPlewedt = PirstDode.elewedt
JPirstQDode = PirstDode.cext
{
صفحه 89:
beforeNod
را یافته و اشاره گر آن را تغییر دهیدیا() ساسا
beforeNode.next =
beforeNode.next.next;
صفحه 90:
jrewovedPlewedt = y.cent.elewedt
اب مب < sg.cexd // 255 دلخواه را حذف کنید
{
josie
jretura rewovedPleweot
1
صفحه 91:
۷" ,)لل )سیون
PirstDode = ue Choicode(‘P’, PirstDode)
صفحه 92:
(0 > سلم) ۸
به جلو اضافه کنید.
PirstDode) ما۳( PirstDode = we
صفحه 93:
ی add(9,’P’) هس
ode newNod—> ۱
beforeNod
e
beforeNode = firstNode.next.next;
beforeNode.next = new ChainNode(‘f’
beforeNode.next);
صفحه 94:
Odio; OS, Bleceat
/ ماضافه کنید بعد از
Ipsext = cew Ohvicode(iheClewedt, p-uext)
1
ووو + +
{
صفحه 95:
صفحه 96:
صفحه 97:
صفحه 98:
73
صفحه 99:
نت
صفحه 100:
صفحه 101:
له () عصلدد ناا 15( اصزنا انز Licked
headerN
ode
صفحه 102:
صفحه 103:
۳ nw Represecaiod ۰۱ 0, ۵ 1
Memory
1
start
. یک نمونه آرایه یک x = fs, b, o, d] Ga
در خانه های مجاور یکدیگر قرار میگیرند
* location(x[i]) = start + i
صفحه 104:
"۳ لامرن 1
Memory
space pverkeud = P bytes Por start
bytes Por x-beerts P+
bytes © =
) (میزان فضایی که برای آرایه فوق نیاز داریم
صفحه 105:
eof OP] سس - وا كر
که در یک جدول نشان داده م شود.
(فازهاه (فازهاه OWA] زطازف۳ه
AMO] Aya] olde] fay]
aASIO] AS] Sle] el]
صفحه 106:
صفحه 107:
رم 90 6۴
IIE] al
column column column column
0
صفحه 108:
1 02۰0۵ ۱
عدداوا
۱ < 6 سم
ed siore os PO orp
صفحه 109:
0
O, wd
a dav,
Qepreseutatioa
@nup
0
5
alec = 5
€ pathy =
fk = x{C] loos = سا[
ما[
صفحه 110:
1 امیس ۳"
5
‘EEE
spuce puverkesd = pverkeud Por P ID arups
bytes O * PF =
bytes OO =
x © bytes (sucvber oP rows + (1) =
صفحه 111:
+410 Pry Represectaiod Ia C uc C
xt
این نمایش آرایه آرایه ها نامیده می شود.
با توجه به شکل فوق نیازبه حافظه ای با سایز های هر )4و4 برای ذخیره آرایه
های یک بعدی دارد.
یک بلوک حافظه شامل سایزتعداد ستونها و سطرها میباشد
صفحه 112:
ijkl
آرایه فوق در یک آرایه یک بعدی قرار گرفته است بطوریکه هر عنصر آن یک سطر
از آرایه فوق است و بعبارتی هر سطر آن یک آرایه یک بعدی می باشد.
. عناصرداخل هر سطر از چپ به راست مرتب شده اند
. سطرها از بالا به يايين مرتب شده اند
Ov wt بل رط ره &, Ph ki, b, 1(
صفحه 113:
عاصرداخل م هر ستون از بألا به أي هر مرتب شده اند .
ستون هااز جب به راست مرتب شده اند .
)1 رط راك بها ريك رك رز رظ رط رارج به Orvet
صفحه 114:
90 59
صما ... تعدادكمتر عناصر آنصفر
صفحه 115:
صفحه 116:
list =
row 1 1 2 8
0۶۸ 4
0000 column 35342
090 3 5
value 3 4 5 7 2
6
صفحه 117:
muy Linea List Represeutatios
element O 1 2
10 1 1 2 2
column 3534
صفحه 118:
ختار نود
Chait Qepreseutatioc
صفحه 119:
FERRER
firstNode
صفحه 120:
0 imeur- List Per Row
2900
9
SOO
Or?
(TY) CTY) ۲
صفحه 121:
ختار نود
Ornw OP ow Chace
صفحه 122:
Ornw OP ow Chace
fo
r=
oo |
SED 7 _
SOO
OP?
OOO row[]
OO
Ce لمح
mh
صفحه 123:
List Represeututios اسان
صفحه 124:
oo |
eo ”
SOO
oF
OOO
OO
7 ۲
صفحه 125:
‘To DO
0
OOOO
0
09 0
“Ty
صفحه 126:
SOO
oF
OOO
OO
7 ۲
۳01۷] [
صفحه 127:
صفحه 128:
صفحه 129:
۳0 OF Oups
top — ©
top —@®
4
9
® ®
botto —> 0 botto —> &
m m
* برای درج وحذف *) باید از م,عمل کرد.
Stack=LIFO=LAST IN FIRST OUT *
صفحه 130:
۳۳ eterPace Otact
public icterPace Stack
}
ارت حاورا ان(
: كاعهم امصزط0 صتاطنج()
spoke vokd prash( Obie thsObien!)
: اسان سا por
صفحه 131:
۳ ی «
Output pairs (u,v) suck thot the let poreuesis ut posiiiva ©
is wotcked wit the ght pocedhesis بدك
(27,84) (C4,88) (18,08) (,09) (C,8) *
(0,90)
(e+d))*"(otb *
)6,08(
وا pareuthesis at “Po has av wautckiog right poreuhesis
0۰ © © ©
صفحه 132:
set 1 سس
8 عبارت را از چپ به راست بخوانید.
Let pareuthesis 4 iy رسید آن رادر پشته اصم کنید.
" وقتى به كوب اددهم دنم ريسيد آن راز يشته ممم كنيد.
صفحه 133:
[rrr
_ (oma)! (4) *(et)-(Ptu(otte*(etb))
RN
صفحه 134:
۳ )جر( () ازمم)
(2,6) (1,13
)
صفحه 135:
۳ )جر( () ازمم)
(2,6) (1,13 (15,19)
)
صفحه 136:
۳ )جر( () ازمم)
)2,6( )1,13 )15,19()21,259(
)
صفحه 137:
(so-a)/ (hel)*(Bti)-(Ptu)/(otte*(atb)) ۴
۳ (2,6) (1,13 (15,19X21,2527,31)
)
* and soon
صفحه 138:
OP Weai/@Prokwa عت للا
* 62 حلقه طلا از ستون SG OAD داده می شوند.
هر ستون در آن مانند یک پشته عمل می کند.
8 و هیچ حلقه بزرگی روی کوچکتر از خودش قرار نمی گیرد.
صفحه 139:
تسه )سرا 0 ۳۰
11
disk Towers OP ل 8
صفحه 140:
تسه )سرا 0 ۳۰
11
disk Towers OP ل 8
صفحه 141:
تسه )سرا 0 ۳۰
11
disk Towers OP ل 8
صفحه 142:
تسه )سرا 0 ۳۰
1
disk Towers OP ل 8
صفحه 143:
Towers OP وه )ما
11
disk Towers OP ل 8
صفحه 144:
تسه )سرا 0 ۳۰
۳
disk Towers OP ل 8
صفحه 145:
تسه )سرا 0 ۳۰
11
disk Towers OP ل 8
صفحه 146:
Towers OP وه )ما
TL
dish Towers OP 2 > «9
¢ 7 disk moves
صفحه 147:
صفحه 148:
Gohuion عد نا
* حلقه اول ستون «)را از 9)به () انتقال دهید.
صفحه 149:
[ ا سست ی
# )-محلقه را از ©) به © انتقال دهيد.
صفحه 150:
Revusive Svhutioa
۱1
صفحه 151:
[ots
public icterPace Gtack
}
‘()publc boolean exepty
: صتاطنج() Objevt peek
spuble vod pusk(Object theObievt)
;()publc Objent por
صفحه 152:
(" Crow ® Licear List Chiss
Onwlirewlia ©
Ckoia #
صفحه 153:
|] Crow OrrapliceurList
Q22 34 56
9 عنصر بالای پشته معادل چپ ترین ویا راست ترین عنصر
داخل آرایه می باشد.
٩ مه << (اسسعل()
۲ روز )0216
© (0 - ()صصع)ايض عه peek() => yei(O)
"* عون (0)©
صفحه 154:
|] row @rrapbiteu List
lalblelafe] T TET TTT TT
0123456
* وقتی که مه در موقعیت چپ ترین عنصر آرایه قراردارد
© سرد ,0 >= )ناس
O(size) titoe ©
pop() => rewove(D) ©
#عيي تساج
صفحه 155:
|] row @rrapbiteu List
Ot 2 34 56
* وقتی که مر در موقعیت راست ترین عنصر آرایه قراردارد
pusk(heObjert) => ok(stze(), teObiers)
" ص3 (0)0
pop() => rewove(size()-() ®
O(A) tere ™
use right eod oP list us top vP stack ©
صفحه 156:
Oernve row Chaic
-firstNode
٩ عنصر بالای پشته معادل چپ ترین ویا راست ترین عنصر
داخل آرایه می باشد.
Qesepi,() => ePsopry ©
" صم (0)0
صفحه 157:
Oernve row Chaic
_-firstNode
8 = | = 0
-وقتى كه 107 در موقعيت جب ترين عنصر آرايه قرارريداريد
peek() => get(0) "
O(1) time "=
push(theObject) => add(0, theObject) "
O(1) time "=
pop() => remove(0) *
O(1) time "=
صفحه 158:
(Prow Chain اس
ue
= ۳ = ۳ 5
-وقتى كه ([0] در موقعيت راست ترين عنصر آرايه قراردارد
peek() => get(size() - 1) *
* O(size) time
* push(theObject) => add(size(),
theObject)
* O(size) time
* pop() => remove(size()-1)
* O(size) time
صفحه 159:
Bad peck © (ارکسی()
Zz
0320935255
روصت موجاوضنا حاط ةو(
مسا[ erry}
()pubtic Obert perks
® (ewpr())
cew Cop Stachxcepiion تن(
retara cp(etze() ~()
صفحه 160:
()push(theObert) Bard pop
3 <= |
0123456
vord prsh(Objert ireBlewrest)
معط سل
()public Obert por
}
P (ep)
۱0 نيجه CwptSrackCxvepiion
۳ rewour(size() - 0)
1
صفحه 161:
(:(0 - )نصا با
(ه )وله )یلها )وم
(وسمصحه )درم Tew سهحا():!
صفحه 162:
ا
4 —
|| بمجدعدجه خلا جمد رمه جددج جه
P (top == stack. teach - Cl)
i(stack, O * stack.lecreth)
put the@lewedt of the top oF the stack //
jetack[++1op] = theClewent
{
صفحه 163:
(۳۳۳
—— ی
top 34 00122
publ Obert poy
5-0
® (ewpr())
Oikrow oew CxoppOrackBxvepion
Obert topCleweut = stack[iop]
[سرص] امعد = ond ماس ما ال
سار top Cleweut
{
صفحه 164:
۳ Orack Crow Ooratck
Gee text ۴
صفحه 165:
Oerived@rwGtack 090
099
099 اهزاس رو و لسنوط)
0.99
a jovani. Stack ddGs
Derived inked Gtack 9002
صفحه 166:
| هه Le
يك ليست خطى مى باشد.
عنصر جلوى صف بورج ناميده ميشود.
عنصر انتهاى ليست rear نامیده میشود.
افزودن عنصر به ليست فقط ازانتهاى صف" بح " امکان
يذير است.
حذف کردن عناصراز لیست از جلوی صف"۳7" امکان
پذیر است.
صفحه 167:
(us Gtop Queue
و
صفحه 168:
(us Gtop Queue
Fa
صفحه 169:
(us Gtop Queue
mr ةع يم
Fg
صفحه 170:
صفحه 171:
1 ی و۱ ۳۳
صح0 هه publi
}
باو قات {O)pwbic bovleus
(pubic Obert yetProwBelewent
)مکی ()pubhe Object
pu(Objert theObjert) لادب حاط مز
جوم اعصزط0 حناطج():
صفحه 172:
O12 34 56
زمانی که چپ ليست و مس در راست لیست باشد.
۴ ماه همه << تسه ۵()
O(() toe 2
wetProuCkewea() => ¢e(D) *
0)0( عمس ©
wet(ReaCleweal) => yei(size() - 4( ۴
O(A) toe ©
pri(theObiert) => uhd(size(), heObier!) ©
O(A) tere ©
rewe(D) >= امس
[isin Prow OrrapliceurList
O(ste) itor O
صفحه 173:
0 1 2 34 56
زمانى كدوم راست ليست و -وسم درجب ليست باشد. ©
)(۵ ماه همه << تسه ۴
O(() toe 2
vet ProuPleweni() => yei(size()- (1) ۴
O(A) tree O
ve(RrarClwerni() => oei(D) "*
O(A) toe ©
pri(keObient) => add, theObievt) ۴
O(size) toe O
[isis row @rrapbiceur List
er )موز [ اس
0 یب O(d)
صفحه 174:
[or Crow @rraicealist
0 عملیات درج وحذف در صف با (1)() صورت می گیرد.
صفحه 175:
Orrve Prow CxteudedOkuia
lastNode
|
front rear
لیست قرار دارد Cowl TEAL لیست و ue front a5 وقتی
* Queue.isEmpty() => super.isEmpty()
- O(1) time
* getFrontElement() => get(0)
- O(1) time
صفحه 176:
Orrve Prow CxteudedOkuia
“Ts
front I
* getRearElement() => getLast() ... new method
- O(1) time
* put(theObject) => append(theObject)
- O(1) time
* remove() => remove(0)
- O(1) time
صفحه 177:
Orrve Prow CxteudedOkuia
lastNode
rear front
وقتى كه :110101 راست ليست و 21 ©1جِب ليست قرار دارد
QQueue.isEmpty() => super.isEmpty
- O(1) time
* getFrontElement() => getLast()
~O(1) time
صفحه 178:
Orrve Prow CxteudedOkuia
“Ts
rear front
* getRearElement() => get(0)
- O(1) time
* put(theObject) => add(0, theObject)
- O(1) time
* remove() => remove(size-1)
- O(size) time
صفحه 179:
[ower rap Queue
* _کاربرد یک آرایه یک بعدی بعنوان صف
queue! 1ألالالةةةالةالا
]
* کاربرد یک آرایه یک بعدی بعنوان صف حلقوی
]3( ]2[
صفحه 180:
Custow rap Queue
صف حلقوی با 3 عنصر پر شده است.
[2] [3]
صفحه 181:
Custow rap Queue
* حالت دیگری از قرار گیری 3 عنصر در لیست حلقوی
[2] [3]
صفحه 182:
Custow rap Queue
* کاربرد ۲661 3110 110111 در ليست حلقوی
- :8011 مكانى لستكه ب لبتدلىا يسلشايم میکند.
- 1681 مکانیلستکه به انتهای_یستلشایه مىكك.
صفحه 183:
Odd Ou Cleweat
* 167 درجهنعقربه هایس اعتحر کتمیکند.
صفحه 184:
امس (dd @a
* 1621 درجهتقربه هاى._اعتح ر كتشهيد
* در مكانى كه ۲601 به آن اشاره مى كند
[0]116116]1621 را اضافه كنيد.
صفحه 185:
Rewove Ou Clewwect
Front * را يكواحد cule جا کنید.
صفحه 186:
[Serre سس
* 1 را یکولحددر جهنعقربه هایساعنجابه i Sle
* و محتوای [1116116]870101) را از صف حذف کنید.
]3[ تس
fear
11
صفحه 187:
Ooviery rear Clockwise
Treart +;
if (rear = = queue.length) rear = 0;
* rear = (rear + 1) % queue.length;
صفحه 188:
صفحه 189:
۹ Prot Queue
صفحه 190:
۹ Prot Queue
صفحه 191:
۹ Prot Queue
صفحه 192:
صفحه 193:
صفحه 194:
صفحه 195:
® Paul Tock Please
* اگر به پر کردن صف ادامه دهیم در نهایت می رسيم به
front = rear :b,s
؟ اگر دقت کنید همان شرط خالی بودن صف می باشد
درصورتی که صف پر است !
صفحه 196:
۱۱۱۱۲۵ |
ل شرط پر و خالی بودن در صف حلقوی
Queue is ewpty PP (Pi == rear) && thetOperciodisPul #
Queue is PuliPP (Proot == rear) && lastOperciod sPu #
صفحه 197:
MLE che
7 شرط پر و خالی بودن در صف معمولی
Quarts ey PP (sae 2 0( *
* اط صصه == Qua ts PULPP (ste
صفحه 198:
صفحه 199:
puer's Oiew OP 0 Pree
صفحه 200:
صفحه 201:
۳
۱
ie Decl Deere کاربردهای لیست
0
۱
(Fos Fai بعد بو Pea)
روزهای هفته ٩
ماه هاى سال ©
دانشجويان يى كلاس ©
كاربرد درخت:براى داده هايى با سلسله مراتب يكسان "
هائند كارمندان يى شركت ©
صفحه 202:
Berri Outs Bad Trees ۵
& عنصری که در بالاترین مرتبه قرار دارد. يا ريشه ناميده
ميشود.
ی عناصریکه در مرلتببعد از ريشه قرار می
گیرند نامیدم میشود.
a طاصریهنتنق كه ف امم بان اهر
صفحه 203:
Chisses (Pan OP Picture 0.0(
childreft of
Integer || Double Exceptioy| FfleOutputStrean
great grand child of
صفحه 204:
58
" یک درخت از یک مجموعه عناصر متناهی تشکیل
شده است.
اولین عنصر ریشه نامیده می شود.
* مابقی عناصرزیر درخت نامیده ۲ و subtrees
"می شود.
صفحه 205:
صفحه 206:
صفحه 207:
Purect, Crandporec, Gibliocps, Ouwwestvrs, Orsvendtacts
صفحه 208:
Integer || Double
صفحه 209:
A A سا
به هرسطح یا اوررورا در درخت یک شماره میدهیم:
ريشه در () امرس قرار دارد.
زیر درخت های ريشه از سطح )شروع می شوند.
البتماعردا ريشه مى تواند از سطح یک نیز باشد بنابراین
اورسا مربوط به زیر درخت های ريشه | سطح 0 شروع
میشود.
صفحه 210:
oP levels وی ات
كم
2-5
سل
F
a
|
\_
HunuineEscepie
L
صفحه 211:
F HeOutputStreafn
20
3
Exception,
Double
Oode Oeqer = Ducwber OP. Chittreu
Integer
صفحه 212:
Pree Oeyrer = Dux Oode Deyrer
ie 3
ای
Integer || Double Exception, FileOutputStrea:
20
Degree of tree
= 3.
صفحه 213:
۱ مها
" درخت دودویی از تعداد محدودی عنصر تشکیل شده است.
* اولین عنصر آن ريشه می باشد.
درخت دودویی درختی است که درجه هر گره در آن یا
صفر باشد یادو.
تعریف:درجه گره:شامل تعداد زیر درخت های آن گره
ميباشت,
اگر درجه گره دو باشد دو زیر درخت آن زير درخت هاى
چپ و راست نامیده می شوند.
صفحه 214:
۴ هر گره در درخت باینری درجه بیشتر از دو ندارد.
" یک درخت دودویی می تواند خالی باشد اما درخت
معمولی نمی تواند خالی باشد.
صفحه 215:
* در درخت باینری زیر درخت ها دارای ترتیب می باشند.اما در
درخت معمولی برای زیر درخت ها ترتیبی قائل نیستیم.
0 ®
* ترتیب زیر درخت ها:
* متفاوت هستنداگر به دیددرخت باینری به آنها نگاه کرد.
* یکسان هستند اگر به دیددرخت معمولی به آنها نگاه کرد
صفحه 216:
لسستستسا
6 (۲ +م) * ( +ع) + 9.89 + -ع
* عبارت محاسباتی بالا تسکیل شده از:
Operctors © )+ -, /, *).عملكر ها//
Opernns (u, b, vd, &, Py, k, 9.28, (a +b), (7 + ©
IPs isle xt), et.)
A(,)) Detcviters ©
صفحه 217:
| مهس
8 انواع عملگر ها:
Gls Sle & دودویی:نیازمند دو عملوند هستند.
utb
9
5
" عملكر هاى يكانى:نيازمند يك عملوند هستند.
qt
با
صفحه 218:
۱ سم
& روش معمولی برای نوشتن یک عبارت.
# عملگر های دودونی میان دو عملوند قربار می گيرند.
u*b
utb*s
u*blo
o— Pith + 0.06 + (c +a) * (a +b)
صفحه 219:
۱ سیم سا
* کدام عملگر زودتر اعمال می شود؟
utb*o
u*btold
* برای عملگر هاترتیب یا اولویت قائل می شویم
(-)prieriy(*) = prionty(/) > prioriy(+) = priory
عملگری زودتر اعمال می شود که بالاترین اولویت را
داشته باشد.
صفحه 220:
[oe reer ۱
* اگر عملگرهایی که در عبارت قرار می گیرند دارای
اولویت یکسان باشند از چپ به راست عملگر ها را روی
عملوندها اعمال كنيد.
utb-o
a*blold
صفحه 221:
۳ ۱6 دأو عع ds Wand To Purse
* _ سه روش برای نمایش یک عباریت محاسباتی داریم:
* 10:که درآنلبندا عملوندچپاب عدعلگودر وسط/
ونهایتاعملوند راست قرار می گیرد.
»طم :كه دريآنلبتدا عملكريا ريشه / ب-عدعلوندچپ/
ونهايتاعملوند راست قرار مى كيرد.
“اوم :كه در آنلبتدا عملوندجيصلكريا ريشه /
بعدعلوندراست/ونهایتا ريشه قرار میگیرد.
صفحه 222:
مثال:
م 10۳-۰۱
+Pvsihix = ob
[cost (Pore
صفحه 223:
| (Cxaswples
=utb co ®
abc* +
*Infix=a*b+
86 ab*c+
* Infix = (a + b) * (c-d)/
(e + f) abt+cd- * ef +/
صفحه 224:
۱ تست
© ارو بت ان Replace
+ << ه 0
+ ط © ه << وا + و +
<< و ۶
-ab=>u?b-
صفحه 225:
عبارت محاسباتی را از. چپ به راست بخوانید
به هر لسن يا عملوند رسيديددر يشته عاصام كنيد.
زمانى كه به عملوند رسيديد از يشته مكنيد وعملكر
راروى أن اعمال كنيد.
این روش برای اين است که در »زاجم عملگر بعد
از عملوند ها می آید.
صفحه 226:
مامیآمر) ست |
" (ط+ 6 * (ك - م) / (ع + ج)
/+ubtod-*eP ®
bt+od-*eP 6 +/
4 0*61 قرب 8
cd-*ef+/ ۰
stac
صفحه 227:
۳۳ (vatuatioa
(& +P)/(¢-d)* (a+b) ®
/+abtod-*eP 6
/+ bt+od-*eP 6
s +cd-*ef+/
s cd-*ef+/
۰ d-*ef+/
۰ - * 6 ۲ + _
° و stac
صفحه 228:
6+ (۱-۰ 6+ ۴
+ * ۳
۰ ef+/
stac
صفحه 229:
۴ (9 +م) * (-66) ۱( +ع)
۱+ Sef se
۰ ef+/
۶ E+]
۰ aay
° /
stac
صفحه 230:
۴ (9 +م) * (-66) ۱( +ع)
[+ Sef se
۰ ef+/
3 17
e +/
۶ /
stac
صفحه 231:
| Prefix Pore
درء<جمم ابتدا عملكر و سيس عملوند جب ونهايتا "
عموند راست مى ايد.
با + و - رن
+Posttix = ub
Prefix = tab
صفحه 232:
مس( وه 006
صفحه 233:
0 uw
Sarr
1 45
(--ج)/(
*(at
b)®
Ko
صفحه 234:
Oerits OP Bitar Pree (Pore
کار با الگوریتم درخت باینری بهینه تر از عبارت
محاسباتی است.
Oivay Pree a
صفحه 235:
صفحه 236:
۱ ل Wests. او سمالي
آخرین گره در درخت باینری معرف ارتفاع می باشد.
حداقل تعداد گره ها در we
درخت دودویی( میباشد.
صفحه 237:
Dusber OF Dodes من
* | برای درخت کامل:درختی که تمام گره های سطح آخرش وجود داشته باشد. برای محاسبه
يتعداد كره هااز روش زیر:
5 &
Maximum number of
nodes
+ ... + 8 +4 + 2 + 1 ع
۳-1
صفحه 238:
ِ سا 8 OP Order مها
* اگر ب تعداد گره های یک درخت باینری باشد محدوده
آن :
۴ 6-0 > و > |
logy, (wd) <=k<=u 8
صفحه 239:
Cull (Dicer Tree
۳ تعدادگره ها در یک درخت دودویی به ارتفاع با:
adhe OF — (|
©veé ۵
ارتفاع در درخت کامل بالا ) میباشد.
صفحه 240:
0 Oodes Ia )© Pull سم
# تعداد نودهادر درخت باینری از تا ) - 6 متغیر است.
* شمارش سطوح از بالا به پایین می باشد.
* در هر سطح شمارش گره ها از چپ به راست می باشد.
6 ۵ و tb
صفحه 241:
۳ Oxnober Properties
6 < و ts
والد هر گره مثل : درگره (/: آن میباشد ,البته به استثنای
0 < :. زیرا:
= ) 2 ۱ ريشه میباشد وريشه وال ندارد .
صفحه 242:
۳ )ای( ١
* گره چپ ؛ در :63 میباشد. ۳
* ب تعدادگرم هاوی کر خنب اشد . لگر ب < 2 باشد آنگامز
دارای فرزند چپ نمی باشد.
صفحه 243:
جج دجس سیسات
» < و ts
۴ گره راست : در 0+0 میباشد.
8ب تعدادگره هاویکدرختباشد . لگر ن < )+2 باشد آنگار
دارای فرزند راست نمی باشد.
صفحه 244:
Coppi Drea row ik 3 Docker
® در یک درخت باینری تعداد گره ها میان تا »
می باشد.
* اگر درخت شامل هر ب تا باشد آنگاه به آن
درخت ,درخت کامل گویند و سطر آخر کاملا پر نشده
باشد و گره ها ازچپ به راست قرار گرفته باشد.
صفحه 245:
—
© ١ »” نا » 6 © ١
" مثال:درخت كامل را با 0) گره در نظر بكيريد.
صفحه 246:
برای نمايش درخت دودویی می توان از آرایه استفاده
کرد.
"" نمایش با استفاده از ليست های پیوندی
صفحه 247:
muy Represeuuiva
ابتداكره هاى يى درخت را به صورت سطحى I Devel Order
چپ به راست شماره گذاری کرده سپس درخت را سطحی پیماین
کرده به این صورت که گره در [1]جج؛ قرار مى كيرد.
۱۳۱۱۱
صفحه 248:
[Sh Ohms سین ۳ 1
يه
" براى نمايش يك درخت دودویی با استفاه ازیک آرايه
با سایز)+ب تا "(نیاز داریم.
tree[
]
صفحه 249:
Represrutction سس
إد كه دارای دو اشاره گر یکی به راست.
*_تمام گره های درخت باینری در نمایش پیوندی به صورت یک نود نمایش داده می
ویکی به چپ دارد
*_ کل فضایی که
جهت نمایش لیست پیوندی:
required by mr ete) مسج
یم برای ب گره درخت بایتری
صفحه 250:
, سس
۱ )هه | کرسم:ظ) عووال) The
تنل ۳
Oia )و
1
واه زان ز
اه جله<ا)ع“الرد:6) رز // ز بر درخت چب
ان
Bir /DreeOode ricf // زیر درخت راست
صفحه 251:
Cxavple
55 4
صفحه 252:
revrder
سوه
ostorder
Level order
صفحه 253:
۳ ۱ 5 ١
0
ازوزرمیشود.
صفحه 254:
revrder
سوه
ostorder
Level order
صفحه 255:
snl)
) !<
۱۸۸
)
احا )سل 0 سر
i preOrder (LridhOhd
صفحه 256:
| reer ابو (vet = prict)
صفحه 257:
| reer ابو (vet = prict)
abdghei cf j
صفحه 258:
| reer OP G Pree
/*+ab-cdtef
معادل »70262 در عبارت محاسباتی!
صفحه 259:
order Mraversal
ره ۱ الب |)
(1 != ofl)
موز
j visit(!)
Order (triqhtChitd)
صفحه 260:
| Cxowple (vist = pric)
صفحه 261:
| سس = privi)
gdhbeiafjc
صفحه 262:
1 (متاضی2) م۳ بر) دس
KA
gdh beia fjfje
صفحه 263:
| OF Cxpressiva Tree
a+b * 6۵ - 0/ et+f
صفحه 264:
Traversal | ول رون
postOrder(Bicay/PreeOode})
}
(1 != ofl)
5 postOrder وان ۸(
5 postOrder ار
i vieit(!)
صفحه 265:
oo عاممومج) (visit = print)
صفحه 266:
oo عاممومج) (visit = print)
KA
ghdiebjfca
صفحه 267:
oo OP G& Tree
ab+cd- *ef +/
معادل :]0051 در عبارت محاسباتی!
صفحه 268:
Traversal (pplicatioas
KX
صفحه 269:
تسم
-bet | be the tree root
(t != ofl)
}
jvisit | cod put its chides oo o PICO queue
rewove 0 ude Prow the CIPO queue ond
swell it t
صفحه 270:
1 (سم < نم عامصممج) دیا
AN
abcdef ghi j
صفحه 271:
ع ع هی ی
owe (xawples
preorder
اه <
inorde
r =
ab
postord
er =
ab
level
order =
ab
وأ" يي" م" ي*
صفحه 272:
reorder (ud (Postorder
وا < =
26 2 = ۳
صفحه 273:
۳
ee fttorder —~ydkKbeiuFfio ®
preorder =ubdykeiokj ®
gdhb 110
ei
صفحه 274:
gdhb fic
5 preorder = bdykeicoPj ®
,ا ريشه بعدیلسل» زیر درختچپ/ م زیر ۴
درختولست
x
gd ei
h
صفحه 275:
aorder (ud Preorder
[+
ZN
006 ei
ho opreorter = ۲۱6
ريشه بعدومىياشد./ع زیر در ختچپوازیر 2 "
tly petal yd ya
0
۳1 Si
4» “nr
صفحه 276:
Oud Postorder سا
در له امرواپیمایش از چپ به راست می باشد
در لس بوم)پیمایش از راست به چپ می باشد.
iworder =ydkbeiukio
postorder =ybkdiebjPou
{Pree د ات
اكلم // زير درخت جب
۲ // زيردرختولست
صفحه 277:
Qo bevel Order سا
در ان اسجاپیمایش از چپ به راست می باشد.
۱
order = abode Pyhij ارو
Sree root is a
اكلم // زير درختجب
زیردرختولست
صفحه 278:
لا صف بأ الويت بالا
" صف با الويت يايين
صفحه 279:
* اعمال زير را می توان روی آن انجام داد.
جك كردن اينكه صف خالى است يا نه؟
سايز و اندازه صف
اضافه كردن يك عنصر به ليست
بيدا كردن عنصر با كمترين اولويت
حذف عنصرى با كمترين اولويت
صفحه 280:
* اعمال زير را می توان روی آن انجام داد.
هر عنصر
جك كردن اينكه صف خالى است يا نه؟
سايز و اندازه صف
اضافه كردن يك عنصر به ليست
پیدا کردن عنصر با بیشترین اولویت
حذف عنصری با بیشترین اولویت
صفحه 281:
isCwpty, size, aed yet => O((|) عون
put ced rexepue => O(loy 1) fico
كه در آن » طول ليست مى باشد
صفحه 282:
" عناصر را مرتب شده در اولویت قر
" گزینش عنصر با توجه به کلید اولویت آن:
۰ اگر عنصری با کمترین اولویت را خواستیم انتخاب کنیم باید
صف به صورت صعودی مرتب شده باشد.
* اگر عنصری با بیشترین اولویت را خواستیم انتخاب کنیم باید
صف به صورت نزولی مرتب شده باشد.
صفحه 283:
مرت کنیدپنج
8 از صف با الویت بالا
* ابتدا عناصر را در یک صف ب الویت بالا قرا
as
الى هي
* پنج مرتبه عمل حذف را انجام دهيد در نهايت عناصر از راست
به جب مرتب مى شوند.
صفحه 284:
Gorted Ona
(Pte = Oux Priority Queue
[
5 الو
بالا
يت
صفحه 285:
Gorted Ora
5 الو
بالا
J
۲7۳۷۲۲۲
[«
OPter Pirst Rewove Dux O;
صفحه 286:
Gorted Orray
5 الو
بالا
3
Pte = Rewove Dux سیم
[
صفحه 287:
Gorted Ora
1
بالا
يت
تتلا جوم
سس و
صفحه 288:
صف با
ت بالا
مه موه
صفحه 289:
صف با
ت بالا
مه موه
صفحه 290:
we * (د
wT 1
eve is O. vee او
0 3 = ]1777
* (0)() کار
صفحه 291:
صفحه 292:
صفحه 293:
6
ريشه کمترین مقدار را دارد
صفحه 294:
6 e
ريشه بيشترين مقدار. را دارد
صفحه 295:
صفحه 296:
درخت کامل با ۵ گره
صفحه 297:
درخت کامل با ٩ گره وهمچنین مره
ree
صفحه 298:
درخت کامل با ٩ گره وهمچنین »جر
ree
صفحه 299:
صفحه 300:
0 1 2 3 ۰۸ 5 6 7 8 9 10
صفحه 301:
صفحه 302:
۰ ظ) و۱" امحعاظ) Dax Wea
درخت کامل با 00) گره
صفحه 303:
۰ ظ) و۱" امحعاظ) Dax Wea
()گره جدید می باشد
صفحه 304:
۰ ظ) و۱" امحعاظ) Dax Wea
000 گره جدید می باشد
صفحه 305:
۰ ظ) و۱" امحعاظ) Dax Wea
000 گره جدید می باشد
صفحه 306:
۰ ظ) و۱" امحعاظ) Dax Wea
000 گره جدید می باشد
صفحه 307:
۰ ظ) و۱" امحعاظ) Dax Wea
000 گره جدید می باشد
صفحه 308:
۰ ظ) و۱" امحعاظ) Dax Wea
درخت کامل با 0 گره
صفحه 309:
۰ ظ) و۱" امحعاظ) Dax Wea
© گره جدید می باشد
صفحه 310:
۰ ظ) و۱" امحعاظ) Dax Wea
© گره جدید می باشد
صفحه 311:
۰ ظ) و۱" امحعاظ) Dax Wea
© گره جدید می باشد
صفحه 312:
3
ASL) O(log a) ol Suen سایز
| مقدار ب باشد
صفحه 313:
بزرگترین مقدلر. در ريشه قرار دارد.
صفحه 314:
پس از آنکه بزرگترین مقدار حذف شد
صفحه 315:
eo
در (Malad heap عنصر قرار مى كيرد.
heap 4 1,0 اضافه كنيد.
صفحه 316:
لط
صفحه 317:
لط
صفحه 318:
لط
صفحه 319:
9 بزرگترین عنصر قرار می گیرد.
صفحه 320:
پس از آنکه بزرگترین مقدار حذف شد
صفحه 321:
اکنوز تعدا
ون ده
keup 5 تعداد© عذ
© عنصر قرا
J
می
صفحه 322:
صفحه 323:
صفحه 324:
صفحه 325:
OP Rewove Dux Cleweut
صفحه 326:
dO, ,9 ,6 ,2 ,9 ,9 ,6 ,9 ,9 ,4 ب] 2 یه نو
ad
صفحه 327:
ابتدا موقعیت 0/» را در آرایه فوق محاسبه کرده و سپس از آن
کره در درخت شروع کنید
صفحه 328:
موی عن() بسودنرا در درختچکک نید.در درختب7
دوج امحتولوريشه از كليه عناصر لنب زركتر مىياشد.
صفحه 329:
لط
صفحه 330:
لط
صفحه 331:
لط
صفحه 332:
لط
صفحه 333:
لط
صفحه 334:
مکان 00 با 6 عوض می شود.
صفحه 335:
مکان 40 با 6 عوض می شود.
صفحه 336:
لط
صفحه 337:
مکان )را بیابید؟
صفحه 338:
يافتن مكان 0
صفحه 339:
یافتن مکان )
صفحه 340:
یافتن مکان )
صفحه 341:
انجام شد.
صفحه 342:
ارتقاع » heap = h 4s
تعداد زیر درخت ها با ريشه در 11 2 level j
پیچیدگی زمانی برای هر زیر درخت 2 (1+-0)5
صفحه 343:
صفحه 344:
كنيد يك نود خارجى هر جایی زیردرخت ۳
نداشته باشد.
به همين دليل به آن درخت باينرى كسترش يافته
مى كويند.
صفحه 345:
صفحه 346:
Tree تسم
ee
=n +1 تعداد گره های خارجی
صفحه 347:
طول كوك تين منتتير وه ود خارجی در
درخت هاى ريشه محاسبه كرد.
صفحه 348:
Ld
5 5 ۱
صفحه 349:
له سا هی
Diciioray Operciivas ©
vei(hev)
voke) وان
rewwove(hev)
سوه مان
()sorecrd
)اس (لندیسگره در درختباینریرا برمیگردلند.)
مج هر (کند محترلواندیسدر در خثبایتریرا حذفمي)
صفحه 350:
L
HashTable | O(n) 0
Binary O(n) O(log n)
ie O(log n) O(log n)
Binary
صفحه 351:
D is number of buckets
صفحه 352:
8 برای هر گره دلخواه > کلیه عناصر زیر رخ
چپ آن کوچکتر از آن وکلیه عناصر زیر درخت
راست آن بزرکتر. از آن می باشد.
صفحه 353:
فقط کلید ها را نشان داده است.
صفحه 354:
پیمایش میانوندی آن با ره امکا ن پذیر است.
صفحه 355:
Susy =O(height) = O(n
صفحه 356:
Put 35.
صفحه 357:
صفحه 358:
Put 18.
صفحه 359:
res
Suse < put() =O(height).
صفحه 360:
گرهآدر وضعیت های
* اگر گره برگ باشد
*اگر گره از درجه یک باشد.
*اگر گره از درجه دو باشد
صفحه 361:
حذف كره برك - 70
صفحه 362:
صفحه 363:
حذف گره تک فرزندی < ۳0)
صفحه 364:
a
0
I
حذف گره تک فرزندی
صفحه 365:
حذف گره دو فرزندی < dD
صفحه 366:
res
جابه جا كنيد با بزرگترین در زیر درخت چپ ویا با
کوچکترین در زیر درخت راست.
صفحه 367:
جابه جا كنيد با بزرگترین در زیر درخت چپ ویا با
کوچکترین در زیر درخت راست.
صفحه 368:
جابه جا كنيد با بزرگترین در زیر درخت چپ ویا با
کوچکترین در زیر درخت راست.
صفحه 369:
بزركترين كليد يا بايد برگ باشد یا گره تک فرزندی
صفحه 370:
res
حذف گره دو فرزندی 000 <
صفحه 371:
res
جابه جا کنید با بزرگترین در زیر درخت چپ
صفحه 372:
oe
جابه جا کنید با بزرگترین در زیر درخت چپ
صفحه 373:
2“
جابه جا کنید با بزرگترین در زیر درخت چپ
صفحه 374:
610۳1(۰) 0< پیچیدگی
صفحه 375:
Pree 1 موه رسب ص۳۴
جستجوی باینری
در هر نود یک فیلد اضافی وجود دارد:
<< شمارشتعداد نود هایچپدرخت
صفحه 376:
odexed icra Geurch Tree
leftSize 0
صفحه 377:
[2,6,7,8,10,15,18,20,25,30,35,40]
rank(2) = 0
rank(15) = 5
rank(20) = 7
leftSize(x) = rank(x)
صفحه 378:
sorted list =
12.6,7,8.10,15,18, 20,25,30,35,40]
صفحه 379:
sorted list =
12,.6,7,8,10,15,18,20,25,30,35,40]
صفحه 380:
۴ << ملی: ز
elect را لنتخابکن.
۴ رواد > لب ۱
عنصری انتخاب می شود که محتوای «جلم: آن در زیر درخت
چپ رمی باشد.
۴ را < بل ۱
عنصری انتخاب می شودکه محتوای ()-حت09ط» - ععل) آن
در زیر درخت راست عرمی باشد.
صفحه 381:
list = [a,b,c,d,¢,f,g,h,i,j,k,1]
صفحه 382:
9 jw
list = [a,b,c,d,e,f,g,h,i,j,k,1]
صفحه 383:
chiar)
list = [a,b,c,d,e, m,f,g,h,i,j,k,1]
find node with element 4 (e)
صفحه 384:
chiar)
list = [a,b,c,d,e, m,f,g,h,i,j,k,1]
find node with element 4 (e)
صفحه 385:
chiar)
را به رلستگره و لضافه کردم لست
در نتیجه زیر درخت راست 6 به عنوان زیر درخت راست
«قرار می گیرد.
صفحه 386:
توا 2ب
«را بعنولنفرزند چپدر زیر درختولست
گرم و قرار دهید.
صفحه 387:
۱ سحت"
8 پیچیدگی < (0/))
ساختمان دادهها و الگوريتم
رشته علوم کامپيوتر
ناصر آيت
در مورد ساختمان داده
ساختمان داده روشی است برای معرفی و دستکاری داده
و کلیه برنامه های معرفی داده
برای معرفی داده نیازمند یک الگوریتم میباشد.
در مورد ساختمان داده
روش های طراحی الگوریتم نیازمند پیشرفت برنامه هایی است که برای
نگهداری داده است.
در علوم کامپیوتر مطالعه ساختمان داده ها مهم وضروری میبا شد.
Perequisites
++C
پیچیدگی
Big oh , theta and omega notation
Sorting
ترتیب زیر را در نظر بگیرید:
]a[0],a[1],…, a[n-1
پس از مرتب سازی صعودی داریم:
]a[0] <=a[1] <= ….<=a[n-1
example:8,6,9,4,3 => 3,4,6,8,9
Sort metods
Insertion sort
Bubble sort
Selection sort
Count sort
Shaker sort
Shell sort
Heap sort
Merge sort
Quick sort
اضافه کردن یکinsert an element
لیست ترتیبی زیر را در نظر بگیرید:
input: 3, 6, 9, 14
عنصر 5را به لیست فوق اضافه کنید.
output: 3, 5, 6, 9, 14
Insert An Element
insert 5
14 ,9 ,6 ,3
. را با آخرین عنصر لیست مقایسه کنید5 عدد
Shift 14 right to get 3, 6, 9, , 14
Shift 9 right to get 3, 6, , 9, 14
Shift 6 right to get 3, , 6, 9, 14
: خروجی5 با اضافه کردن
Output: 3, 5, 6, 9, 14
Insert An Element
insert into a[0:i-1] //
;Int j
For (j=i-1 ; j>=0 && t <a[ j] ;j--)
A[ j+1] = a[ j]
; A[ j+1] = t
Insertion sort
.1
.2
لیستی با سایز 1در نظر بگیرید”.اولین عنصر را
داخل لیست قرار دهید“.
عمل insertionرا تکرار کنید بطوریکه ترتیب داده
ها حفظ شود
Insertion sort
Sort 7, 3, 5, 6, 1
Start with 7 and insert 3=> 3,7
Insert 5=>3, 5, 7
Insert 6=>3, 5, 6, 7
Insert 1=>1, 3, 5, 6, 7
Insertion sort
For (i=1 ; i<a.length ; i++)
insert a[i] into a[0:i-1] //{
code to insert comes here//
}
Insertion sort
For (i=1 ; i<a.length ; i++)
insert a[i] into a[0:i-1] //{
code to insert comes here//
int t =a[ j]
;int j
For ( j=i-1 ; j>=0 && t <a[ j] ; j--)
A[ j+1] = a[ j]
; A[ j+1] = t
}
Complexityیا پیچیدگی
.1
.2
.3
پیچیدگی مکانی /حافظه ای
پیچیدگی زمانی
شمارش یک عملگر خاص
شمارش تعداد مراحل
پیچیدگی Asymptotic
Compration count
شمارش مقایسه ای
For (i=1 ; i<a.length ; i++)
insert a[i] into a[0:i-1] //{
code to insert comes here//
int t =a[ j]
;int j
For ( j=i-1 ; j>=0 && t <a[ j] ; j--)
A[ j+1] = a[ j]
; A[ j+1] = t
}
Compration count
یک نمونه کاراکتری از nرا در نظر بگیرید ،که در
آن nطول لیستی باشد که می خواهیم روی آن
Insertion sortرا انجام دهیم.
و تعداد توابع این نمونه کاراکتری را بشمارید.؟؟؟؟
Determine count as a function of this instance
???.characteristic
Compration count
For (j=i-1 ; j>=0 && t <a[ j] ;j--)
;A[ j+1] = a[ j]
چند مقایسه انجام شده است ؟
Compration count
)For (j=i-1 ; j>=0 && t <a[ j] ;j--
];A[ j+1] = a[ j
شمارش تعداد مقایسات وابسته به ][aو tبا توجه به i
Compration count
Worst-case count=maximum count
Best –case count=minimum count
Avarage count
Worst-case Compration count
For (j=i-1 ; j>=0 && t <a[ j] ;j--)
;A[ j+1] = a[ j]
A=[1,2,3,4] and t=0 =>4 compares
A=[1,2,3,..,i] and t=0 =>i compares
Worst-case Compration count
for(int i=1; i< n ; i++)
For (j=i-1 ; j>=0 && t <a[ j] ;j--)
;A[ j+1] = a[ j]
: تعداد کل مقایسات
Total comprase =1+2+3+…+(n-1)
n/2)n-1(=
Step count
یک مرحله از محاسبات وابسته است به مقادیر n
برای مثال :
add , 100 subtracts,1000 multiplies 10
فقط یک stepمحسوب میشود .
وبه این مفهوم نمی باشد که با افزایش nیک مرحله
نیز به تعداد stepاضافه شود.
Step count
s/e
For (i=1 ; i<a.length ; i++)
insert a[i] into a[0:i-1]
code to insert comes here
int t =a[ j]
int j;
For ( j=i-1 ; j>=0 && t <a[ j] ; j--)
A[ j+1] = a[ j]
A[ j+1] = t ;
}
1//
1
0 //{
0
1
1
1
0
Step count
یا یک نمی باشد0 همیشهs/e
X=mymath.sum(a,n)
Where n is the instance characteristic has a s/e
count of n
Step count
s/e
step
For (i=1 ; i<a.length ; i++)
insert a[i] into a[0:i-1]
code to insert comes here
int t =a[ j]
int j;
For ( j=i-1 ; j>=0 && t <a[ j] ; j--)
A[ j+1] = a[ j]
A[ j+1] = t ;
}
1
0 //{
1//
0
1
1
1
0
i+1
i
Step count
For (int i=1;; i<a.length; i++)
}2i+3{
Step count for
For (int i=1; i<a.length;; i++)
Is n
Step count for body of for loop is
3(n-1)+)n-1+…+1+2+3(2
n +3(n-1))n-1(=
)n+3()n-1(=
محاسبه پیچیدگی در مرتب سازی درجی
)O(n2
به چه معنی می باشد؟
محاسبه پیچیدگی در مرتب سازی درجی
بدترین حالتӨ(n2):
بهترین حالتӨ(n) :
بنابراین انتظار میرود بدترین حالت زمانی است که n
دوبل میشود(تکرار میشود).
محاسبه پیچیدگی در مرتب سازی درجی
آیا )O(n2خیلی زیاد است؟
الگوریتم تجربی( )practicalچه میباشد؟
Faster Computer Vs Better
Algorithm
پیشرفت الگوریتم ها مفید تر از پیشرفت سخت افزار
است.
ساختمان داده
Data Structure
انواع داده :
داده هایی که در یک مجموعه قرار می گیرند(در ارتباط).
}Ex: integer= {0, +1,-1,+2,-2,….
}days of week = {S,M,T,W,TH,SA
Data object
.داده هایی که نامربوط با هم هستند
:Example
MyDataObject={apple, chair, 2,5,red,green ,jack}
Data Structure
+ Data oject
روابطی که وجود دارد برای مقایسه میان عناصر
Ex:369<370
284=280+4
Data Structure
:میان عناصری که مقایسه میشوند در یک مثال
369
is more signification than 6 3
is immediately to the left of 6 3
is immediately to the right of 6 9
Data Structure
روابط خاص معموال توسط عملگر های خاص روی
چندین نمونه داده ایجاد می شود عبارتند از:
Add,subtract, predecessor,multiply
،تفریق ،جمع
ضرب
Linear (or Ordered) lists
Instannces are of the form
)e0,e1,e2,….,en-1(
Where ei denodes a list element n>=0 is finite
List size is n
Linear (or Ordered) lists
)L= (e0,e1,e2,e3,….,en
روابط زیر بر قرار است:
e0 :عنصر جلوی لیست میباشد”zeroth element“ .
en-1:عنصر آخرلیست میباشد”last elements“ .
ei+1 :دقیقا بعداز eiقرار می گیرد.
:مثالهایی از لیست های خطی
Student in COP3530=(jack,jill,
Abe ,Henry,Mary ,…,judy)
Exams in COP3530=(exam1, exam 2, exam3)
Days of Week=(S,M,T,W,TH,SA)
Months=(Jan,Feb ,Mar ,Apr,…,Nov,Dec)
)(Linear list Oprations-size
اندازه گیری سایز لیست
:Example
L=(a,b,c,d,e)
Size=5
Linear list Oprations-get(the index)
.یک عنصر را میگیرد و اندیس آن را بعنوان خروجی می دهد
:Example
L=(a,b,c,d,e)
Get(0)=a
Get(2)=c
Get(4)=e
Get(-1)=error
Get(9)=error
Linear list Oprations-indexof (the element)
.اندیس هر عنصر را برمی گرداند
L= (a,b,d,b,a)
Index of(d)=2
Index of(a)=0
Index of(z)=-1
Linear list Oprations-remove(the index)
.حذ ف را انجام داده و محتوای اندیس مورد نظر را برمی گرداند
L=(a,b,c,d,e,f,g)
Remove(2) returns c
and L become (a,b,d,e,f,g)
index of d,e,f and g decrease by 1
Linear list Oprations-remove(the index)
.حذ ف را انجام داده و محتوای اندیس مورد نظر را برمی گرداند
L=(a,b,c,d,e,f)
Remove(-1)=>error
Remove(20)=>error
Data structure specification
Language independet
Abstract Data Type
Java
Abstaract class
Liner List Abstaract Data Type
{
عملگر ها
AbstractData Type Linear List
instances
Ordered finit collection of zero or more elements
:) (Empty
نتیجه درست را بر می گرداند اگر و فقط اگر لیست خالی باشد ،در غیرنتیجه
false :میبا شد.
:) (Size
اندازه لیست را بر می گرداند.بعبارتی تعداد عناصر داخل لیست را بر می
گرداند.
Data Representation Methods
Array ---chapter 5
Linked---chapter 6
Simulated
Linear List Array Representation
e
6
5
4
L=(a,b,c,d,e)
3
d
2
c
1
b
a
Right to Left Mapping
a
b
c
d
e
Mapping That Skip Every Other position
d
c
b
a
Wrap Around Mapping
c
b
a
e
d
Represention Used In Text
6
5
4
3
e
d
2
1
c
b
a
Add/Remove An Element _1
Size=5
e
d
c
b
a
Add/Remove An Element_2
Add ( l, g)
size-=6
e
d
c
b
g
a
][Length of Array element
چون نمی دانیم چه تعداد عنصر در لیست وجود خواهد
داشت ،بنابراین باید یک مقدار اولیه برای آن فرض
.کرد.و سپس بر حسب نیاز آن را افزایش داد
Liner List Abstaract Data Type
):Get (index
خروجی آن اندیس عنصر میباشد بر طبق جایگاه آن ودرصورتی مقدار()-1
را برمی گرداند که عنصر مورد نظر در لیست نباشد.
):Remove (index
عنصر را حذف کرده و محتوای عنصر را برمی گرداند.
):Add (index, x
عنصر xرا در indexداده شده اضافه کرده و پس از آن شماره اندیس ما
بقی عناصر از موقعیت جاری یک واحد افزایش میابد.
:) (Output
خروجی لیست است که از چپ به راست مرتب می شود.
Linear List As Java abstract Class
Public abstractclass Linear ListAsAbstractClass
{
;)(Public abstarct Boolean isEmpty
;)(Public abstarct int size
;Public abstarct object get(int index)
;Public abstarct int indexOf(Object the element)
;Public abstarct object remove(int index)
;Public abstarct void add(int index, Object the element)
;)(Public abstarct string to sorting
}
Linked Representation
عناصر لیست در حافظه با ترتیبی دلخواه
نگهداری می شوند.
explicit information (called a link)
اطالعات صریح که لینک نامیده می شوند
برای رفتن از یک عنصر به عنصر دیگر
استفاده میشوند
Memory Layout
.برای نمایش لیست ها از آرایه ها استفاده می شود
L = (a,b,c,d,e)
a b
c d e
هرلینک از یک جدول دلخواه استفاده می کند.
A linked representation uses an
arbitrary
layout.
c
a
e
d
b
Linked Representation
b
d
e
تهی می باشد )e( .اشاره گر عنصر
firstNode:
برای اشاره به عنصر شروع استفاده میشود.
a
firstNode
c
Normal Way To Draw A Linked List
firstNode
a
b
c
d
فیلد اشاره گر
فیلد داده
nul
le
Chain
firstNode
nul
le
d
c
b
a
دریک زنجیر یا در یک لیست از اشاره گر هاهر نود نشان دهنده
یک عنصر می باشد.
از یک نود به نود دیگر یک اشاره گر وجود دارد.
اشاره گر آخرین لیست تهی میباشد.
Node Representation
;package dataStructures
class ChainNode
{
;Object element
;ChainNode next
}
next
element
Constructors Of ChainNode
}{ )(ChainNode
null
null
ChainNode(Object element)
{this.element = element;}
ChainNode(Object element,
ChainNode next)
{this.element = element;
this.next = next;}
null
element
next
element
get(0)
firstNode
a
b
c
;checkIndex(0)
;desiredNode = firstNode
;return desiredNode.element
d
nul
le
get(1)
firstNode
a
b
;checkIndex(1)
;desiredNode = firstNode.next
;return desiredNode.element
c
d
nul
le
get(2)
firstNode
a
b
c
d
;checkIndex(2)
;desiredNode = firstNode.next.next
;return desiredNode.element
nul
le
get(5)
firstNode
a
b
c
checkIndex(5); desiredNode =
;firstNode.next.next.next.next.next
;return desiredNode.element
d
nul
le
NullPointerException
firstNode
a
b
c
d
nul
le
desiredNode =
firstNode.next.next.next.next.next.nex
;t
Remove An Element
firstNode
a
b
c
d
remove(0)
firstNode = firstNode.next;
nul
le
remove(2)
firstNode
a
انتخاب کنید
b
cc
beforeNod
راeبخواهد حذف شود
d
nul
le
ابتدا نود قبل از نودی را که
"یعنیfirst node"
beforeNode = firstNode.next;
remove(2)
firstNode
a
b
c
d
beforeNod
e
nul
le
درbeforeNode .اکنون اشاره گرآن را تغییر دهید
beforeNode.next =
beforeNode.next.next;
add(0,’f’)
firstNo
de
f
a
b
c
d
nul
le
newNo
de
نود جدید را انتخاب کنید که حتما دارای فیلد داده واشاره گرباشد
: گام اول.
ChainNode newNode =
new ChainNode(new Character(‘f’),
firstNode);
add(0,’f’)
firstNo
de
f
a
b
c
d
nul
le
newNo
de
آن را بعنوان نود آغاز انتخاب کنید:گام اول.
firstNode = newNode;
One-Step add(0,’f’)
firstNo
de
f
a
b
c
newNo
de
firstNode = new ChainNode(
;new Character(‘f’), firstNode)
d
nul
le
add(3,’f’)
firstNode
a
newNod
e
b
c
f
d
nul
le
beforeNod
e
.را انتخاب کنید2 ابتدا نود با اندیس:گام اول
حال نود جدید را ایجاد کرده بطوریکه دارای فیلد داده و فیلد اشاره گر داشته:گام دوم
باشد.
ChainNode newNode = new ChainNode(new
Character(‘f’),
beforeNode.next);
• finally link beforeNode to newNode
beforeNode.next = newNode;
Two-Step add(3,’f’)
firstNode
a
newNod
e
b
c
f
d
nul
le
beforeNod
e
beforeNode = firstNode.next.next;
beforeNode.next = new ChainNode(new
Character(‘f’),
beforeNode.next);
The Class Chain
The Class Chain
firstNode
a
b
c
d
size =
شمارش.تعدادعناصر لیست میباشد
کاربردChainNode
next (datatype ChainNode)
element (datatype Object)
nul
le
The Class Chain
/* linked implementation of LinearList **/
;package dataStructures
Import c++; // has Iterator
public class Chain implements LinearList
{
data members //
;protected ChainNode firstNode
;protected int size
methods of Chain come here //
}
Constructors
/* ** ایجاد یک لیست خالی/
public Chain(int initialCapacity)
{
firstNode and size: مقادیر اولیه//
null and 0 //
}
)(public Chain
};this(0){
The Method isEmpty
/* ** مقدار درست را برمی گردانداگر وفقط اگر لیست خالی باشد/
)(public boolean isEmpty
};return size == 0{
)(The Method size
/* ** خروجی آن شمارش تعداد عناصر داخل لیست میباشد/
)(public int size
};return size{
The Method checkIndex
throws IndexOutOfBoundsException when@ **/
/* index is not between 0 and size - 1 *
را-1 یا0 **اندیس مربوط به هر عنصر را بر می گرداند و زمانی که/
/*.برگرداند به این مفهوم است که آن عنصر در لیست وجود ندارد
void checkIndex(int index)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException
;)index = " + index + " size = " + size"(
}
firstNode
The
Method get
a
b
c
public Object get(int index)
{
;checkIndex(index)
نود دلخواه راتغییر دهید//
;ChainNode currentNode = firstNode
for (int i = 0; i < index; i++)
;currentNode = currentNode.next
;return currentNode.element
}
d
nul
le
The Method indexOf
public int indexOf(Object theElement)
{
یک زنجیر از نودها را جستجو کنید//
;ChainNode currentNode = firstNode
اندیس نود جاری// ;int index = 0
&& while (currentNode != null
)currentNode.element.equals(theElement)!
{
به نود بعدی تغییر دهید//
;currentNode = currentNode.next
;++index
}
The Method indexOf
اطمینان از اینکه عنصر مربوطه را یافته ایم//
if (currentNode == null)
;return -1
else
;return index
}
Removing An Element
firstNode
a
b
c
remove(0)
;firstNode = firstNode.next
d
nul
le
Remove An Element
public Object remove(int index)
{
;checkIndex(index)
;Object removedElement
نود شروع را حذف کنید// if (index == 0)
{
;removedElement = firstNode.element
;firstNode = firstNode.next
}
remove(2)
firstNode
a
b
c
d
beforeNod
e
nul
le
beforeNodeرا یافته و اشاره گر آن را تغییر دهید
beforeNode.next =
beforeNode.next.next;
Remove An Element
else
q: جایگاهی برای قرار دادن نود جاری میباشد// {
;ChainNode q = firstNode
for (int i = 0; i < index - 1; i++)
;q = q.next
;removedElement = q.next.element
نود دلخواه را حذف کنید// ;q.next = q.next.next
}
;--size
;return removedElement
}
One-Step add(0,’f’)
firstNo
de
f
a
b
c
d
nul
le
newNo
de
;firstNode = new ChainNode(‘f’, firstNode)
Add An Element
public void add(int index, Object theElement)
{
if (index < 0 || index > size)
موقعیت لیست نادرست است//
throw new IndexOutOfBoundsException
;)index = " + index + " size = " + size"(
if (index == 0)
. به جلو اضافه کنید//
;firstNode = new ChainNode(theElement, firstNode)
Two-Step add(3,’f’)
firstNode
a
newNod
e
b
c
f
d
beforeNod
e
beforeNode = firstNode.next.next;
beforeNode.next = new ChainNode(‘f’,
beforeNode.next);
nul
le
Adding An Element
else
عنصر جدید را بیابید// {
;ChainNode p = firstNode
for (int i = 0; i < index - 1; i++)
;p = p.next
اضافه کنید بعد ازp //
;p.next = new ChainNode(theElement, p.next)
}
;++size
}
Chain With Header Node
headerN
ode
a
b
c
d
nul
le
Empty Chain With Header Node
headerN
ode
nul
l
Circular List
firstNode
a
b
c
d
e
Doubly Linked List
firstNode
lastNode
nul
l
a
b
c
d
nul
le
Doubly Linked Circular List
firstNode
a
b
c
d
e
Doubly Linked Circular List With Header Node
headerN
ode
a
b
c
d
e
Empty Doubly Linked Circular List With Header Node
headerN
ode
Arrays
++1D Array Representation In C, and C
Memory
a
b
c
d
start
x = [a, b, c, d] یک نمونه آرایه یک بعدی
د ر خانه های مجاور یکدیگر قرار میگیرند
• location(x[i]) = start + i
Space Overhead
Memory
a
b
c
d
start
space overhead = 4 bytes for start
bytes for x.length 4 +
bytes 8 =
) (میزان فضایی که برای آرایه فوق نیاز داریم
2D Arrays
a آرایه دو بعدی
:declared as
;int [][]a = new int[3][4]
.که در یک جدول نشان داده م شود
a[0][0] a[0][1] a[0][2] a[0][3]
a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]
Rows Of A 2D Array
a[0][0] a[0][1] a[0][2] a[0][3]
a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]
row 0
row 1
row 2
Columns Of A 2D Array
a[0][0] a[0][1] a[0][2] a[0][3]
a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]
column
0
column column
1
2
column
3
++2D Array Representation In C and C
آرایه دو بعدیx
a, b, c, d
e, f, g, h
i, j, k, l
.آرایه های یک بعدی هستند, سطر های آرایه دو بعدی
نمایش آرایه های دوبعد با استفاده از آرایه یک بعدی
x = [row0, row1, row 2]
row 0 = [a,b, c, d]
row 1 = [e, f, g, h]
row 2 = [i, j, k, l]
and store as 4 1D arrays
++2D Array Representation In Java, C, and C
x[]
a b c d
e f
g h
i
k l
j
x.length = 3
x[0].length = x[1].length = x[2].length = 4
Space Overhead
x[]
a b c d
e f
g h
i
k l
j
space overhead = overhead for 4 1D arrays
bytes 8 * 4 =
bytes 32 =
x 8 bytes )number of rows + 1( =
++Array Representation In C and C
][x
a b c d
g h
e f
k l
i
j
این نمایش آرایه آرایه ها نامیده می شود.
با توجه به شکل فوق نیازبه حافظه ای با سایز های 3و4و4و 4برای ذخیره آرایه
های یک بعدی دارد.
یک بلوک حافظه شامل سایزتعداد ستونها و سطرها میباشد
Row-Major Mapping
:Example 3 x 4 array
abcd
efgh
i jkl
آرایه فوق در یک آرایه یک بعدی قرار گرفته است بطوریکه هر عنصر آن یک سطر از
آرایه فوق است و بعبارتی هر سطر آن یک آرایه یک بعدی می باشد.
عناصرداخل هر سطر از چپ به راست مرتب شده اند .
سطرها از باال به پایین مرتب شده اند .
}We get y[] = {a, b, c, d, e, f, g, h, i, j, k, l
row i
…
row 2
row 1
row 0
Column-Major Mapping
abcd
efgh
i jkl
آرایه فوق در یک آرایه یک بعدی قرار گرفته است بطوریکه هر عنصر آن یک
ستون از آرایه فوق است و بعبارتی هر ستون آن یک آرایه یک بعدی می باشد.
عناصرداخل هر ستون از باال به پایین مرتب شده اند .
ستون هااز چپ به راست مرتب شده اند .
}We get y = {a, e, i, b, f, j, c, g, k, d, h, l
Sparse Matrices
… sparseتعدادبیشتر عناصر آن صفر می باشد
… denseتعدادکمتر عناصر آن صفر می باشد
Representation Of Unstructured
Sparse Matrices
هر عنصر غیر صفری در ماتریس اسپارس را میتوان بصورت
زیر نشان داد
)row, column, value(
Single Linear List Example
40300
07500
00000
00620
list =
row
1 1 2 2 4
4
column 3 5 3 4 2
3
value
3 4 5 7 2
6
Array Linear List Representation
row
list =
value
6
1 1 2 2 4 4
column 3 5 3 4 2 3
3 4 5 7 2
element
0 1 2
3 4 5
row
1 1 2 2
column
3 5 3 4
4 4
Chain Representation
ساختار نود
row
valu
e
col
nex
t
Single Chain
row
1 1 2 2 4
4
list = column 3 5 3 4 2
3
value 3 4 5 7
2 6
1 3
3
1 5
4
firstNode
2 3
5
2 4
7
4 2
2
4 3
6 null
One Linear List Per Row
300
40
500
07
row1 =
(5,4)]
row2 =
(4,7)]
row3 =
row4 =
(3,6)]
[(3, 3),
[(3,5),
[]
[(2,2),
Array Of Row Chains
ساختار نود
nex
colt value
Array Of Row Chains
null
3
300
40
500
07
000
00
3
5
4
null
3
5
4
7
nul
l
null
2
row[]
2
3
6
Orthogonal List Representation
.Node structure
row
dow
n
col
nex
t
value
Row Lists
1 3 3
300
40
500
07
000
00
2 3 5
nul
l
4 2 2
4 3 6
n
1 5 4
n
2 4 7
n
Column Lists
1 3 3
0300
4
7500
0
0000
0
0620
2 3 5
4 2 2
n
4 3 6
n
1 5 4
n
2 4 7
Orthogonal Lists
1 3 3
300
40
500
07
000
00
2 3 5
nul
l
4 2 2
n
row[]
4 3 6
n n
1 5 4
n n
2 4 7
n
Variations
May use circular lists instead of
chains.
Stacks
پشته نوعی لیست خطی میباشد.
اولین عنصری که داخل پشته قرار میگیرد bottomنامیده می شود
آخرین عنصری که داخل پشته قرار بگیرد topنامیده می شود
عملیات حذف و درج فقط از topامکان پذیر می باشد
Stack Of Cups
top
botto
m
top
F
E
E
D
D
C
C
B
B
A
botto
m
A
.عمل کردtop باید ازF برای درج وحذف
• Stack=LIFO=LAST IN FIRST OUT
The Interface Stack
public interface Stack
{
;)(public boolean empty
;)(public Object peek
;public void push(Object theObject)
;)(public Object pop
}
Parentheses Matching
)m-n(/))k-l(*)h+j(-)f+g(/)c+d-e*)a+b(((
Output pairs (u,v) such that the left parenthesis at position
.u is matched with the right parenthesis at v
)0,32( )27,31( )21,25( )15,19( )1,13( )2,6(
)34,38(
)c+d((*))a+b(
)0,4(
right parenthesis at 5 has no matching left parenthesis
)8,12(
left parenthesis at 7 has no matching right parenthesis
Parentheses Matching
عبارت را از چپ به راست بخوانید.
وقتی به Left parenthesisرسید آن رادر پشته pushکنید.
وقتی به right parenthesisرسید آن رااز پشته popکنید.
Example
)m-n(/))k-l(*)h+j(-)f+g(/)c+d-e*)a+b(((
2
1
0
Example
)m-n(/))k-l(*)h+j(-)f+g(/)c+d-e*)a+b(((
15
1
0
(2,6) (1,13
)
Example
)m-n(/))k-l(*)h+j(-)f+g(/)c+d-e*)a+b(((
21
1
0
(2,6) (1,13 (15,19)
)
Example
)m-n(/))k-l(*)h+j(-)f+g(/)c+d-e*)a+b(((
27
1
0
(2,6) (1,13 (15,19)(21,25)
)
Example
)m-n(/))k-l(*)h+j(-)f+g(/)c+d-e*)a+b(((
1
0
(2,6) (1,13 (15,19)(21,25)
(27,31)(0,32)
)
• and so on
Towers Of Hanoi/Brahma
4
3
2
1
A
B
C
64حلقه طال از ستون Aبه Cانتقال داده می شوند.
هر ستون در آن مانند یک پشته عمل می کند.
و هیچ حلقه بزرگی روی کوچکتر از خودش قرار نمی گیرد.
Towers Of Hanoi/Brahma
3
2
1
A
B
C
disk Towers Of Hanoi/Brahma-3
Towers Of Hanoi/Brahma
2
1
A
3
B
C
disk Towers Of Hanoi/Brahma-3
Towers Of Hanoi/Brahma
1
2
3
A
B
C
disk Towers Of Hanoi/Brahma-3
Towers Of Hanoi/Brahma
1
3
2
A
B
C
disk Towers Of Hanoi/Brahma-3
Towers Of Hanoi/Brahma
A
3
2
1
B
C
disk Towers Of Hanoi/Brahma-3
Towers Of Hanoi/Brahma
3
2
1
A
B
C
disk Towers Of Hanoi/Brahma-3
Towers Of Hanoi/Brahma
2
1
3
A
B
C
disk Towers Of Hanoi/Brahma-3
Towers Of Hanoi/Brahma
3
2
1
A
B
C
disk Towers Of Hanoi/Brahma-3
• 7 disk moves
Recursive Solution
1
C
B
با استفاده از مساله برج هانوی n > 0حلقه را میتوان از Aبه Cبا استفاده از Bمنتقل کرد.
با استفاده از Cتعداد n-1حلقه را از Aبه Bانتقال داده.
A
Recursive Solution
1
C
B
حلقه اول ستون Aرا از Aبه Cانتقال دهید.
A
Recursive Solution
1
A
B
C
. انتقال دهیدC بهB حلقه را ازn-1
Recursive Solution
1
A
B
C
moves(n) = 0 when n = 0
moves(n) = 2*moves(n-1) + 1 = 2n-1 when n > 0
Stacks
public interface Stack
{
;)(public boolean empty
;)(public Object peek
;public void push(Object theObject)
;)(public Object pop
}
Derive From A Linear List Class
ArrayLinearList
Chain
Derive From ArrayLinearList
a b c d e
0 1 2
3 4 5 6
عنصر باالی پشته معادل چپ ترین ویا راست ترین
.عنصر داخل آرایه می باشد
)(empty() => isEmpty
O(1) time
peek() => get(0) or get(size() - 1)
O(1) time
Derive From ArrayLinearList
a b c d e
0 1 2
3 4 5 6
در موقعیت چپ ترین عنصر آرایه قرارداردtop وقتی که
push(theObject) => add(0, theObject)
O(size) time
pop() => remove(0)
O(size) time
Derive From ArrayLinearList
a b c d e
0 1 2
3 4 5 6
در موقعیت راست ترین عنصر آرایه قرارداردtop وقتی که
push(theObject) => add(size(), theObject)
O(1) time
pop() => remove(size()-1)
O(1) time
use right end of list as top of stack
Derive From Chain
firstNode
nul
le
d
c
b
a
عنصر باالی پشته معادل چپ ترین ویا راست ترین
عنصر داخل آرایه می باشد.
)(empty() => isEmpty
O(1) time
Derive From Chain
firstNode
a
b
c
d
nul
le
در موقعیت چپ ترین عنصر آرایهtop –وقتی که
قراردارد
peek() => get(0)
O(1) time
push(theObject) => add(0, theObject)
O(1) time
pop() => remove(0)
Derive From Chain
firstNode
a
b
c
d
nul
le
در موقعیت راست ترین عنصر آرایه قرارداردtop –وقتی که
• peek() => get(size() - 1)
• O(size) time
• push(theObject) => add(size(),
theObject)
• O(size) time
• pop() => remove(size()-1)
• O(size) time
)(empty() And peek
a b c d e
0 1 2
3 4 5 6
)(public boolean empty
};)(return isEmpty{
)(public Object peek
{
if (empty())
;)(throw new EmptyStackException
return get(size() - 1)
}
)(push(theObject) And pop
a b c d e
0 1 2
3 4 5 6
public void push(Object theElement)
};add(size(), theElement){
)(public Object pop
{
if (empty())
;)(throw new EmptyStackException
;return remove(size() - 1)
}
)(A Faster pop
if (empty())
;)(throw new EmptyStackException
;return remove(size() - 1)
.vs
try {return remove(size() - 1);}
catch(IndexOutOfBoundsException e)
};)(throw new EmptyStackException{
)…(push
a b c d e
0 1 2
3 4
top
public void push(Object theElement)
{
increase array size if necessary //
if (top == stack.length - 1)
stack = ChangeArrayLength.changeLength1D
;)stack, 2 * stack.length(
put theElement at the top of the stack //
;stack[++top] = theElement
}
)(pop
a b c d e
0 1 2
3 4
top
)(public Object pop
{
if (empty())
;)(throw new EmptyStackException
;Object topElement = stack[top]
stack[top--] = null; // enable garbage collection
;return topElement
}
Linked Stack From Scratch
.See text
Performance
pop, push, and peek operations 500,000
initial capacity
Class
10
500,000
ArrayStack
0.44s
0.22s
DerivedArrayStack
0.60s
0.38s
DerivedArrayStackWithCatch
0.55s
0.33s
java.util.Stack
1.15s
DerivedLinkedStack
3.20s
3.20s
Queues
یک لیست خطی می باشد.
عنصر جلوی صف frontنامیده میشود.
عنصر انتهای لیست rearنامیده میشود.
افزودن عنصر به لیست فقط ازانتهای صف" " rearامکان پذیر است.
حذف کردن عناصراز لیست از جلوی صف" "frontامکان پذیر است.
Bus Stop Queue
Bus
Stop
front rear
rear
rea
r
rear
rear
Bus Stop Queue
Bus
Stop
front
rear
rear
rear
Bus Stop Queue
Bus
Stop
front
rear
rear
Bus Stop Queue
Bus
Stop
front
rear
rear
The Interface Queue
public interface Queue
{
;)(public boolean isEmpty
;)(public Object getFrontEelement
;)(public Object getRearEelement
;public void put(Object theObject)
;)(public Object remove
}
Derive From ArrayLinearList
a b c d e
0 1 2
3 4 5 6
. در راست لیست باشدrear چپ لیست وfrontزمانی که
)(Queue.isEmpty() => super.isEmpty
O(1) time
getFrontElement() => get(0)
O(1) time
getRearElement() => get(size() - 1)
O(1) time
put(theObject) => add(size(), theObject)
O(1) time
remove() => remove(0)
O(size) time
Derive From ArrayLinearList
e d c b a
0 1 2
3 4 5 6
. درچپ لیست باشدrear راست لیست وfrontزمانی که
)(Queue.isEmpty() => super.isEmpty
O(1) time
getFrontElement() => get(size() - 1)
O(1) time
getRearElement() => get(0)
O(1) time
put(theObject) => add(0, theObject)
O(size) time
remove() => remove(size() - 1)
O(1) time
Derive From ArrayLinearList
عملیات درج وحذف در صف با ( O)1صورت می گیرد.
Derive From ExtendedChain
lastNode
firstNode
a
b
c
d
front
nul
le
rear
راست لیست قرار داردrear چپ لیست وfront وقتی که
• Queue.isEmpty() => super.isEmpty()
– O(1) time
• getFrontElement() => get(0)
– O(1) time
Derive From ExtendedChain
lastNode
firstNode
a
b
c
d
nul
le
front
rear
• getRearElement() => getLast() … new method
– O(1) time
• put(theObject) => append(theObject)
– O(1) time
• remove() => remove(0)
– O(1) time
Derive From ExtendedChain
lastNode
firstNode
e
d
rear
c
b
nul
la
front
چپ لیست قرار داردrear راست لیست وfront وقتی که
)(Queue.isEmpty() => super.isEmpty
– O(1) time
• getFrontElement() => getLast()
–
Derive From ExtendedChain
lastNode
firstNode
a
b
c
d
rear
• getRearElement() => get(0)
– O(1) time
• put(theObject) => add(0, theObject)
– O(1) time
• remove() => remove(size-1)
– O(size) time
nul
le
front
Custom Array Queue
کاربرد یک آرایه یک بعدی بعنوان صف
[queue
]
• کاربرد یک آرایه یک بعدی بعنوان صف حلقوی
][3
][2
][1
][4
][5
][0
Custom Array Queue
• صف حلقوی با 3عنصر پر شده است.
][2
][3
B
A
]C [4
][5
][1
][0
Custom Array Queue
• حالت دیگری از قرار گیری 3عنصر در لیست حلقوی
][2
][3
[1] C
][4
][5
A
B
][0
Custom Array Queue
• کاربرد front and rearدر لیست حلقوی
– frontمکانی است که ب ابتدای لیست اشاره می کند.
– Rearمکانی است که به انتهای لیست اشاره می کند.
][2
][3
][3
B
rear
fron
t
][4
rear
[1] C
][5
A
B
][0
][2
A
fron
]t [1
]C [4
][5
][0
Add An Element
. درجهت عقربه های ساعت حرکت می کندrear •
[2]
[3]
A
fron
t [1]
B
rear
C [4]
[0]
[5]
Add An Element
• rearدرجهت عقربه های ساعت حرکت دهید.
• در مکانی که rearبه آن اشاره می کند
] queue[rearرا اضافه کنید.
][2
][3
B
A
fron
]t [1
]C [4
][5
D
rear
][0
Remove An Element
. را یک واحد جابه جا کنیدFront •
[2]
[3]
A
fron
t [1]
B
rear
C [4]
[0]
[5]
Remove An Element
• Frontرا یک واحددر جهت عقربه های ساعت جابه جا
کنید.
• و محتوای ] queue[frontرا از صف حذف کنید.
][3
B
rear
]fron [2
A
t
]C [4
][5
][1
][0
Moving rear Clockwise
• rear++;
if (rear = = queue.length) rear = 0;
[2]
[3]
A
fron
t
[1]
B
rear
C [4]
[0]
[5]
• rear = (rear + 1) % queue.length;
Empty That Queue
[2]
[3]
fron
[4]t
rear C
[1]
[0]
B
A
[5]
Empty That Queue
[2]
[3]
rear C
[1]
[0]
[4]
B
[5]
fron
t
Empty That Queue
[2]
[3]
rear C
[1]
[0]
fron
t
[4]
[5]
Empty That Queue
][3
][2
rear
][1
][4
][5
زمانی تمام عناصر داخل صف حذف شود آنگاهfront = rear :
اگر صف خالی باشد front = rear = 0
][0
fron
t
A Full Tank Please
[2]
[3]
fron
[4]t
rear C
[1]
[0]
B
A
[5]
A Full Tank Please
[2]
[3]
D
rear
fron
[4]t
[1] C
[0]
B
A
[5]
A Full Tank Please
[2]
[3]
D
E
B
A
rear
fron
[4]t
[1] C
[0]
[5]
A Full Tank Please
][2
][3
E
fron
[4]t
rear
D
[1] C
F
][5
A
B
][0
• اگر به پر کردن صف ادامه دهیم در نهایت می رسیم به
شرطfront = rear :
• اگر دقت کنید همان شرط خالی بودن صف می باشد
درصورتی که صف پر است!
!!!!!Ouch
شرط پر و خالی بودن در صف حلقوی
Queue is empty iff (front == rear) && !lastOperationIsPut
Queue is full iff (front == rear) && lastOperationIsPut
!!!!!Ouch
شرط پر و خالی بودن در صف معمولی
Queue is empty iff (size == 0)
Queue is full iff (size == queue.length)
Trees
Nature Lover’s View Of A Tree
برگ ها
شاخه
ریشه
Computer Scientist’s View
ریشه
برگ ها
شاخه
گره
Linear Lists And Trees
کاربردهای لیست های خطی :برای داده های ترتیبی است
()e0, e1, e2, …, en-1
روزهای هفته
ماه های سال
دانشجویان یک کالس
کاربرد درخت:برای داده هایی با سلسله مراتب یکسان
مانند کارمندان یک شرکت
Hierarchical Data And Trees
عنصری که در باالترین مرتبه قرار دارد rootیا ریشه نامیده
میشود.
Childrenعناصری که در مراتب بعد از ریشه قرار می
گیرند نامیده می شود.
leavesعناصری هستند که فاقد childrenهستند.
Classes (Part Of Figure 1.1)
Object
Number
Integer
root
children of
root
OutputStream
Throwable
Double
Exception
FileOutputStream
grand children of
root
RuntimeException
great grand child of
Definition
یک درخت از یک مجموعه عناصر متناهی تشکیل
شده است.
اولین عنصر ریشه نامیده می شود.
مابقی عناصرزیر درخت نامیده " subtrees of t
"می شود.
Subtrees
Object
Number
Integer
Double
root
Throwable
OutputStream
Exception
FileOutputStream
RuntimeException
Leaves
Object
Number
Integer
Double
Throwable
OutputStream
Exception
FileOutputStream
RuntimeException
Parent, Grandparent, Siblings, Ancestors, Descendants
Object
Number
Integer
Double
Throwable
OutputStream
Exception
FileOutputStream
RuntimeException
Levels
Object
Number
Integer
Double
Level
1
Level 2
Throwable
OutputStream
Exception
FileOutputStream
Level 3
RuntimeException
Level 4
Caution
به هرسطح یا Levelدر درخت یک شماره میدهیم:
ریشه در level 0قرار دارد.
زیر درخت های ریشه از سطح 1شروع می شوند.
البته levelریشه می تواند از سطح یک نیز باشد بنابراین
levelمربوط به زیر درخت های ریشه ا سطح 2شروع
میشود.
height = depth = number of levels
Object
Number
Integer
Double
Level
1
Level 2
Throwable
OutputStream
Exception
FileOutputStream
Level 3
RuntimeException
Level 4
Node Degree = Number Of Children
Object
2
1Throwable
Number
0
Integer
0
3
1OutputStream
1
Double
Exception
0
FileOutputStream
RuntimeException0
Tree Degree = Max Node Degree
Object
2
1Throwable
Number
0
Integer
0
1OutputStream
1
Double
Degree of tree
= 3.
3
Exception
0
FileOutputStream
RuntimeException0
Binary Tree
درخت دودویی از تعداد محدودی عنصر تشکیل شده است.
اولین عنصر آن ریشه می باشد.
درخت دودویی درختی است که درجه هر گره در آن یا صفر
باشد یادو.
تعریف:درجه گره:شامل تعداد زیر درخت های آن گره میباشد.
اگر درجه گره دو باشد دو زیر درخت آن زیر درخت های چپ
و راست نامیده می شوند.
Differences Between A Tree & A Binary Tree
هر گره در درخت باینری درجه بیشتر از دو ندارد.
یک درخت دودویی می تواند خالی باشد اما درخت
معمولی نمی تواند خالی باشد.
Differences Between A Tree & A Binary Tree
در درخت باینری زیر درخت ها دارای ترتیب می باشند.اما در
درخت معمولی برای زیر درخت ها ترتیبی قائل نیستیم.
a
b
a
b
• ترتیب زیر درخت ها:
• متفاوت هستنداگر به دیددرخت باینری به آنها نگاه کرد.
• یکسان هستند اگر به دیددرخت معمولی به آنها نگاه کرد
Arithmetic Expressions
e – f/g*h + 3.25 + )c + d( * )a + b(
:عبارت محاسباتی باال تسکیل شده از
//عملگرها.)* ,/ ,- ,+( Operators
Operands (a, b, c, d, e, f, g, h, 3.25, (a + b), (c +
//عملوند ها.d), etc.)
.)) ,(( Delimiters
Operator Degree
انواع عملگر ها:
عملگر های دودویی:نیازمند دو عملوند هستند.
a+b
c/d
e-f
عملگر های یکانی:نیازمند یک عملوند هستند.
g+
h-
Infix Form
روش معمولی برای نوشتن یک عبارت.
عملگر های دودوئی میان دو عملوند قرار می گیرند.
a*b
a+b*c
a*b/c
(e – f/g*h + 3.25 + )c + d( * )a + b
Operator Priorities
کدام عملگر زودتر اعمال می شود؟
برای عملگر هاترتیب یا اولویت قائل می شویم
a+b*c
a*b+c/d
)-(priority(*) = priority(/) > priority(+) = priority
عملگری زودتر اعمال می شود که باالترین اولویت را
داشته باشد.
Tie Breaker
اگر عملگرهایی که در عبارت قرار می گیرند دارای
اولویت یکسان باشند از چپ به راست عملگر ها را روی
عملوندها اعمال کنید.
a+b-c
a*b/c/d
Infix Expression Is Hard To Parse
سه روش برای نمایش یک عبارت محاسباتی داریم:
:Infix که درآن ابتدا عملوندچپ /بعدعملگردر وسط/
ونهایتاعملوند راست قرار می گیرد.
: prefixکه درآن ابتدا عملگریا ریشه /بعدعملوندچپ /
ونهایتاعملوند راست قرار می گیرد.
: postfixکه درآن ابتدا عملوندچپ عملگریا ریشه /
بعدعملوندراست /ونهایتا ریشه قرار می گیرد.
Postfix Form
:مثال
Infix = a + b
+Postfix = ab
Postfix
Examples
Infix = a + b * c
= Postfix
ab c * +
• Infix = a * b +
c
ab * c +
Postfix =
• Infix = (a + b) * (c – d) /
(e + f)
a b +c d - * e f + /
Postfix =
Unary Operators
.Replace with new symbols
@ a => a +
+ a + b => a @ b +
? a => a - a-b => a ? b -
Postfix Evaluation
عبارت محاسباتی را از چپ به راست بخوانید
به هر oprandیا عملوند رسیدیددر پشته pushکنید.
زمانی که به عملوند رسیدید از پشته popکنید وعملگر
را روی آن اعمال کنید.
این روش برای این است که در postfixعملگر بعد
از عملوند ها می آید.
Postfix Evaluation
)e + f( / )c – d( * )a + b(
/+ab+cd-*ef
/+ab+cd-*ef
•ab+cd-*ef+/
•ab+cd-*ef+/
b
a
stac
Postfix Evaluation
)e + f( / )c – d( * )a + b(
/+ab+cd-*ef
/+ab+cd-*ef
•a
•a
•a
•a
•a
b
b
b
b
b
+
+
+
+
+
c
c
c
c
c
d
d
d
d
d
-
*
*
*
*
*
e
e
e
e
e
f
f
f
f
f
+
+
+
+
+
/
/
/
/
/
d
c
(a +
b)
stac
Postfix Evaluation
)e + f( / )c – d( * )a + b(
/+ab+cd-*ef
•ab+cd-*ef+/
(c – d)
(a +
b)
stac
Postfix Evaluation
)e + f( / )c – d( * )a + b(
/+ab+cd-*ef
•a
•a
•a
•a
b
b
b
b
+
+
+
+
c
c
c
c
d
d
d
d
-
*
*
*
*
e
e
e
e
f
f
f
f
+
+
+
+
/
/
/
/
f
e
(a + b)*(c –
d)
stac
Postfix Evaluation
)e + f( / )c – d( * )a + b(
/+ab+cd-*ef
•a
•a
•a
•a
•a
b
b
b
b
b
+
+
+
+
+
c
c
c
c
c
d
d
d
d
d
-
*
*
*
*
*
e
e
e
e
e
f
f
f
f
f
+
+
+
+
+
/
/
/
/
/
(e + f)
(a + b)*(c –
d)
stac
Prefix Form
در prefixابتدا عملگر و سپس عملوند چپ ونهایتا
عموند راست می آید.
Infix = a + b
+Postfix = ab
Prefix = +ab
Binary Tree Form
a+b
•-a
+
a
b
a
Binary Tree Form
)e + f ( / )c – d ( * )a + b (
//
*
+
+
a
e
b
c
d
f
Merits Of Binary Tree Form
کار با الگوریتم درخت باینری بهینه تر از عبارت
محاسباتی است.
Binary Tree
/
+
f
*
e
+
d
c
b
a
Binary Tree Properties & Representation
Minimum
Nodes
Numberاندازه ارتفاع آن
Ofدرخت باینری به
های یک
حداقل تعداد گره
میباشد.
آخرین گره در درخت باینری معرف ارتفاع می باشد.
حداقل تعداد گره ها در
درخت دودویی hمیباشد.
Maximum Number Of Nodes
برای درخت کامل:درختی که تمام گره های سطح آخرش وجود داشته باشد .برای محاسبه حداکثر
تعداد گره هااز روش زیر:
Maximum number of
nodes
=1+2+4+8+…+
h-1
Number Of Nodes & Height
اگر nتعداد گره های یک درخت باینری باشد محدوده
آن :
h <= n <= 2h – 1
log2(n+1) <= h <= n
Full Binary Tree
تعدادگره ها در یک درخت دودویی به ارتفاع :h
2h – 1میباشد.
ارتفاع در درخت کامل باال 4میباشد.
Numbering Nodes In A Full Binary
Tree
تعداد نودهادر درخت باینری از 1تا 2h – 1متغیر است.
شمارش سطوح از باال به پایین می باشد.
در هر سطح شمارش گره ها از چپ به راست می باشد.
1
3
7
2
6
12 13 14 15
4
5
11
10
9
8
Node Number Properties
1
3
7
2
6
12 13 14 15
4
5
11
10
9
والد هر گره مثل iدرگره i / 2آن میباشد ,البته به
استثنای .i = 1زیرا:
i = 1ریشه میباشد وریشه والد ندارد .
8
Node Number Properties
1
3
7
2
6
12 13 14 15
4
5
11
10
9
گره چپ iدر 2iمیباشد.
n تعدادگره های یک درخت باشد .اگر 2i > nباشد آنگاه i
دارای فرزند چپ نمی باشد.
8
Node Number Properties
1
3
7
2
6
12 13 14 15
4
5
11
10
9
گره راست iدر 2i+1میباشد.
n تعدادگره های یک درخت باشد .اگر 2i+1 > nباشد آنگاه i
دارای فرزند راست نمی باشد.
8
Complete Binary Tree With n Nodes
در یک درخت باینری تعداد گره ها میان 1تا n
می باشد.
اگر درخت شامل هر nتا باشد آنگاه به آن
درخت ,درخت کامل گویند و سطر آخر کامال پر نشده
باشد و گره ها ازچپ به راست قرار گرفته باشد.
Example
1
3
7
2
6
12 13 14 15
4
5
11
10
9
8
مثال:درخت کامل را با 10گره در نظر بگیرید.
Binary Tree Representation
برای نمایش درخت دودویی می توان از آرایه استفاده
کرد.
نمایش با استفاده از لیست های پیوندی
Array Representation
ابتداگره های یک درخت را به صورت سطحی Level Orderاز
چپ به راست شماره گذاری کرده سپس درخت را سطحی پیمایش
کرده به این صورت که گره iدر ] tree[iقرار می گیرد.
a1
3
c
7
g
2
b
f
6
5
e
d
10
j
9
i
4
h
a b c d e f g h i j
[tree
0
5
10
]
8
Right-Skewed Binary
Tree
1
a
7
c
15
b 3
d
a - b - - - c - - - - - - - d
[tree
0
5
10
15
]
برای نمایش یک درخت دودویی با استفاه ازیک آرایه با سایز n+1تا 2nنیاز
داریم.
Linked Representation
تمام گره های درخت باینری در نمایش پیوندی به صورت یک نود نمایش داده می شود که دارای دو اشاره گر یکی به راست ویکی به چپ دارد.
کل فضایی که نیاز داریم برای nگره درخت باینری
جهت نمایش لیست پیوندی:
).n * (space required by one node
The Class BinaryTreeNode
;package dataStructures
public class BinaryTreeNode
{
;Object element
زیر درخت چپ// ;BinaryTreeNode leftChild
زیر درخت راست//;BinaryTreeNode rightChild
}
Linked Representation Example
roo
t
a
b
c
e
d
f
g
leftChild
element
rightChild
h
Binary Tree Traversal Methods
Preorder
Inorder
Postorder
Level order
Binary Tree Traversal Methods
در پیمایش درخت باینری هر گره فقط یک مرتبه
visitمیشود.
Binary Tree Traversal Methods
Preorder
Inorder
Postorder
Level order
Preorder Traversal
public static void preOrder(BinaryTreeNode t)
{
if (t != null)
{
;visit(t)
;preOrder(t.leftChild)
;preOrder(t.rightChild)
}
}
Preorder Example (visit = print)
a
b
c
a bc
Preorder Example (visit = print)
a
b
f
e
d
g
c
h
a bdghe i c f j
i
j
Preorder Of Expression
Tree
/
*
+
+
a
e
b
c
f
d
/ * +a b - c d +e f
! در عبارت محاسباتیprefix معادل
Inorder Traversal
public static void inOrder(BinaryTreeNode t)
{
if (t != null)
{
;inOrder(t.leftChild)
;visit(t)
;inOrder(t.rightChild)
}
}
Inorder Example (visit = print)
a
b
c
ba c
Inorder Example (visit = print)
a
b
f
e
d
g
c
h
gdhbe i a f j c
i
j
Inorder By Projection (Squishing)
a
b
f
e
d
g
c
h
g d h
i
b e i a
j
f jc
Inorder Of Expression Tree
/
*
+
+
a
e
b
c
f
d
a + b * c - d/
e + f
Postorder Traversal
public static void postOrder(BinaryTreeNode t)
{
if (t != null)
{
;postOrder(t.leftChild)
;postOrder(t.rightChild)
;visit(t)
}
}
Postorder Example (visit = print)
a
b
c
bc a
Postorder Example (visit = print)
a
b
f
e
d
g
c
h
ghdi e bj f c a
i
j
Postorder Of Expression
Tree
/
*
+
+
a
e
b
c
f
d
a b +c d - * e f + /
! در عبارت محاسباتیpostfix معادل
Traversal Applications
a
b
f
e
d
g
c
h
i
j
Level Order
.Let t be the tree root
while (t != null)
{
;visit t and put its children on a FIFO queue
remove a node from the FIFO queue and
;call it t
}
Level-Order Example (visit = print)
a
b
f
e
d
g
c
h
a bc de f ghi j
i
j
Some Examples
preorder
= ab
inorde
r=
ab
postord
er =
ab
level
order =
ab
a
a
b
b
b
a
a
b
b
b
a
a
a
b
a
b
Preorder And Postorder
preorder = ab
postorder =
ba
a
b
a
b
Inorder And Preorder
inorder = g d h b e i a f j c
preorder = a b d g h e i c f j
a
gdhb
ei
fjc
Inorder And Preorder
a
gdhb
ei
fjc
preorder = a b d g h e i c f j
ei / زیر درخت چپgdh / ریشه بعدی استb
زیر درخت راست
a
b
gd
h
fjc
ei
Inorder And Preorder
a
b
gd
h
fjc
ei
preorder = a b d g h e i c f j
زیر درختg/. ریشه بعدی می باشدd
.زیر درخت راست می باشدhو/چپ
a
b
d
g
fjc
ei
h
Inorder And Postorder
پیمایش از چپ به راست می باشدlevel order در
.پیمایش از راست به چپ می باشدPost order در
inorder = g d h b e i a f j c
postorder = g h d i e b j f c a
;Tree root is a
زیر درخت چپ// gdhbei
زیردرخت راست// fjc
Inorder And Level Order
.پیمایش از چپ به راست می باشدlevel order در
inorder = g d h b e i a f j c
level order = a b c d e f g h i j
;Tree root is a
زیر درخت چپ// gdhbei
زیردرخت راست// fjc
Priority Queues
دونوع صف اولویت دار تعریف می کنیم:
صف با الویت باال
صف با الویت پایین
Min Priority Queue
یک مجموعه از عناصر میباشد.
برای هر عنصر یک کلید اولویت تعریف می کنیم.
اعمال زیر را می توان روی آن انجام داد.
چک کردن اینکه صف خالی است یا نه؟
سایز و اندازه صف
اضافه کردن یک عنصر به لیست
پیدا کردن عنصر با کمترین اولویت
حذف عنصری با کمترین اولویت
Max Priority Queue
یک مجموعه از عناصر میباشد.
برای هر عنصر یک کلید اولویت تعریف می کنیم.
اعمال زیر را می توان روی آن انجام داد.
چک کردن اینکه صف خالی است یا نه؟
سایز و اندازه صف
اضافه کردن یک عنصر به لیست
پیدا کردن عنصر با بیشترین اولویت
حذف عنصری با بیشترین اولویت
Complexity Of Operations
وheaps leftist دو نمونه خوب می توان از
. نام بردleftist trees
isEmpty, size, and get => O(1) time
put and remove => O(log n) time
طول لیست می باشدn که در آن
Applications
Sorting
کلید هر عنصر به عنوان اولویت آن محسوب می شود.
عناصر را مرتب شده در لیست اولویت قرار دهید
گزینش عنصر با توجه به کلید اولویت آن:
اگر عنصری با کمترین اولویت را خواستیم انتخاب کنیم باید
صف به صورت صعودی مرتب شده باشد.
اگر عنصری با بیشترین اولویت را خواستیم انتخاب کنیم باید
صف به صورت نزولی مرتب شده باشد.
Sorting Example
مرتب کنیدپنج عنصری که کلید های آن به این قرار باشد:
1 ,4 ,2 ,8 ,6
از صف با الویت باال استفاده کنید.
ابتدا عناصر را در یک صف ب الویت باال قرار دهید
پنج مرتبه عمل حذف را انجام دهید در نهایت عناصر از راست
به چپ مرتب می شوند.
After Putting Into Max Priority Queue
8
4
1
2
6
صف با الویت
باال
Sorted Array
After First Remove Max Operation
4
1
6
صف با الویت
باال
2
8
Sorted Array
After Second Remove Max Operation
4
1
صف با الویت
باال
2
6
8
Sorted Array
After Third Remove Max Operation
1
صف با الویت
باال
2
4
6
8
Sorted Array
After Fourth Remove Max Operation
صف با الویت باال
1
2
4
6
8
Sorted Array
After Fifth Remove Max Operation
صف با الویت باال
1
2
4
6
8
Sorted Array
Complexity Of Sorting
عنصرn مرتب سازی
.n put operations => O(n log n) time
.n remove max operations => O(n log n) time
.total time is O(n log n)
compare with O(n2)
Heap Sort
کاربرد صف با الویت باال در heapدیده می شود.
این مرتب سازی با ) O(nقابل انجام است.
Min Tree Definition
هر درختی دارای valueیا یک مقدار می باشد
:Min treeدرختی است که در آن valueریشه از value
تمام زیر درختها با فرزندانش کمتر باشد.
Min Tree Example
2
3
9
7
9
4
8
9
ریشه کمترین مقدار را دارد
4
Max Tree Example
9
8
9
7
1
4
2
3
ریشه بیشترین مقدار را دارد
4
Min Heap Definition
درخت باینری کامل
min tree
Min Heap With 9 Nodes
گره9 درخت کامل با
Min Heap With 9 Nodes
2
4
6
8
3
7
9
3
6
min گره وهمچنین9 درخت کامل با
tree
Max Heap With 9 Nodes
9
8
6
5
7
7
2
6
1
max گره وهمچنین9 درخت کامل با
tree
Heap Height
Heapدرختی کامل می باشد که ارتفاع ان
).log2 (n+1است
A Heap Is Efficiently Represented As An Array
9
8
7
6
5
7
2
1
0
9
8
7
6
7
2
6
5
1
1
2
3
4
5
6
7
8
9 10
6
Moving Up And Down A Heap
1
9
2
3
8
7
4
5
6
7
5
1
8
9
7
6
2
6
Putting An Element Into A Max Heap
9
8
7
6
5
7
1
2
6
7
گره10 درخت کامل با
Putting An Element Into A Max Heap
9
8
7
6
5
7
1
2
6
5
7
گره جدید می باشد5
Putting An Element Into A Max Heap
9
8
7
6
5
7
1
2
6
7
گره جدید می باشد20
Putting An Element Into A Max Heap
9
8
7
6
5
2
1
6
7
7
گره جدید می باشد20
Putting An Element Into A Max Heap
9
7
6
5
8
1
2
6
7
7
گره جدید می باشد20
Putting An Element Into A Max Heap
20
9
7
6
5
8
1
2
6
7
7
گره جدید می باشد20
Putting An Element Into A Max Heap
20
9
7
6
5
8
1
2
6
7
7
گره11 درخت کامل با
Putting An Element Into A Max Heap
20
9
7
6
5
8
1
2
6
7
7
گره جدید می باشد15
Putting An Element Into A Max Heap
20
9
7
6
5
2
1
7
7
6
8
گره جدید می باشد15
Putting An Element Into A Max Heap
20
7
15
6
5
9
1
7
7
2
6
8
گره جدید می باشد15
Complexity Of Put
20
7
6
15
2
9
8
پیچیدگی آن ) O(log nزمانیکه سایز
heapمقدار nباشد
6
7
7
1
5
Removing The Max Element
20
7
6
15
2
9
8
بزرگترین مقدلر در ریشه قرار دارد.
6
7
7
1
5
Removing The Max Element
7
6
15
2
9
8
پس از آنکه بزرگترین مقدار حذف شد
6
7
7
1
5
Removing The Max Element
7
6
15
2
9
8
6
7
7
در heapتعداد 10عنصر قرار می گیرد.
8را به heapاضافه کنید.
1
5
Removing The Max Element
7
15
6
5
9
1
7
7
2
6
Removing The Max Element
15
7
6
5
9
1
7
7
2
6
Removing The Max Element
15
9
7
6
5
8
1
7
7
2
6
Removing The Max Element
15
7
6
9
2
6
8
7
7
15بزرگترین عنصر قرار می گیرد.
1
5
Removing The Max Element
7
6
9
2
6
8
7
7
پس از آنکه بزرگترین مقدار حذف شد
1
5
Removing The Max Element
7
6
9
2
6
8
7
7
اکنون در heapتعداد 9عنصر قرار می
گیرد.
1
5
Removing The Max Element
9
6
5
7
8
1
2
6
Removing The Max Element
9
7
6
5
8
1
2
6
Removing The Max Element
9
8
6
5
7
7
1
2
6
Complexity Of Remove Max Element
9
8
6
5
7
7
1
O(log n) = پیچیدگی
2
6
Initializing A Max Heap
1
3
2
4
8
5
9
7
10
6
7
11
8
input array = [-, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11]
Initializing A Max Heap
1
3
7
2
6
5
11
8
4
7
10
9
8
ابتدا موقعیت n/2را در آرایه فوق محاسبه کرده و سپس از آن
گره در درخت شروع کنید
Initializing A Max Heap
1
3
7
2
6
11
8
5
4
7
10
9
Max heapبودن را در درخت چک کنید.در درخت max
heapمحتوای ریشه از کلیه عناصر آن بزرگتر می باشد.
8
Initializing A Max Heap
1
3
2
4
8
11
9
7
10
6
8
5
7
Initializing A Max Heap
1
3
2
9
8
11
4
7
10
6
8
5
7
Initializing A Max Heap
1
3
2
9
8
11
4
7
10
6
8
5
7
Initializing A Max Heap
1
7
2
9
8
11
4
7
10
6
8
5
3
Initializing A Max Heap
1
7
2
9
8
11
4
7
10
6
8
5
3
Initializing A Max Heap
1
7
11
9
8
6
4
7
10
8
5
. عوض می شود2 با11 مکان
3
Initializing A Max Heap
1
7
11
9
8
10
4
8
6
7
5
. عوض می شود2 با10 مکان
3
Initializing A Max Heap
1
7
11
9
8
10
4
7
2
6
8
5
3
Initializing A Max Heap
1
7
11
9
8
10
4
2
7
6
3
8
5
را بیابید؟1 مکان
Initializing A Max Heap
11
7
9
8
10
4
2
7
6
8
5
1 یافتن مکان
3
Initializing A Max Heap
11
10
7
9
8
6
4
2
7
3
8
5
1 یافتن مکان
Initializing A Max Heap
11
10
7
9
8
5
4
2
7
6
3
8
1 یافتن مکان
Initializing A Max Heap
11
10
7
9
8
5
4
2
7
6
3
8
1
.انجام شد
Time Complexity
11
7
3
9
6
5
8
2
8
7
10
ارتفاع درخت heap = h
تعداد زیر درخت ها با ریشه در
j-1
=level j 2
پیچیدگی زمانی برای هر زیر درخت = )O(h-j+1
4
1
Complexity
پیچیدگی زمانی برای زیر درخت سطح
j
=< )2j-1(h-j+1) = t(j
زمان کل= )t(1) + t(2) + … + t(h-1) = O(n
Extended Binary Trees
یک درخت باینری را در نظر بگیریدو اضافه
کنید یک نود خارجی هر جایی زیر درخت
نداشته باشد.
به همین دلیل به آن درخت باینری گسترش یافته
می گویند.
A Binary Tree
An Extended Binary Tree
= تعداد گره های خارجیn+1
)(The Function s
برای هر گره xدر درخت باینری گسترش یافته با
استفاده از تابع ) s(xقادریم:
طول کوتاهترین مسیر از xبه گره خارجی در زیر
درخت های ریشه محاسبه کرد.
s() Values Example
Binary Search Trees
:Dictionary Operations
get(key)
put(key, value)
remove(key)
:Additional operations
)(ascend
). (اندیس گره در درخت باینری را برمی گرداندget(index)
) (کند محتوای اندیس در درخت باینری را حذف میremove(index)
Complexity Of Dictionary Operations
)(get(), put() and remove
Data Structure Worst Case
Expected
Hash Table
O(1)
O(n)
Binary Search O(n)
Tree
Balanced
O(log n)
Binary Search
Tree
O(log n)
O(log n)
Complexity Of Other Operations
ascend(), get(index), remove(index)
Data Structure ascend
Hash Table
get and
remove
O(D +n log n) O(D +n log n)
Indexed BST O(n)
O(n)
Indexed
O(n)
Balanced BST
O(log n)
D is number of buckets
Definition Of Binary Search Tree
در یک درخت باینری
هر گره دارای ( )key, valueمیباشد.
برای هر گره دلخواه xکلیه عناصر زیر درخت
چپ آن کوچکتر از آن وکلیه عناصر زیر درخت
راست آن بزرگتر از آن می باشد.
Example Binary Search Tree
20
10
6
2
40
15
8
30
25
.فقط کلید ها را نشان داده است
)(The Operation ascend
20
10
40
30
15
25
پیمایش میانوندی آن با ) O(nامکا ن پذیر است.
6
8
2
)(The Operation get
20
10
6
2
40
15
8
30
25
= پیچیدگیO(height) = O(n(
)(The Operation put
20
10
6
2
40
15
8
Put 35.
30
25
35
)(The Operation put
20
10
6
2
15
8
7
Put 7.
40
30
25
35
)(The Operation put
20
10
6
2
40
15
8
7
Put 18.
30
18
25
35
)(The Operation put
20
10
6
2
40
15
8
30
18
25
7
=< پیچیدگیput() =O(height).
35
)(The Operation remove
گره در وضعیت های:
اگر گره برگ باشد
اگر گره از درجه یک باشد.
اگر گره از درجه دو باشد
Remove From A Leaf
20
10
6
2
40
15
8
30
18
25
35
7
7 = گره برگ
حذف
Remove From A Leaf (contd.)
20
10
6
2
40
15
8
30
18
25
35
7
35 = حذف گره برگ
Remove From A Degree 1 Node
20
10
6
2
40
15
8
30
18
7
40 = حذف گره تک فرزندی
25
35
Remove From A Degree 1 Node (contd.)
20
10
6
2
40
15
8
7
15 = حذف گره تک فرزندی
30
18
25
35
Remove From A Degree 2 Node
20
10
6
2
40
15
8
30
18
7
10 = حذف گره دو فرزندی
25
35
Remove From A Degree 2 Node
20
10
40
30
35
15
25
18
6
2
8
7
جابه جا کنید با بزرگترین در زیر درخت چپ ویا با
کوچکترین در زیر درخت راست.
Remove From A Degree 2 Node
20
10
40
30
35
15
25
18
6
2
8
7
جابه جا کنید با بزرگترین در زیر درخت چپ ویا با
کوچکترین در زیر درخت راست.
Remove From A Degree 2 Node
20
8
40
30
35
15
25
18
6
2
8
7
جابه جا کنید با بزرگترین در زیر درخت چپ ویا با
کوچکترین در زیر درخت راست.
Remove From A Degree 2 Node
20
8
40
30
35
15
25
18
6
2
8
7
بزرگترین کلید یا باید برگ باشد یا گره تک فرزندی
Another Remove From A Degree 2 Node
20
10
6
2
40
15
8
30
18
25
35
7
= 20 حذف گره دو فرزندی
Remove From A Degree 2 Node
20
10
40
30
35
15
25
18
6
2
8
7
جابه جا کنید با بزرگترین در زیر درخت چپ
Remove From A Degree 2 Node
20
10
40
30
35
15
25
18
6
2
8
7
جابه جا کنید با بزرگترین در زیر درخت چپ
Remove From A Degree 2 Node
18
10
40
30
35
15
25
18
6
2
8
7
جابه جا کنید با بزرگترین در زیر درخت چپ
Remove From A Degree 2 Node
18
10
6
2
40
15
8
7
= پیچیدگیO(height).
30
25
35
Indexed Binary Search Tree
جستجوی باینری
در هر نود یک فیلد اضافی وجود دارد:
=leftSize شمارش تعداد نود های چپ درخت
Example Indexed Binary Search Tree
7
20
4
3
10
1
0
6
1 30
15
0
2
40
8
1
0
7
leftSize =red
0
18
0
25
0
35
leftSize And Rank
inorder =موقعیت عناصر درRank
(inorder = )مرتب کلید ها به صورت صعودی.
[2,6,7,8,10,15,18,20,25,30,35,40]
rank(2) = 0
rank(15) = 5
rank(20) = 7
leftSize(x) = rank(x)
leftSize And Rank
7
20
4
3
10
1
0
6
1 30
15
0
2
40
8
1
0
18
0
25
0
35
0
7
sorted list =
[2,6,7,8,10,15,18,20,25,30,35,40]
get(index) And remove(index)
7
20
4
3
10
1
0
6
1 30
15
0
2
40
8
1
0
18
0
25
0
35
0
7
sorted list =
[2,6,7,8,10,15,18,20,25,30,35,40]
get(index) And remove(index)
if index = x.leftSize
. را انتخاب کنx.element
if index < x.leftSize
آن در زیر درخت چپindex عنصری انتخاب می شود که محتوای
.می باشدx
if index > x.leftSize
) آن درindex - x.leftSize-1( عنصری انتخاب می شودکه محتوای
.می باشدx زیر درخت راست
Linear List As Indexed Binary Tree
7
h
4
3
e
1
b
f
0
a
l
d
1
0
1
0
g
j
0
i
k
0
0
c
list = [a,b,c,d,e,f,g,h,i,j,k,l]
add(5,’m’)
7
h
4
3
e
1
b
f
0
a
l
d
1
0
1
0
g
j
0
i
k
0
0
c
list = [a,b,c,d,e,f,g,h,i,j,k,l]
add(5,’m’)
7
h
4
3
e
1
b
f
0
a
l
d
1
0
1
0
g
j
0
i
k
0
0
c
list = [a,b,c,d,e, m,f,g,h,i,j,k,l]
find node with element 4 (e)
add(5,’m’)
7
h
4
3
e
1
b
f
0
a
l
d
1
0
1
0
g
j
0
i
k
0
0
c
list = [a,b,c,d,e, m,f,g,h,i,j,k,l]
find node with element 4 (e)
)’add(5,’m
h
7
4
3
e
l
j
0
0
1
0
k
i
1
m
f
0
g
b
1
0
a
d
0
c
mرا به راست گره eاضافه کرده است
در نتیجه زیر درخت راست eبه عنوان زیر درخت راست
mقرار می گیرد.
)’add(5,’m
h
7
4
3
e
l
j
0
0
1
0
k
i
1
b
f
0
g
m
1
0
a
d
0
c
mرا بعنوان فرزند چپ در زیر درخت راست
گره eقرار دهید.
add(5,’m’)
O(height) = پیچیدگی