ต้นไม้แดงดำ (อังกฤษ: Red-Black Tree) เป็นต้นไม้ค้นหาแบบทวิภาคที่ประยุกต์แนวคิดมาจากต้นไม้ได้ดุล 2-3-4 ให้เป็นต้นไม้ค้นหาแบบทวิภาค โดยที่ปมของต้นไม้แดงดำจะมีการเก็บตัวแปรหนึ่ง มักเรียกว่าสีแดงและสีดำ มีสองสีซึ่งสามารถเก็บด้วยค่าความจริงหรือตัวแปรขนาดหนึ่งบิตได้ และทำให้ต้นไม้นี้ถูกเรียกชื่อว่า ต้นไม้แดงดำ
| ต้นไม้แดงดำ (Red-Black Tree) |
|---|
ตัวอย่างต้นไม้แดงดำ |
| ความสำคัญของลำดับ | เรียงจากน้อยไปมาก |
|---|
| การซ้ำกันของสมาชิก | ไม่อนุญาตให้ซ้ำ |
|---|
| เวลาที่ใช้ค้นหาตามค่า | O (log n) |
|---|
| เวลาที่ใช้ในการเข้าถึง | O (log n) |
|---|
| การทำให้ว่าง | ทำรากให้เป็น null |
|---|
| เวลาที่ใช้ทำให้ว่าง | O (1) |
|---|
| โครงสร้างต้นแบบ | ต้นไม้ค้นหาแบบทวิภาค, ต้นไม้ได้ดุล 2-3-4 |
|---|
| โครงสร้างที่นำไปใช้ | ต้นไม้แบบบี |
|---|
| ความซับซ้อนในการคำนวณแบบสัญกรณ์โอใหญ่ |
|---|
| ขั้นตอนวิธี | | ถัวเฉลี่ย | เลวร้ายที่สุด |
|---|
|
ต้นไม้แดงดำ เป็นต้นไม้ค้นหาทวิภาคซึ่งแต่ละ Node ของต้นไม้จะมีสีกำกับคือเป็นสีแดงหรือไม่ก็ดำ เป็นต้นไม้ที่นำแนวคิดมาจากต้นไม้ได้ดุล 2-3-4 มาประยุกต์โดยใช้ Node แบบสองทั้งหมด โดยสำหรับ Node แบบสามจะถูกแทนด้วย Node แบบสองสองและเรียงกันโดย Node ใด Node หนึ่งเป็นสีแดง ส่วน Node แบบสี่จะถูกแทนด้วย Node แบบสองสาม โดยลูกทั้งคู่เป็นสีแดง มีข้อกำหนดต่างๆตามต้นไม้ค้นหาทวิภาค และมีข้อบังคับเพิ่มเติมคือ
1.Node เป็นสีแดงหรือสีดำ
2.ราก(Root)เป็นสีดำ
3.ใบ(leaves)ทุกใบเป็นสีดำ
4.ลูกของ Node ที่เป็นสีแดงต้องเป็นสีดำ
5.ทุกๆทางเดินอย่างง่าย(simple path; ทางเดินที่ผ่านแต่ละ Node เพียงครั้งเดียว)จากรากไปยังใบจะผ่านจำนวน Node สีดำเท่ากัน
จุดเด่นของต้นไม้แดงดำ ต้นไม้แดงดำดัดแปลงมาจากต้นไม้ได้ดุล 2-3-4 ซึ่งถูกกันความสูงระหว่าง log2n ถึง log4n ระยะทางจากรากไปยังใบที่อยู่ใกล้ที่สุด กับระยะทางจากรากไปยังใบที่อยู่ไกลที่สุดห่างกันไม่เกิน สองเท่า (พิสูจน์โดย Contradiction ให้ระยะทางห่างกันเกินสองเท่า แต่จำนวน Node สีดำจะต้องเท่ากันตามคุณสมบัติของต้นไม้แดงดำดังนั้นจำนวน Node สีแดงของเส้นทางที่ไกลย่อมต้องมากกว่า black-height(จำนวน Node สีดำจากรากไปยังใบ) และมากกว่าจำนวน Node สีแดงของเส้นทางที่ใกล้ แต่ว่าลูกของNodeสีแดงจะต้องเป็นสีดำเสมอทำให้เกิดข้อขัดแย้ง)จึงสามารถบอกได้ว่าต้นไม้แดงดำนี้ค่อนข้างได้ดุลย์ และเนื่องจากประสิทธิภาพเชิงเวลาของการกระทำต่างๆในต้นไม้ค้นหาทวิภาคนั้นขึ้นอยู่กับความสูงทำให้การทำงานมีประสิทธิภาพที่ดีแม้จะอยู่ในกรณีย่ำแย่(ช้ากว่าไม่เกินสองเท่าของกรณีที่ดี) ซึ่งต่างจาก Binary search tree ทั่วไป
บริการที่มักจะมี - การเพิ่ม การลบ และการค้นหา
ความเร็วที่ใช้ในการทำงาน เนื่องจากต้นไม้แดงดำ มีความสูงจำกัดแน่นอนเป็น log2n ถึง log4n จึงประกันเวลาการทำงานอยู่ใน O (log n)
ประเภทข้อมูลที่ใช้สร้างต้นไม้แดงดำ Node ของต้นไม้แดงดำนั้นมีข้อมูลเพิ่มมาจาก Node ของ binary search tree แบบปกติคือจะมีการเพิ่มตัวแปรที่เก็บ สี แดงดำ อาจเป็น ตัวเลข หรือค่าความจริง ซึ่งใช้หน่วยจำเพิ่มขึ้นเพียงแค่หนึ่งบิตต่อหนึ่งปม การแสดงสีอาจแสดงด้วย edge แทนที่จะเป็นสีของ nodeซึ่งไม่ได้ทำให้เกิดข้อแตกต่างแต่อย่างใด
การสร้างบริการของต้นไม้แดงดำ การเพิ่มสมาชิก
การเพิ่มสมาชิกของต้นไม้แดงดำจะเลียนแบบการทำงานของต้นไม้ได้ดุล 2-3-4 ซึ่งมีการเปลี่ยนสมาชิกของ Node ให้สูงขึ้นไป หรือการแตก Node เหล่านี้สามารถแทนด้วยต้นไม้แดงดำด้วยวิธีการจัดการตามสมบัติของต้นไม้แดงดำที่ว่า ลูกของ Node ที่เป็นสีแดงต้องเป็นสีดำ และจัดการดังต่อไปนี้ได้
- เพิ่มสมาชิกโดยใช้วิธีการเดียวกับ binary search tree ทั่วไป เพียงแต่ Node ที่เพิ่มใหม่นี้ให้เป็น Node สีแดง
- สำรวจว่า Node พ่อของ Node ใหม่ที่เพิ่มขึ้นเป็นสีแดงหรือไม่ ถ้าใช่จะขัดกับสมบัติกล่าวมาข้างต้น ก็จะทำได้สองวิธีดังนี้
- การสลับสีสาม Node ในกรณีที่มีการต่อในลักษณะคล้ายกับต่อ Node แบบสี่ การสลับสีสาม Node จะเสมือนการแตก Node ในต้นไม้ได้ดุล2-3-4
- การหมุน Node และสลับสีสาม Node ในบางกรณีการสลับสีสาม Node เฉย ๆ ไม่อาจช่วยให้ถูกต้องกับสมบัติที่กล่าวมาข้างต้นได้ ดังนั้นการหมุน Node เท่านั้นจึงช่วยให้สมบัติถูกต้องแบบนี้จะสอดคล้องกับการเพิ่มข้อมูลใน Node ในต้นไม้ได้ดุล2-3-4
การลบสมาชิก
สำหรับการ delete ก็จะเป็นลักษณะเดียวกับการทำ insert คือ operation ของการทำ delete ทั่วๆไปจะมีลักษณะเหมือนกับ delete ของ Binary Search Tree เริ่มจากพิจารณาว่า Node ที่จะทำการ delete นั้นไม่มีลูกเป็น Node ภายใน , มีลูก 1 Node เป็น Node ภายใน, ลูกทั้ง 2 Node เป็น Node ภายใน โดยถ้าเป็นกรณีที่ Node ที่จะทำการ delete ไม่มีลูกเป็น Node ภายในก็จะลบ Node นั้นทิ้งแล้วแทนด้วย sentinelเลย แต่ถ้ามี 1 Node ภายใน ก็จะแทน Node ที่ต้องการลบด้วยลูกของ Node นั้นเลย และในกรณีสุดท้ายจะหา successor (ตัวที่มีค่าน้อยที่สุดที่มีค่ามากกว่า Node นั้น) มาแล้วทำการลบ successor แทน แล้วย้ายค่าของ successor มาไว้ใน Node นั้น จากนั้นก็ต้องพิจารณาว่าการลบนั้นทำให้เกิดข้อขัดแย้งในคุณสมบัติ 5 ข้อหรือไม่ โดยจะเกิดข้อขัดแย้งขึ้นเมื่อ Node ที่เราทำการลบไป เป็นสีดำก็จะต้องทำการ fixup เพื่อขจัดข้อขัดแย้งไป
การค้นหาสมาชิก
การค้นหาสมาชิกนั้นสะดวกมากกว่าต้นไม้ได้ดุล2-3-4 เพราะใช้วิธีค้นหาแบบเดียวกับ Binary search tree ได้
ดูเพิ่ม นไม, แดงดำ, บทความน, ไม, การอ, างอ, งจากแหล, งท, มาใดกร, ณาช, วยปร, บปร, งบทความน, โดยเพ, มการอ, างอ, งแหล, งท, มาท, าเช, อถ, เน, อความท, ไม, แหล, งท, มาอาจถ, กค, ดค, านหร, อลบออก, เร, ยนร, าจะนำสารแม, แบบน, ออกได, อย, างไรและเม, อไร, งกฤษ, black, tree, เป, นต. bthkhwamniimmikarxangxingcakaehlngthimaidkrunachwyprbprungbthkhwamni odyephimkarxangxingaehlngthimathinaechuxthux enuxkhwamthiimmiaehlngthimaxacthukkhdkhanhruxlbxxk eriynruwacanasaraemaebbnixxkidxyangiraelaemuxir tnimaedngda xngkvs Red Black Tree epntnimkhnhaaebbthwiphakhthiprayuktaenwkhidmacaktnimiddul 2 3 4 ihepntnimkhnhaaebbthwiphakh odythipmkhxngtnimaedngdacamikarekbtwaeprhnung mkeriykwasiaedngaelasida misxngsisungsamarthekbdwykhakhwamcringhruxtwaeprkhnadhnungbitid aelathaihtnimnithukeriykchuxwa tnimaedngdatnimaedngda Red Black Tree twxyangtnimaedngdakhwamsakhykhxngladberiyngcaknxyipmakkarsaknkhxngsmachikimxnuyatihsaewlathiichkhnhatamkhaO log n ewlathiichinkarekhathungO log n karthaihwangtharakihepn nullewlathiichthaihwangO 1 okhrngsrangtnaebbtnimkhnhaaebbthwiphakh tnimiddul 2 3 4okhrngsrangthinaipichtnimaebbbikhwamsbsxninkarkhanwnaebbsykrnoxihykhntxnwithithwechliyelwraythisud enuxha 1 lksnakhxngtnimaedngda 2 cudednkhxngtnimaedngda 3 brikarthimkcami 4 khwamerwthiichinkarthangan 5 praephthkhxmulthiichsrangtnimaedngda 6 karsrangbrikarkhxngtnimaedngda 6 1 karephimsmachik 6 2 karlbsmachik 6 3 karkhnhasmachik 7 duephimlksnakhxngtnimaedngda aekikhtnimaedngda epntnimkhnhathwiphakhsungaetla Node khxngtnimcamisikakbkhuxepnsiaednghruximkda epntnimthinaaenwkhidmacaktnimiddul 2 3 4 maprayuktodyich Node aebbsxngthnghmd odysahrb Node aebbsamcathukaethndwy Node aebbsxngsxngaelaeriyngknody Node id Node hnungepnsiaedng swn Node aebbsicathukaethndwy Node aebbsxngsam odylukthngkhuepnsiaedng mikhxkahndtangtamtnimkhnhathwiphakh aelamikhxbngkhbephimetimkhux1 Node epnsiaednghruxsida2 rak Root epnsida3 ib leaves thukibepnsida4 lukkhxng Node thiepnsiaedngtxngepnsida5 thukthangedinxyangngay simple path thangedinthiphanaetla Node ephiyngkhrngediyw cakrakipyngibcaphancanwn Node sidaethakncudednkhxngtnimaedngda aekikhtnimaedngdaddaeplngmacaktnimiddul 2 3 4 sungthukknkhwamsungrahwang log2n thung log4n rayathangcakrakipyngibthixyuiklthisud kbrayathangcakrakipyngibthixyuiklthisudhangknimekin sxngetha phisucnody Contradiction ihrayathanghangknekinsxngetha aetcanwn Node sidacatxngethakntamkhunsmbtikhxngtnimaedngdadngnncanwn Node siaedngkhxngesnthangthiiklyxmtxngmakkwa black height canwn Node sidacakrakipyngib aelamakkwacanwn Node siaedngkhxngesnthangthiikl aetwalukkhxngNodesiaedngcatxngepnsidaesmxthaihekidkhxkhdaeyng cungsamarthbxkidwatnimaedngdanikhxnkhangidduly aelaenuxngcakprasiththiphaphechingewlakhxngkarkrathatangintnimkhnhathwiphakhnnkhunxyukbkhwamsungthaihkarthanganmiprasiththiphaphthidiaemcaxyuinkrniyaaey chakwaimekinsxngethakhxngkrnithidi sungtangcak Binary search tree thwipbrikarthimkcami aekikhkarephim karlb aelakarkhnhakhwamerwthiichinkarthangan aekikhenuxngcaktnimaedngda mikhwamsungcakdaennxnepn log2n thung log4n cungpraknewlakarthanganxyuin O log n praephthkhxmulthiichsrangtnimaedngda aekikhNode khxngtnimaedngdannmikhxmulephimmacak Node khxng binary search tree aebbpktikhuxcamikarephimtwaeprthiekb si aedngda xacepn twelkh hruxkhakhwamcring sungichhnwycaephimkhunephiyngaekhhnungbittxhnungpm karaesdngsixacaesdngdwy edge aethnthicaepnsikhxng nodesungimidthaihekidkhxaetktangaetxyangidkarsrangbrikarkhxngtnimaedngda aekikhkarephimsmachik aekikh karephimsmachikkhxngtnimaedngdacaeliynaebbkarthangankhxngtnimiddul 2 3 4 sungmikarepliynsmachikkhxng Node ihsungkhunip hruxkaraetk Node ehlanisamarthaethndwytnimaedngdadwywithikarcdkartamsmbtikhxngtnimaedngdathiwa lukkhxng Node thiepnsiaedngtxngepnsida aelacdkardngtxipniid ephimsmachikodyichwithikarediywkb binary search tree thwip ephiyngaet Node thiephimihmniihepn Node siaedng sarwcwa Node phxkhxng Node ihmthiephimkhunepnsiaednghruxim thaichcakhdkbsmbtiklawmakhangtn kcathaidsxngwithidngni karslbsisam Node inkrnithimikartxinlksnakhlaykbtx Node aebbsi karslbsisam Node caesmuxnkaraetk Node intnimiddul2 3 4 karhmun Node aelaslbsisam Node inbangkrnikarslbsisam Node echy imxacchwyihthuktxngkbsmbtithiklawmakhangtnid dngnnkarhmun Node ethanncungchwyihsmbtithuktxngaebbnicasxdkhlxngkbkarephimkhxmulin Node intnimiddul2 3 4karlbsmachik aekikh sahrbkar delete kcaepnlksnaediywkbkartha insert khux operation khxngkartha delete thwipcamilksnaehmuxnkb delete khxng Binary Search Tree erimcakphicarnawa Node thicathakar delete nnimmilukepn Node phayin miluk 1 Node epn Node phayin lukthng 2 Node epn Node phayin odythaepnkrnithi Node thicathakar delete immilukepn Node phayinkcalb Node nnthingaelwaethndwy sentinelely aetthami 1 Node phayin kcaaethn Node thitxngkarlbdwylukkhxng Node nnely aelainkrnisudthaycaha successor twthimikhanxythisudthimikhamakkwa Node nn maaelwthakarlb successor aethn aelwyaykhakhxng successor maiwin Node nn caknnktxngphicarnawakarlbnnthaihekidkhxkhdaeynginkhunsmbti 5 khxhruxim odycaekidkhxkhdaeyngkhunemux Node thierathakarlbip epnsidakcatxngthakar fixup ephuxkhcdkhxkhdaeyngip karkhnhasmachik aekikh karkhnhasmachiknnsadwkmakkwatnimiddul2 3 4 ephraaichwithikhnhaaebbediywkb Binary search tree idduephim aekikhtnimexwiaexl thriph tnimbanekhathungcak https th wikipedia org w index php title tnimaedngda amp oldid 6246919, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ
, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม
