Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ในวิทยาศาสตร์คอมพิวเตอร์ ต้นไม้สเคปโกท (อังกฤษ: scapegoat tree)เป็นต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ ค้นพบโดย Arne Anderson Igal Galperin และ Ronald L. Rivest ในกรณีแย่ที่สุด จะใช้เวลาค้นข้อมูล O (log n) ใช้เวลาเพิ่มและลบข้อมูลโดยเฉลี่ย O (log n)
ภายในปมหนึ่งปมจะเก็บเพียงข้อมูล และ pointer ไปที่ปมลูกทั้งสอง
ทฤษฎี
ต้นไม้ค้นหาแบบทวิภาคจะสมดุลเมื่อปมทางขวาและปมทางซ้ายของรากเท่ากัน
ถ้าเป็นแบบ α-weight-balanced ต้องเป็นตามเงื่อนไขดังนี้
size (left) <= α*size (node) size (right) <= α*size (node)
โดยที่ size แสดงเป็นฟังก์ชันดังนี้
function size (node) if node = nil return 0 else return size (node->left) + size (node->right) + 1 end
ต้นไม้ค้นหาแบบทวิภาค ที่เป็น α-weight-balanced จะเป็น α-height-balanced ด้วย
height (tree) <= log1/α (NodeCount)
ต้นไม้สเคปโกทไม่รับประกันว่าจะเป็น α-weight-balanced ตลอดเวลา แต่จะใกล้เคียง α-height-balanced เสมอ
height (scapegoat tree) <= log1/α (NodeCount) + 1
ต้นไม้สเคปโกท สามารถใช้ α ที่มีค่าได้ตั้งแต่ 0.5 ถึง 1 จึงมีความยืดหยุ่นในการปรับสมดุล การใช้ค่า α สูงๆ จะทำให้การเพิ่มข้อมูลรวดเร็วขึ้น แต่การค้นและลบข้อมูลช้าลง ในทางกลับกัน ถ้าใช้ α ต่ำๆ ก็เพิ่มข้อมูลก็จะช้า แต่จะค้นและลบข้อมูลได้เร็ว การเลือกค่า α จะขึ้นอยู่กับว่า ขณะทำงานมีการเพิ่ม ค้น ลบข้อมูลบ่อยแค่ไหน
คำสั่ง
การเพิ่มข้อมูล
คล้ายกับต้นไม้ค้นหาแบบทวิภาคที่ไม่ปรับสมดุล แต่ต่างกันเล็กน้อย
เมื่อพบตำแหน่งที่จะแทรก จะต้องบันทึกความสูงของปมที่เพิ่มมาด้วย ถ้าการเพิ่มปมนี้ทำให้ไม่เป็น α-height-balanced ก็ต้องทำการ rebalance ในการ rebalance จะทำการปรับสมดุลของ subtree ที่มีรากเป็น "สเคปโกท"
สเคปโกทเป็นปมปมหนึ่งตามเส้นทางจากปมล่าสุดไปสู่ปมราก การหาสเคปโกททำได้โดยการไล่ย้อนขึ้นไปจากปมใหม่ไปจนถึงราก และเลือกปมที่ subtree ไม่เป็น α-height-balanced
การปีนย้อนขึ้นไปตามปมอาจใช้พื้นที่ O ('log n') ใน stack แต่สามารถเลี่ยงได้โดยให้มี pointer สำหรับชี้ปมลูกไปที่ปมแม่ เพื่อตรวจสอบว่าปมเป็นสเคปโกทหรือไม่ จะต้องหาจำนวนปมลูกทั้งหมดของปมนั้นๆ แล้วตรวจสอบว่าเป็น α-weight-balanced หรือไม่
size (left) <= α *size (node) size (right) <= α *size (node)
และเมื่อไม่สอดคล้องกับเงื่อนไข ก็จะถือว่าเป็นสเคปโกท
เมื่อพบปมที่เป็นสเคปโกทแล้ว ต้นไม้ย่อยที่มีรากเป็นสเคปโกทก็จะต้องถูกสร้างใหม่ให้สมดุล ซึ่งใช้เวลา O (n) โดยการไล่ไปตามต้นไม้ย่อยเพื่อเรียงลำดับข้อมูลและนำค่า median มาใช้เป็นรากใหม่ เพราะฉะนั้น กรณีแย่สุดของการเพิ่มข้อมูล คือเมื่อมีการ rebalance จะใช้เวลา O (n) แต่เมื่อถัวเฉลี่ย จะใช้เวลาเพียง O (log n)
การลบข้อมูล
สำหรับต้นไม้สเคปโกท การลบจะง่ายกว่าการเพิ่มข้อมูล ต้นไม้สเคปโกทต้องมีตัวแปร MaxNodeCount สำหรับเก็บจำนวนปมมากที่สุดที่เคยมี และเมื่อมีการ rebalance จะเก็บค่าใหม่เป็นค่าจำนวนปม (NodeCount) ขณะนั้น การลบจะลบแบบต้นไม้ค้นหาแบบทวิภาค แต่เมื่อ
NodeCount <= MaxNodeCount / 2
จะทำการ rebalance และเก็บค่าจำนวนปมทั้งหมดขณะนั้น (NodeCount) ไปที่ MaxNodeCount เช่นเดียวกับการเพิ่มข้อมูล เมื่อถัวเฉลี่ยแล้ว จะใช้เวลา 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, เว็บ, คอมพิวเตอร์
lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisud inwithyasastrkhxmphiwetxr tnimsekhpokth xngkvs scapegoat tree epntnimkhnhaaebbthwiphakhthimiokhrngsrangprbsmdulexngid khnphbody Arne Anderson Igal Galperin aela Ronald L Rivest inkrniaeythisud caichewlakhnkhxmul O log n ichewlaephimaelalbkhxmulodyechliy O log n phayinpmhnungpmcaekbephiyngkhxmul aela pointer ipthipmlukthngsxngthvsditnimkhnhaaebbthwiphakhcasmdulemuxpmthangkhwaaelapmthangsaykhxngrakethakn thaepnaebb a weight balanced txngepntamenguxnikhdngni size left lt a size node size right lt a size node odythi size aesdngepnfngkchndngni function size node if node nil return 0 else return size node gt left size node gt right 1 end tnimkhnhaaebbthwiphakh thiepn a weight balanced caepn a height balanced dwy height tree lt log1 a NodeCount tnimsekhpokthimrbpraknwacaepn a weight balanced tlxdewla aetcaiklekhiyng a height balanced esmx height scapegoat tree lt log1 a NodeCount 1 tnimsekhpokth samarthich a thimikhaidtngaet 0 5 thung 1 cungmikhwamyudhyuninkarprbsmdul karichkha a sung cathaihkarephimkhxmulrwderwkhun aetkarkhnaelalbkhxmulchalng inthangklbkn thaich a ta kephimkhxmulkcacha aetcakhnaelalbkhxmuliderw kareluxkkha a cakhunxyukbwa khnathanganmikarephim khn lbkhxmulbxyaekhihnkhasngkarephimkhxmul khlaykbtnimkhnhaaebbthwiphakhthiimprbsmdul aettangknelknxy emuxphbtaaehnngthicaaethrk catxngbnthukkhwamsungkhxngpmthiephimmadwy thakarephimpmnithaihimepn a height balanced ktxngthakar rebalance inkar rebalance cathakarprbsmdulkhxng subtree thimirakepn sekhpokth sekhpokthepnpmpmhnungtamesnthangcakpmlasudipsupmrak karhasekhpokththaidodykarilyxnkhunipcakpmihmipcnthungrak aelaeluxkpmthi subtree imepn a height balanced karpinyxnkhuniptampmxacichphunthi O log n in stack aetsamartheliyngidodyihmi pointer sahrbchipmlukipthipmaem ephuxtrwcsxbwapmepnsekhpokthhruxim catxnghacanwnpmlukthnghmdkhxngpmnn aelwtrwcsxbwaepn a weight balanced hruxim size left lt a size node size right lt a size node aelaemuximsxdkhlxngkbenguxnikh kcathuxwaepnsekhpokth emuxphbpmthiepnsekhpokthaelw tnimyxythimirakepnsekhpokthkcatxngthuksrangihmihsmdul sungichewla O n odykariliptamtnimyxyephuxeriyngladbkhxmulaelanakha median maichepnrakihm ephraachann krniaeysudkhxngkarephimkhxmul khuxemuxmikar rebalance caichewla O n aetemuxthwechliy caichewlaephiyng O log n karlbkhxmul sahrbtnimsekhpokth karlbcangaykwakarephimkhxmul tnimsekhpokthtxngmitwaepr MaxNodeCount sahrbekbcanwnpmmakthisudthiekhymi aelaemuxmikar rebalance caekbkhaihmepnkhacanwnpm NodeCount khnann karlbcalbaebbtnimkhnhaaebbthwiphakh aetemux NodeCount lt MaxNodeCount 2 cathakar rebalance aelaekbkhacanwnpmthnghmdkhnann NodeCount ipthi MaxNodeCount echnediywkbkarephimkhxmul emuxthwechliyaelw caichewla O log n karkhnkhxmul ichwithikhnkhxmulaebbediywkbtnimkhnhaaebbthwiphakh ichewla O log n