Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
บทความนี้ไม่มีจาก |
ต้นไม้ค้นหาแบบทวิภาค (อังกฤษ: binary search tree , BST) เป็นโครงสร้างข้อมูล ซึ่งใช้โครงสร้างต้นไม้ในการทำต้นไม้ค้นหาแบบทวิภาคต่างจากต้นไม้แบบทวิภาคตรงที่ส่วนของต้นไม้ด้านซ้ายของข้อมูลใดๆ จะน้อยกว่าข้อมูลนั้น และส่วนของต้นไม้ด้านขวาของข้อมูลใดๆ จะมากกว่าข้อมูลนั้นเสมอ ต้นไม้ค้นหาแบบทวิภาคสร้างขึ้นมาเพื่อให้เติมลบ หรือหาได้ง่าย สำหรับข้อมูลที่เปรียบเทียบกันได้ ต้นไม้ค้นหาแบบทวิภาคมักใช้ในการทำโครงสร้างข้อมูลชนิดอื่นๆต่อไป
| ต้นไม้ค้นหาแบบทวิภาค | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
 การเรียงตัวของต้นไม้ค้นหาแบบทวิภาค | |||||||||||||||||||||
| ความสำคัญของลำดับ | เรียงจากน้อยไปมาก | ||||||||||||||||||||
| การซ้ำกันของสมาชิก | ไม่อนุญาตให้ซ้ำ | ||||||||||||||||||||
| เวลาที่ใช้ค้นหาตามดัชนี | - | ||||||||||||||||||||
| เวลาที่ใช้ค้นหาตามค่า | โดยเฉลี่ย O(log n) กรณีแย่สุด O(n) | ||||||||||||||||||||
| เวลาที่ใช้ในการเข้าถึง | โดยเฉลี่ย O(log n) กรณีแย่สุด O(n) | ||||||||||||||||||||
| การทำให้ว่าง | ลบรากทิ้ง | ||||||||||||||||||||
| เวลาที่ใช้ทำให้ว่าง | O(1) | ||||||||||||||||||||
| โครงสร้างต้นแบบ | ต้นไม้ทวิภาค | ||||||||||||||||||||
| โครงสร้างที่นำไปใช้ | |||||||||||||||||||||
| ความซับซ้อนในการคำนวณแบบสัญกรณ์โอใหญ่ | |||||||||||||||||||||
| |||||||||||||||||||||
ลักษณะของต้นไม้ค้นหาทวิภาค
ต้นไม้ค้นหาแบบทวิภาคจะต้องเป็นต้นไม้ทวิภาค กล่าวคือมีสองลูกต่อหนึ่งโนด และส่วนของต้นไม้ด้านซ้าย (left subtree) จะต้องน้อยกว่า ตัวข้อมูล และส่วนของต้นไม้ด้านขวา (right subtree) จะต้องมากกว่า ตัวข้อมูลเสมอ สำหรับข้อมูลที่ใช้ในต้นไม้ค้นหาแบบทวิภาคเราจะใช้ข้อมูลที่เปรียบเทียบกันได้ (Comparable) เช่นตัวเลข ซึ่งสามารถบอกได้ว่าสิ่งใดมากกว่าหรือน้อยกว่าอีกสิ่งหนึ่งได้
จุดเด่นของต้นไม้ค้นหาแบบทวิภาค
จุดเด่นของต้นไม้ค้นหาแบบทวิภาคคือการเอาออก นำเข้า และการเรียงลำดับของข้อมูลอยู่ตลอดเวลา และการค้นหาแบบ ทวิภาค (binary search) ทำให้ตัดออกได้เป็นส่วนๆ และใช้เวลาโดยเฉลี่ย O(log n)
บริการที่มักจะมี
- หาจุดยอดที่เก็บสมาชิก e
- การเพิ่ม/ลบข้อมูล สมาชิก e
- การไล่ลำดับสมาชิก และการแวะผ่านต้นไม้
- การสำรวจสมาชิกพิเศษ เช่น สมาชิกที่เป็นใบ
ความเร็วที่ใช้ในการทำงาน
ความเร็วในการทำงานส่วนมากยังเป็น O(log n) เนื่องจากมีการค้นหาเป็นการค้นหาแบบทวิภาค ซึ่งตัดสิ่งที่เป็นไปไม่ได้ออกครึ่งหนึ่ง ทำให้ทำงานได้รวดเร็ว แต่บางกรณี ที่ต้นไม้ยาว (ยาวสุดคือต่อกันเป็นรายการโยง) เช่นนี้อาจทำให้ต้นไม้ทำงานช้า ไม่สามารถการันตีประสิทธิภาพได้ นำไปสู่แนวคิดการทำต่อไป
| การทำงาน | เวลา |
|---|---|
| การหาตามดัชนี | - |
| การเข้าถึงสมาชิก | O(log n) |
ดูเพิ่ม
 | บทความคณิตศาสตร์นี้ยังเป็น คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มเติมข้อมูล |
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
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 okhrngsrangtnaebbtnimthwiphakhokhrngsrangthinaipichkhwamsbsxninkarkhanwnaebbsykrnoxihykhntxnwithithwechliyelwraythisudenuxthiO n O n karkhnhaO log n O n karephimO log n O n karlbO log n O n lksnakhxngtnimkhnhathwiphakhtnimkhnhaaebbthwiphakhcatxngepntnimthwiphakh klawkhuxmisxngluktxhnungond aelaswnkhxngtnimdansay left subtree catxngnxykwa twkhxmul aelaswnkhxngtnimdankhwa right subtree catxngmakkwa twkhxmulesmx sahrbkhxmulthiichintnimkhnhaaebbthwiphakheracaichkhxmulthiepriybethiybknid Comparable echntwelkh sungsamarthbxkidwasingidmakkwahruxnxykwaxiksinghnungidcudednkhxngtnimkhnhaaebbthwiphakhcudednkhxngtnimkhnhaaebbthwiphakhkhuxkarexaxxk naekha aelakareriyngladbkhxngkhxmulxyutlxdewla aelakarkhnhaaebb thwiphakh binary search thaihtdxxkidepnswn aelaichewlaodyechliy O log n brikarthimkcamihacudyxdthiekbsmachik e karephim lbkhxmul smachik e karilladbsmachik aelakaraewaphantnim karsarwcsmachikphiess echn smachikthiepnibkhwamerwthiichinkarthangankhwamerwinkarthanganswnmakyngepn O log n enuxngcakmikarkhnhaepnkarkhnhaaebbthwiphakh sungtdsingthiepnipimidxxkkhrunghnung thaihthanganidrwderw aetbangkrni thitnimyaw yawsudkhuxtxknepnraykaroyng echnnixacthaihtnimthangancha imsamarthkarntiprasiththiphaphid naipsuaenwkhidkarthatxip karthangan ewlakarhatamdchni karekhathungsmachik O log n duephimtnim khnitsastr okhrngsrangkhxmulbthkhwamkhnitsastrniyngepnokhrng khunsamarthchwywikiphiediyidodykarephimetimkhxmuldk