| ต้นไม้ |
|---|
การเรียงตัวของต้นไม้ในมโนทัศน์ของโครงสร้างข้อมูล |
| ความสำคัญของลำดับ | เรียงจากน้อยไปมาก |
| การซ้ำกันของสมาชิก | ไม่อนุญาตให้ซ้ำกัน |
| วิธีการเข้าถึง(access) | การแวะผ่านต้นไม้ (tree traversal) |
| เวลาที่ใช้ในการเข้าถึง | O (log n),O (n) (แล้วแต่ลักษณะข้อมูลและโครงสร้างต้นไม้) |
| โครงสร้างข้อมูลที่มีรูปแบบนี้ | ต้นไม้ค้นหาแบบทวิภาค |
ต้นไม้ (อังกฤษ: Tree) เป็น แบบชนิดข้อมูลนามธรรม ประเภทหนึ่ง มีลักษณะการเรียงเป็นกิ่งก้านสาขาแตกแขนงออกไป จะไม่มีวงวน (loop) โยงในสมาชิกตัวต่างๆ โดยสมาชิกจะถูกเก็บไว้ในประเภทข้อมูลชนิดวัตถุ (Object) หรือโครงสร้าง (Structure) เรียกว่าปม (node) ซึ่งจะมีตัวแปรซึ่งเก็บตัวชี้ (Pointer) ไปยังปมอื่นๆได้
ต้นไม้ถูกใช้ในการจัดการข้อมูลที่เปรียบเทียบกันได้ (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 ภาคจะมีความสูงต่ำสุดที่เป็นไปได้คือ
บริการที่มักจะมี - การเพิ่ม ลบ และค้นสมาชิก
- การหาตัวมากที่สุด หรือน้อยที่สุด
- การไล่สมาชิกตามการแวะผ่านต้นไม้ (tree traversal)
ความเร็วที่ใช้ในการทำงาน ต้นไม้เน้นการทำงานอย่างรวดเร็วโดยการตัดทอนกิ่งที่ไม่สนใจ เช่นต้นไม้ค้นหาแบบทวิภาคที่สามารถไล่ไปตามกิ่งของต้นไม้ ทำให้อย่างมากที่สุด การค้นหาก็จะผ่านจำนวนข้อมูลเท่ากับความสูงของต้นไม้ ซึ่งความสูงของต้นไม้ที่น้อยที่สุดเป็น O (log n) จึงทำให้บริการที่เร็วที่สุดเป็น O (log n) อย่างไรก็ตาม หากจัดการไม่เหมาะสม ความสูงของต้นไม้อาจยืดเป็น O (n)ได้ส่งผลให้บริการช้า จึงต้องมีการจำกัดความสูงและคงสมดุลของต้นไม้ให้เหมาะสม
การแวะผ่านต้นไม้ การแวะผ่านต้นไม้ (tree traversal) หมายถึงการทำงานผ่านต้นไม้ใดๆ เช่นการไล่พิมพ์สมาชิก การสร้างแถวลำดับเก็บทุกสมาชิกของต้นไม้ ฯลฯ ที่จำเป็นต้องผ่านสมาชิกทุกๆตัวในต้นไม้ ซึ่งการเรียงลำดับการแวะผ่านต้นไม้จำเป็นต้องใช้ความสัมพันธ์เวียนเกิด การแวะผ่านต้นไม้มีสามแบบดังต่อไปนี้
- การแวะผ่านก่อนลำดับ (preorder traversal) หมายถึงการแวะผ่านโดยให้ความสำคัญรากก่อนแล้วจึงแวะผ่านต้นไม้ย่อยของลูกจากซ้ายไปขวา
- การแวะผ่านตามลำดับ (inorder traversal) หมายถึงการแวะผ่านโดยให้ความสำคัญต้นไม้ย่อยของลูกซ้ายก่อน และกลับมาแวะที่ราก แล้วจึงแวะผ่านต้นไม้ย่อยทางขวา และกลับมาแวะที่ราก เช่นนี้ไปเรื่อยๆสลับกันไป จนถึงต้นไม้ย่อยของลูกสุดท้าย
- การแวะผ่านหลังลำดับ (postorder traversal) หมายถึงการแวะผ่านต้นไม้ย่อยของลูกเรียงจากซ้ายไปขวา แล้วจึงแวะผ่านรากทีหลัง
โครงสร้างข้อมูลที่เป็นต้นไม้ดูเพิ่ม นไม, โครงสร, างข, อม, สำหร, บความหมายอ, นไม, แก, ความกำกวม, นไม, การเร, ยงต, วของต, นไม, ในมโนท, ศน, ของโครงสร, างข, อม, ลความสำค, ญของลำด, เร, ยงจากน, อยไปมากการซ, ำก, นของสมาช, ไม, อน, ญาตให, ำก, นว, การเข, าถ, access, การแวะผ, านต, นไม, tree, traversal, เวล. sahrbkhwamhmayxun duthi tnim aekkhwamkakwm tnimkareriyngtwkhxngtniminmonthsnkhxngokhrngsrangkhxmulkhwamsakhykhxngladb eriyngcaknxyipmakkarsaknkhxngsmachik imxnuyatihsaknwithikarekhathung access karaewaphantnim tree traversal ewlathiichinkarekhathung O log n O n aelwaetlksnakhxmulaelaokhrngsrangtnim okhrngsrangkhxmulthimirupaebbni tnimkhnhaaebbthwiphakhtnim xngkvs Tree epn aebbchnidkhxmulnamthrrm praephthhnung milksnakareriyngepnkingkansakhaaetkaekhnngxxkip caimmiwngwn loop oynginsmachiktwtang odysmachikcathukekbiwinpraephthkhxmulchnidwtthu Object hruxokhrngsrang Structure eriykwapm node sungcamitwaeprsungekbtwchi Pointer ipyngpmxunidtnimthukichinkarcdkarkhxmulthiepriybethiybknid comparable xyangrwderwechn twelkh hrux kareriyngladbkhwamsakhykhxngkhxmul echn karkhanwnthimiwngelb epnxathi enuxha 1 swnprakxbkhxngtnim 2 tnimphiess 3 cudednkhxngtnim 4 smbtikhxngtniminthangkhnitsastrthimkich 5 brikarthimkcami 6 khwamerwthiichinkarthangan 7 karaewaphantnim 8 okhrngsrangkhxmulthiepntnim 9 duephimswnprakxbkhxngtnim aekikhpm 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 pmlukpmhlanthixyuitsmachiktwnnklayepnsmachikkhxngtnimyxyipdwytnimphiess aekikhtnimkhnha search tree hmaythungtnimthitampmidtnimyxycanxykwa 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 hmaythungtnimthipmidsamarthmilukidktxemuxpmphinxngthangsaymilukethann tnimetimetmyxmepntnimiddulipdwy hip heap hmaythungtnimthiemuxphicarnaintnimyxyidintnim rakcamikhwamsakhy priority makthisudcudednkhxngtnim aekikhtnimepnokhrngsrangthiennkhxmulthiepriybethiybknid comparable echntnimkhnha hruxmiladbkhwamsakhyepnkhntxn echnhip mkichinkarcdkarkhnhaxyangrwderwepn O log n hruxkarcdladbkhwamsakhy echnkarcdniphcn sungeriyngladbkarthanganodytnimniphcnsmbtikhxngtniminthangkhnitsastrthimkich aekikhduephimetimthi tnim thvsdikraf tnim m phakhcamikhwamsungtasudthiepnipidkhux l o g m n displaystyle lfloor log m n rfloor brikarthimkcami aekikhkarephim lb aelakhnsmachik karhatwmakthisud hruxnxythisud karilsmachiktamkaraewaphantnim tree traversal khwamerwthiichinkarthangan aekikhtnimennkarthanganxyangrwderwodykartdthxnkingthiimsnic echntnimkhnhaaebbthwiphakhthisamarthiliptamkingkhxngtnim thaihxyangmakthisud karkhnhakcaphancanwnkhxmulethakbkhwamsungkhxngtnim sungkhwamsungkhxngtnimthinxythisudepn O log n cungthaihbrikarthierwthisudepn O log n xyangirktam hakcdkarimehmaasm khwamsungkhxngtnimxacyudepn O n idsngphlihbrikarcha cungtxngmikarcakdkhwamsungaelakhngsmdulkhxngtnimihehmaasmkaraewaphantnim aekikhkaraewaphantnim tree traversal hmaythungkarthanganphantnimid echnkarilphimphsmachik karsrangaethwladbekbthuksmachikkhxngtnim l thicaepntxngphansmachikthuktwintnim sungkareriyngladbkaraewaphantnimcaepntxngichkhwamsmphnthewiynekid karaewaphantnimmisamaebbdngtxipni karaewaphankxnladb preorder traversal hmaythungkaraewaphanodyihkhwamsakhyrakkxnaelwcungaewaphantnimyxykhxnglukcaksayipkhwa karaewaphantamladb inorder traversal hmaythungkaraewaphanodyihkhwamsakhytnimyxykhxngluksaykxn aelaklbmaaewathirak aelwcungaewaphantnimyxythangkhwa aelaklbmaaewathirak echnniiperuxyslbknip cnthungtnimyxykhxngluksudthay karaewaphanhlngladb postorder traversal hmaythungkaraewaphantnimyxykhxnglukeriyngcaksayipkhwa aelwcungaewaphanrakthihlngokhrngsrangkhxmulthiepntnim aekikhtnimkhnhaaebbthwiphakhduephim aekikhtnim thvsdikraf ekhathungcak https th wikipedia org w index php title tnim okhrngsrangkhxmul amp oldid 7021539, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ
, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม
