Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ต้นไม้ (อังกฤษ: Tree) เป็น แบบชนิดข้อมูลนามธรรม ประเภทหนึ่ง มีลักษณะการเรียงเป็นกิ่งก้านสาขาแตกแขนงออกไป จะไม่มีวงวน (loop) โยงในสมาชิกตัวต่าง ๆ โดยสมาชิกจะถูกเก็บไว้ในชนิดวัตถุ (Object) หรือโครงสร้าง (Structure) เรียกว่าปม (node) ซึ่งจะมีตัวแปรซึ่งเก็บตัวชี้ (Pointer) ไปยังปมอื่น ๆ ได้
| ต้นไม้ | |
|---|---|
 การเรียงตัวของต้นไม้ในมโนทัศน์ของโครงสร้างข้อมูล | |
| ความสำคัญของลำดับ | เรียงจากน้อยไปมาก |
| การซ้ำกันของสมาชิก | ไม่อนุญาตให้ซ้ำกัน |
| เวลาที่ใช้ในการเข้าถึง | การแวะผ่านต้นไม้ (tree traversal) |
| โครงสร้างที่นำไปใช้ | ต้นไม้ค้นหาแบบทวิภาค |
ต้นไม้ถูกใช้ในการจัดการข้อมูลที่เปรียบเทียบกันได้ (comparable) อย่างรวดเร็วเช่น ตัวเลข หรือ การเรียงลำดับความสำคัญของข้อมูล เช่น การคำนวณที่มีวงเล็บ เป็นอาทิ
ส่วนประกอบของต้นไม้
- ปม (node) หมายถึงสิ่งที่เก็บสมาชิกของต้นไม้
- ราก (root) หมายถึงปมที่เราใช้เริ่มค้นหาภายในต้นไม้ ถ้าเป็น null หมายถึงต้นไม้ว่าง (empty tree)
- ปมลูก (child node) หมายถึงปมที่แตกออกมาจากของปมดังกล่าว ส่วนปมที่ปมดังกล่าวแตกมาเรียกว่า ปมพ่อ (parent node) และเรียกปมพ่อของปมพ่อว่า ปมปู่ (grandparent node) และเรียกตามลำดับการนับญาติฝ่ายพ่อไปเรื่อย ๆ ส่วนปมลูกของปมลูกก็จะเป็นปมหลาน (grandchild node) ไปเรื่อย ๆ ตามลำดับการเรียกญาติฝ่ายลูก
- ปมที่มีปมพ่อเป็นปมเดียวกันเรียกว่า ปมพี่น้อง (sibling node)
- ปมที่มี m ลูก เราจะเรียกว่า ปมแบบ m (m-type node)
- ใบ (leaf node) หมายถึงปมที่ไม่มีปมลูก
- การเขียนต้นไม้มักเขียนปมรากอยู่ข้างบน และเขียนแตกแขนงลงมาให้ปมใบอยู่ข้างล่าง
- ความลึกของปม (node depth) หมายถึงจำนวนครั้งของความสัมพันธ์เชิงพ่อ-ลูก ระหว่าง ปมรากถึงปมใด ๆ
- ความสูง (tree height) หมายถึงความลึกของใบที่ลึกที่สุด สำหรับต้นไม้ที่มีแต่รากจะสูง 0 และต้นไม้ว่างอาจตั้งได้ว่าสูง -1
- ต้นไม้ย่อย (subtree) หมายถึงต้นไม้ย่อยที่ใช้สมาชิกของต้นไม้ที่เราพิจารณา ไปเป็นรากส่งผลให้ ปมลูกปมหลานที่อยู่ใต้สมาชิกตัวนั้นกลายเป็นสมาชิกของต้นไม้ย่อยไปด้วย
ต้นไม้พิเศษ
- ต้นไม้ค้นหา (search tree) หมายถึงต้นไม้ที่ตามปมใด ๆ ต้นไม้ย่อยจะน้อยกว่า มากกว่า หรืออยู่ระหว่าง สมาชิกของปมนั้น ในลักษณะการเรียงลำดับ สำหรับต้นไม้ค้นหาที่มีปมแบบ m ใด ๆ ย่อมมีสมาชิกให้เปรียบเทียบ m-1 ตัวในปมนั้น เช่น ปมแบบสาม จะมีสมาชิกสองตัว
- ต้นไม้ m ภาค (m-ary tree) หมายถึงต้นไม้ที่ใช้แต่ปมแบบ m กล่าวคือมี m ลูก
- ต้นไม้แบบทวิภาค (binary tree) หมายถึงต้นไม้ที่มีแต่ปมแบบสอง
- ต้นไม้ค้นหาแบบทวิภาค (binary search tree) หมายถึงต้นไม้ที่มีแต่ปมแบบสอง โดยต้นไม้ย่อยของลูกซ้าย (left child subtree) จะมีค่าน้อยกว่าปมนั้น ๆ และต้นไม้ย่อยของลูกขวา (right child subtree) จะมีค่ามากกว่าปมนั้น ๆ
- ต้นไม้ประกันการทำงาน หมายถึงต้นไม้ที่ประกันความเร็วการทำงานเป็น O (log n)
- ต้นไม้ประกันความสูง หมายถึงต้นไม้ที่ประกันความสูงเป็น O (log n) ต้นไม้ประกันความสูงย่อมเป็นต้นไม้ประกันการทำงานไปด้วย
- ต้นไม้ได้ดุล (balanced tree) หมายถึงต้นไม้ที่มีความสูงต่ำสุดเท่าที่เป็นไปได้สำหรับชุดข้อมูลใด ๆ ต้นไม้ได้ดุลย่อมเป็นต้นไม้ที่ประกันความสูงไปด้วย
- ต้นไม้เติมเต็ม (completed tree) หมายถึงต้นไม้ที่ปมใด ๆ สามารถมีลูกได้ก็ต่อเมื่อปมพี่น้องทางซ้ายมีลูกเท่านั้น ต้นไม้เติมเต็มย่อมเป็นต้นไม้ได้ดุลไปด้วย
- ฮีป (heap) หมายถึงต้นไม้ที่เมื่อพิจารณาในต้นไม้ย่อยใด ๆ ในต้นไม้ รากจะมีความสำคัญ (priority) มากที่สุด
จุดเด่นของต้นไม้
ต้นไม้เป็นโครงสร้างที่เน้นข้อมูลที่เปรียบเทียบกันได้ (comparable) เช่นต้นไม้ค้นหา หรือมีลำดับความสำคัญเป็นขั้นตอน เช่นฮีป มักใช้ในการจัดการค้นหาอย่างรวดเร็วเป็น O (log n) หรือการจัดลำดับความสำคัญ เช่นการจัดนิพจน์ ซึ่งเรียงลำดับการทำงานโดยต้นไม้นิพจน์
สมบัติของต้นไม้ในทางคณิตศาสตร์ที่มักใช้
- ต้นไม้ m ภาคจะมีความสูงต่ำสุดที่เป็นไปได้คือ
![image]()
บริการที่มักจะมี
- การเพิ่ม ลบ และค้นสมาชิก
- การหาตัวมากที่สุด หรือน้อยที่สุด
- การไล่สมาชิกตามการแวะผ่านต้นไม้ (tree traversal)
ความเร็วที่ใช้ในการทำงาน
ต้นไม้เน้นการทำงานอย่างรวดเร็วโดยการตัดทอนกิ่งที่ไม่สนใจ เช่นต้นไม้ค้นหาแบบทวิภาคที่สามารถไล่ไปตามกิ่งของต้นไม้ ทำให้อย่างมากที่สุด การค้นหาก็จะผ่านจำนวนข้อมูลเท่ากับความสูงของต้นไม้ ซึ่งความสูงของต้นไม้ที่น้อยที่สุดเป็น O (log n) จึงทำให้บริการที่เร็วที่สุดเป็น O (log n) อย่างไรก็ตาม หากจัดการไม่เหมาะสม ความสูงของต้นไม้อาจยืดเป็น O (n)ได้ส่งผลให้บริการช้า จึงต้องมีการจำกัดความสูงและคงสมดุลของต้นไม้ให้เหมาะสม
การแวะผ่านต้นไม้
การแวะผ่านต้นไม้ (tree traversal) หมายถึงการทำงานผ่านต้นไม้ใด ๆ เช่นการไล่พิมพ์สมาชิก การสร้างแถวลำดับเก็บทุกสมาชิกของต้นไม้ ฯลฯ ที่จำเป็นต้องผ่านสมาชิกทุก ๆ ตัวในต้นไม้ ซึ่งการเรียงลำดับการแวะผ่านต้นไม้จำเป็นต้องใช้ความสัมพันธ์เวียนเกิด การแวะผ่านต้นไม้มีสามแบบดังต่อไปนี้
- การแวะผ่านก่อนลำดับ (preorder traversal) หมายถึงการแวะผ่านโดยให้ความสำคัญรากก่อนแล้วจึงแวะผ่านต้นไม้ย่อยของลูกจากซ้ายไปขวา
- การแวะผ่านตามลำดับ (inorder traversal) หมายถึงการแวะผ่านโดยให้ความสำคัญต้นไม้ย่อยของลูกซ้ายก่อน และกลับมาแวะที่ราก แล้วจึงแวะผ่านต้นไม้ย่อยทางขวา และกลับมาแวะที่ราก เช่นนี้ไปเรื่อย ๆสลับกันไป จนถึงต้นไม้ย่อยของลูกสุดท้าย
- การแวะผ่านหลังลำดับ (postorder traversal) หมายถึงการแวะผ่านต้นไม้ย่อยของลูกเรียงจากซ้ายไปขวา แล้วจึงแวะผ่านรากทีหลัง
โครงสร้างข้อมูลที่เป็นต้นไม้
ดูเพิ่ม
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
tnim xngkvs Tree epn aebbchnidkhxmulnamthrrm praephthhnung milksnakareriyngepnkingkansakhaaetkaekhnngxxkip caimmiwngwn loop oynginsmachiktwtang odysmachikcathukekbiwinchnidwtthu Object hruxokhrngsrang Structure eriykwapm node sungcamitwaeprsungekbtwchi Pointer ipyngpmxun idtnimkareriyngtwkhxngtniminmonthsnkhxngokhrngsrangkhxmulkhwamsakhykhxngladberiyngcaknxyipmakkarsaknkhxngsmachikimxnuyatihsaknewlathiichinkarekhathungkaraewaphantnim tree traversal okhrngsrangthinaipichtnimkhnhaaebbthwiphakh tnimthukichinkarcdkarkhxmulthiepriybethiybknid comparable xyangrwderwechn twelkh hrux kareriyngladbkhwamsakhykhxngkhxmul echn karkhanwnthimiwngelb epnxathiswnprakxbkhxngtnimpm node hmaythungsingthiekbsmachikkhxngtnim rak root hmaythungpmthieraicherimkhnhaphayintnim thaepn null hmaythungtnimwang empty tree pmluk child node hmaythungpmthiaetkxxkmacakkhxngpmdngklaw swnpmthipmdngklawaetkmaeriykwa pmphx parent node aelaeriykpmphxkhxngpmphxwa pmpu grandparent node aelaeriyktamladbkarnbyatifayphxiperuxy swnpmlukkhxngpmlukkcaepnpmhlan grandchild node iperuxy tamladbkareriykyatifayluk pmthimipmphxepnpmediywkneriykwa pmphinxng sibling node pmthimi m luk eracaeriykwa pmaebb m m type node ib leaf node hmaythungpmthiimmipmluk karekhiyntnimmkekhiynpmrakxyukhangbn aelaekhiynaetkaekhnnglngmaihpmibxyukhanglang khwamlukkhxngpm node depth hmaythungcanwnkhrngkhxngkhwamsmphnthechingphx luk rahwang pmrakthungpmid khwamsung tree height hmaythungkhwamlukkhxngibthilukthisud sahrbtnimthimiaetrakcasung 0 aelatnimwangxactngidwasung 1 tnimyxy subtree hmaythungtnimyxythiichsmachikkhxngtnimthieraphicarna ipepnraksngphlih pmlukpmhlanthixyuitsmachiktwnnklayepnsmachikkhxngtnimyxyipdwytnimphiesstnimkhnha search tree hmaythungtnimthitampmid tnimyxycanxykwa makkwa hruxxyurahwang smachikkhxngpmnn inlksnakareriyngladb sahrbtnimkhnhathimipmaebb m id yxmmismachikihepriybethiyb m 1 twinpmnn echn pmaebbsam camismachiksxngtw tnim m phakh m ary tree hmaythungtnimthiichaetpmaebb m klawkhuxmi m luk tnimaebbthwiphakh binary tree hmaythungtnimthimiaetpmaebbsxng tnimkhnhaaebbthwiphakh binary search tree hmaythungtnimthimiaetpmaebbsxng odytnimyxykhxngluksay left child subtree camikhanxykwapmnn aelatnimyxykhxnglukkhwa right child subtree camikhamakkwapmnn tnimpraknkarthangan hmaythungtnimthipraknkhwamerwkarthanganepn O log n tnimpraknkhwamsung hmaythungtnimthipraknkhwamsungepn O log n tnimpraknkhwamsungyxmepntnimpraknkarthanganipdwy tnimiddul balanced tree hmaythungtnimthimikhwamsungtasudethathiepnipidsahrbchudkhxmulid tnimiddulyxmepntnimthipraknkhwamsungipdwy tnimetimetm completed tree hmaythungtnimthipmid samarthmilukidktxemuxpmphinxngthangsaymilukethann tnimetimetmyxmepntnimiddulipdwy hip heap hmaythungtnimthiemuxphicarnaintnimyxyid intnim rakcamikhwamsakhy priority makthisudcudednkhxngtnimtnimepnokhrngsrangthiennkhxmulthiepriybethiybknid comparable echntnimkhnha hruxmiladbkhwamsakhyepnkhntxn echnhip mkichinkarcdkarkhnhaxyangrwderwepn O log n hruxkarcdladbkhwamsakhy echnkarcdniphcn sungeriyngladbkarthanganodytnimniphcnsmbtikhxngtniminthangkhnitsastrthimkichtnim m phakhcamikhwamsungtasudthiepnipidkhux logmn displaystyle lfloor log m n rfloor brikarthimkcamikarephim lb aelakhnsmachik karhatwmakthisud hruxnxythisud karilsmachiktamkaraewaphantnim tree traversal khwamerwthiichinkarthangantnimennkarthanganxyangrwderwodykartdthxnkingthiimsnic echntnimkhnhaaebbthwiphakhthisamarthiliptamkingkhxngtnim thaihxyangmakthisud karkhnhakcaphancanwnkhxmulethakbkhwamsungkhxngtnim sungkhwamsungkhxngtnimthinxythisudepn O log n cungthaihbrikarthierwthisudepn O log n xyangirktam hakcdkarimehmaasm khwamsungkhxngtnimxacyudepn O n idsngphlihbrikarcha cungtxngmikarcakdkhwamsungaelakhngsmdulkhxngtnimihehmaasmkaraewaphantnimkaraewaphantnim tree traversal hmaythungkarthanganphantnimid echnkarilphimphsmachik karsrangaethwladbekbthuksmachikkhxngtnim l thicaepntxngphansmachikthuk twintnim sungkareriyngladbkaraewaphantnimcaepntxngichkhwamsmphnthewiynekid karaewaphantnimmisamaebbdngtxipni karaewaphankxnladb preorder traversal hmaythungkaraewaphanodyihkhwamsakhyrakkxnaelwcungaewaphantnimyxykhxnglukcaksayipkhwa karaewaphantamladb inorder traversal hmaythungkaraewaphanodyihkhwamsakhytnimyxykhxngluksaykxn aelaklbmaaewathirak aelwcungaewaphantnimyxythangkhwa aelaklbmaaewathirak echnniiperuxy slbknip cnthungtnimyxykhxngluksudthay karaewaphanhlngladb postorder traversal hmaythungkaraewaphantnimyxykhxnglukeriyngcaksayipkhwa aelwcungaewaphanrakthihlngokhrngsrangkhxmulthiepntnimtnimkhnhaaebbthwiphakhduephimtnim thvsdikraf