ต้นไม้สเคปโกท

ในวิทยาศาสตร์คอมพิวเตอร์ ต้นไม้สเคปโกท (อังกฤษ: 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)