ต้นไม้ค้นหาแบบทวิภาค (อังกฤษ: binary search tree , BST) เป็นโครงสร้างข้อมูล ซึ่งใช้โครงสร้างต้นไม้ในการทำต้นไม้ค้นหาแบบทวิภาคต่างจากต้นไม้แบบทวิภาคตรงที่ส่วนของต้นไม้ด้านซ้ายของข้อมูลใดๆ จะน้อยกว่าข้อมูลนั้น และส่วนของต้นไม้ด้านขวาของข้อมูลใดๆ จะมากกว่าข้อมูลนั้นเสมอ ต้นไม้ค้นหาแบบทวิภาคสร้างขึ้นมาเพื่อให้เติมลบ หรือหาได้ง่าย สำหรับข้อมูลที่เปรียบเทียบกันได้ ต้นไม้ค้นหาแบบทวิภาคมักใช้ในการทำโครงสร้างข้อมูลชนิดอื่นๆต่อไป
| ต้นไม้ค้นหาแบบทวิภาค |
|---|
การเรียงตัวของต้นไม้ค้นหาแบบทวิภาค |
| ความสำคัญของลำดับ | เรียงจากน้อยไปมาก |
|---|
| การซ้ำกันของสมาชิก | ไม่อนุญาตให้ซ้ำ |
|---|
| เวลาที่ใช้ค้นหาตามดัชนี | - |
|---|
| เวลาที่ใช้ค้นหาตามค่า | โดยเฉลี่ย O(log n) กรณีแย่สุด O(n) |
|---|
| เวลาที่ใช้ในการเข้าถึง | โดยเฉลี่ย O(log n) กรณีแย่สุด O(n) |
|---|
| การทำให้ว่าง | ลบรากทิ้ง |
|---|
| เวลาที่ใช้ทำให้ว่าง | O(1) |
|---|
| โครงสร้างต้นแบบ | ต้นไม้ทวิภาค |
|---|
| โครงสร้างที่นำไปใช้ | ต้นไม้AVL |
|---|
| ความซับซ้อนในการคำนวณแบบสัญกรณ์โอใหญ่ |
|---|
| ขั้นตอนวิธี | | ถัวเฉลี่ย | เลวร้ายที่สุด |
|---|
| เนื้อที่ | | O(n) | O(n) |
|---|
| การค้นหา | | O(log n) | O(n) |
|---|
| การเพิ่ม | | O(log n) | O(n) |
|---|
| การลบ | | O(log n) | O(n) |
|---|
|
ต้นไม้ค้นหาแบบทวิภาคจะต้องเป็นต้นไม้ทวิภาค กล่าวคือมีสองลูกต่อหนึ่งโนด และส่วนของต้นไม้ด้านซ้าย (left subtree) จะต้องน้อยกว่า ตัวข้อมูล และส่วนของต้นไม้ด้านขวา (right subtree) จะต้องมากกว่า ตัวข้อมูลเสมอ สำหรับข้อมูลที่ใช้ในต้นไม้ค้นหาแบบทวิภาคเราจะใช้ข้อมูลที่เปรียบเทียบกันได้ (Comparable) เช่นตัวเลข ซึ่งสามารถบอกได้ว่าสิ่งใดมากกว่าหรือน้อยกว่าอีกสิ่งหนึ่งได้
จุดเด่นของต้นไม้ค้นหาแบบทวิภาค จุดเด่นของต้นไม้ค้นหาแบบทวิภาคคือการเอาออก นำเข้า และการเรียงลำดับของข้อมูลอยู่ตลอดเวลา และการค้นหาแบบ ทวิภาค (binary search) ทำให้ตัดออกได้เป็นส่วนๆ และใช้เวลาโดยเฉลี่ย O(log n)
บริการที่มักจะมี - หาจุดยอดที่เก็บสมาชิก e
- การเพิ่ม/ลบข้อมูล สมาชิก e
- การไล่ลำดับสมาชิก และการแวะผ่านต้นไม้
- การสำรวจสมาชิกพิเศษ เช่น สมาชิกที่เป็นใบ
ความเร็วที่ใช้ในการทำงาน ความเร็วในการทำงานส่วนมากยังเป็น O(log n) เนื่องจากมีการค้นหาเป็นการค้นหาแบบทวิภาค ซึ่งตัดสิ่งที่เป็นไปไม่ได้ออกครึ่งหนึ่ง ทำให้ทำงานได้รวดเร็ว แต่บางกรณี ที่ต้นไม้ยาว (ยาวสุดคือต่อกันเป็นรายการโยง) เช่นนี้อาจทำให้ต้นไม้ทำงานช้า ไม่สามารถการันตีประสิทธิภาพได้ นำไปสู่แนวคิดการทำต้นไม้เอวีแอลต่อไป
| การทำงาน | เวลา |
|---|
| การหาตามดัชนี | - |
| การเข้าถึงสมาชิก | O(log n) |
นไม, นหาแบบทว, ภาค, บทความน, ไม, การอ, างอ, งจากแหล, งท, มาใดกร, ณาช, วยปร, บปร, งบทความน, โดยเพ, มการอ, างอ, งแหล, งท, มาท, าเช, อถ, เน, อความท, ไม, แหล, งท, มาอาจถ, กค, ดค, านหร, อลบออก, เร, ยนร, าจะนำสารแม, แบบน, ออกได, อย, างไรและเม, อไร, งกฤษ, binary, sea. bthkhwamniimmikarxangxingcakaehlngthimaidkrunachwyprbprungbthkhwamni odyephimkarxangxingaehlngthimathinaechuxthux enuxkhwamthiimmiaehlngthimaxacthukkhdkhanhruxlbxxk eriynruwacanasaraemaebbnixxkidxyangiraelaemuxir tnimkhnhaaebbthwiphakh xngkvs binary search tree BST epnokhrngsrangkhxmul sungichokhrngsrangtniminkarthatnimkhnhaaebbthwiphakhtangcaktnimaebbthwiphakhtrngthiswnkhxngtnimdansaykhxngkhxmulid canxykwakhxmulnn aelaswnkhxngtnimdankhwakhxngkhxmulid camakkwakhxmulnnesmx tnimkhnhaaebbthwiphakhsrangkhunmaephuxihetimlb hruxhaidngay sahrbkhxmulthiepriybethiybknid tnimkhnhaaebbthwiphakhmkichinkarthaokhrngsrangkhxmulchnidxuntxiptnimkhnhaaebbthwiphakhkareriyngtwkhxngtnimkhnhaaebbthwiphakhkhwamsakhykhxngladberiyngcaknxyipmakkarsaknkhxngsmachikimxnuyatihsaewlathiichkhnhatamdchni ewlathiichkhnhatamkhaodyechliy O log n krniaeysud O n ewlathiichinkarekhathungodyechliy O log n krniaeysud O n karthaihwanglbrakthingewlathiichthaihwangO 1 okhrngsrangtnaebbtnimthwiphakhokhrngsrangthinaipichtnimAVLkhwamsbsxninkarkhanwnaebbsykrnoxihykhntxnwithithwechliyelwraythisudenuxthiO n O n karkhnhaO log n O n karephimO log n O n karlbO log n O n enuxha 1 lksnakhxngtnimkhnhathwiphakh 2 cudednkhxngtnimkhnhaaebbthwiphakh 3 brikarthimkcami 4 khwamerwthiichinkarthangan 5 duephimlksnakhxngtnimkhnhathwiphakh aekikhtnimkhnhaaebbthwiphakhcatxngepntnimthwiphakh klawkhuxmisxngluktxhnungond aelaswnkhxngtnimdansay left subtree catxngnxykwa twkhxmul aelaswnkhxngtnimdankhwa right subtree catxngmakkwa twkhxmulesmx sahrbkhxmulthiichintnimkhnhaaebbthwiphakheracaichkhxmulthiepriybethiybknid Comparable echntwelkh sungsamarthbxkidwasingidmakkwahruxnxykwaxiksinghnungidcudednkhxngtnimkhnhaaebbthwiphakh aekikhcudednkhxngtnimkhnhaaebbthwiphakhkhuxkarexaxxk naekha aelakareriyngladbkhxngkhxmulxyutlxdewla aelakarkhnhaaebb thwiphakh binary search thaihtdxxkidepnswn aelaichewlaodyechliy O log n brikarthimkcami aekikhhacudyxdthiekbsmachik e karephim lbkhxmul smachik e karilladbsmachik aelakaraewaphantnim karsarwcsmachikphiess echn smachikthiepnibkhwamerwthiichinkarthangan aekikhkhwamerwinkarthanganswnmakyngepn O log n enuxngcakmikarkhnhaepnkarkhnhaaebbthwiphakh sungtdsingthiepnipimidxxkkhrunghnung thaihthanganidrwderw aetbangkrni thitnimyaw yawsudkhuxtxknepnraykaroyng echnnixacthaihtnimthangancha imsamarthkarntiprasiththiphaphid naipsuaenwkhidkarthatnimexwiaexltxip karthangan ewlakarhatamdchni karekhathungsmachik O log n duephim aekikhtnim khnitsastr okhrngsrangkhxmul bthkhwamekiywkbkhnitsastrniyngepnokhrng khunsamarthchwywikiphiediyidodyephimkhxmul duephimthi sthaniyxy khnitsastrekhathungcak https th wikipedia org w index php title tnimkhnhaaebbthwiphakh amp oldid 5339906, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ
, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม
