ต้นไม้แพะรับบาป

ต้นไม้แพะรับบาป
พิมพ์	ต้นไม้
ประดิษฐ์	1989
คิดค้นโดย	อาร์เน่ แอนเดอร์สสัน , อิกัล กัลเปริน , โรนัลด์ แอล. ริเวสต์
ความซับซ้อนในสัญกรณ์บิ๊กโอ
ความซับซ้อนของพื้นที่ ช่องว่าง ${\displaystyle O(n)}$ ความซับซ้อนเชิงเวลา การทำงาน ตัดจำหน่าย กรณีที่เลวร้ายที่สุด ค้นหา ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$[ 1 ] : 165 แทรก ${\displaystyle O(\log n)}$[ 1 ] : 165 ${\displaystyle O(n)}$[ 1 ] : 167 ลบ ${\displaystyle O(\log n)}$[ 1 ] : 165 ${\displaystyle O(n)}$[ 1 ] : 167

ในวิทยาการคอมพิวเตอร์ต้นไม้แพะรับบาปเป็นต้นไม้ค้นหาไบนารีที่สมดุลตัวเองซึ่งคิดค้นโดยArne Andersson ^{[ 2 ]}ในปี 1989 และอีกครั้งโดยIgal GalperinและRonald L. Rivestในปี 1993 ^{[ 1 ]} โดยให้เวลาค้นหาในกรณีที่เลวร้ายที่สุด (โดยที่ เป็นจำนวนรายการ) และเวลาแทรกและลบ โดยเฉลี่ย${\displaystyle {\color {Blue}O(\log n)}}$${\displaystyle n}$${\displaystyle O(\log n)}$

แตกต่างจากต้นไม้ค้นหาแบบไบนารีที่ปรับสมดุลตัวเองได้ส่วนใหญ่ ซึ่งให้เวลาค้นหาในกรณีที่เลวร้ายที่สุดเช่นกัน ต้นไม้แพะรับบาปไม่มีค่าใช้จ่ายด้านหน่วยความจำเพิ่มเติมต่อโหนดเมื่อเทียบกับต้นไม้ค้นหาแบบไบนารี ทั่วไป กล่าวคือ นอกเหนือจากคีย์และค่าแล้ว โหนดจะเก็บเพียงตัวชี้ไปยังโหนดลูกสองตัวเท่านั้น ทำให้ต้นไม้แพะรับบาปง่ายต่อการใช้งาน และเนื่องจากการจัดเรียงโครงสร้างข้อมูลจึงสามารถลดค่าใช้จ่ายของโหนดได้มากถึงหนึ่งในสาม ${\displaystyle O(\log n)}$

แทนที่จะใช้วิธีการปรับสมดุลทีละน้อยแบบที่อัลกอริทึมต้นไม้สมดุลส่วนใหญ่ใช้ ต้นไม้แพะรับบาปจะเลือก "แพะรับบาป" เป็นครั้งคราวแต่มีค่าใช้จ่ายสูง และสร้างต้นไม้ย่อยที่รากอยู่ที่แพะรับบาปนั้นขึ้นมาใหม่ทั้งหมดให้กลายเป็นต้นไม้ไบนารีที่สมบูรณ์ ดังนั้น ต้นไม้แพะรับบาปจึงมีประสิทธิภาพในการอัปเดตในกรณีที่เลวร้ายที่สุด ${\displaystyle O(n)}$

กล่าวได้ว่าต้นไม้ค้นหาแบบไบนารี (Binary Search Tree) มีความสมดุลของน้ำหนัก (weight-balanced) หากครึ่งหนึ่งของโหนดอยู่ทางด้านซ้ายของโหนดราก และอีกครึ่งหนึ่งอยู่ทางด้านขวา โหนดที่มีความสมดุลของน้ำหนักแบบ α (α-weight-balanced node) ถูกกำหนดให้เป็นโหนดที่ตรงตามเกณฑ์ความสมดุลของน้ำหนักแบบผ่อนปรน:

ขนาด (ซ้าย) ≤ α*ขนาด (โหนด) ขนาด (ขวา) ≤ α*ขนาด (โหนด) 

โดยที่ขนาดสามารถกำหนดได้แบบเวียนซ้ำดังนี้:

ฟังก์ชัน size(node) ถ้า node = nil ให้คืนค่า 0 มิฉะนั้นให้คืนค่า size(node->left) + size(node->right) + 1 จบเงื่อนไขจบฟังก์ชัน

แม้แต่ต้นไม้ที่เสื่อมสภาพ (รายการเชื่อมโยง) ก็ยังตรงตามเงื่อนไขนี้หาก α=1 ในขณะที่ α=0.5 จะตรงกับต้นไม้ไบนารีที่เกือบสมบูรณ์เท่านั้น

ต้นไม้ค้นหาแบบไบนารีที่สมดุลน้ำหนัก α จะต้องสมดุลความสูง α ด้วย นั่นคือ

height(tree) ≤ floor(log 1/α (size(tree))) 

โดยหลักการผกผันต้นไม้ที่ไม่สมดุลด้านความสูง α จะไม่สมดุลด้านน้ำหนัก α ด้วย

ต้นไม้แพะรับบาปไม่รับประกันว่าจะรักษาสมดุลน้ำหนัก α ไว้ได้ตลอดเวลา แต่จะรักษาสมดุลความสูง α อย่างหลวมๆ เสมอ

height(scapegoat tree) ≤ floor(log 1/α (size(tree))) + 1. 

การละเมิดเงื่อนไขความสมดุลของความสูงนี้สามารถตรวจพบได้ในขณะทำการสอดใส่ และบ่งชี้ว่าต้องมีการละเมิดเงื่อนไขความสมดุลของน้ำหนักด้วยเช่นกัน

สิ่งนี้ทำให้ต้นไม้แพะรับบาปคล้ายกับต้นไม้แดง-ดำตรงที่ทั้งสองมีข้อจำกัดเรื่องความสูง อย่างไรก็ตาม ทั้งสองแตกต่างกันอย่างมากในวิธีการกำหนดตำแหน่งที่จะทำการหมุน (หรือในกรณีของต้นไม้แพะรับบาป คือการปรับสมดุล) ในขณะที่ต้นไม้แดง-ดำเก็บข้อมูล 'สี' เพิ่มเติมไว้ในแต่ละโหนดเพื่อกำหนดตำแหน่ง ต้นไม้แพะรับบาปจะหาแพะรับบาปที่ไม่ได้รับการปรับสมดุลน้ำหนัก α เพื่อทำการปรับสมดุล ซึ่งคล้ายคลึงกับต้นไม้ AVLในแง่ที่ว่าการหมุนจริงขึ้นอยู่กับ 'ความสมดุล' ของโหนด แต่วิธีการกำหนดความสมดุลนั้นแตกต่างกันอย่างมาก เนื่องจากต้นไม้ AVL ตรวจสอบค่าความสมดุลทุกครั้งที่มีการแทรก/ลบ จึงมักจะเก็บค่านี้ไว้ในแต่ละโหนด แต่ต้นไม้แพะรับบาปสามารถคำนวณได้เฉพาะเมื่อจำเป็นเท่านั้น ซึ่งก็คือเมื่อต้องหาแพะรับบาป

แตกต่างจากต้นไม้ค้นหาแบบปรับสมดุลอัตโนมัติอื่นๆ ส่วนใหญ่ ต้นไม้แพะรับบาปมีความยืดหยุ่นอย่างมากในเรื่องการปรับสมดุล โดยรองรับค่า α ใดๆ ก็ได้ที่ 0.5 < α < 1 ค่า α สูงจะส่งผลให้มีการปรับสมดุลน้อยลง ทำให้การแทรกข้อมูลเร็วขึ้น แต่การค้นหาและการลบข้อมูลช้าลง และในทางกลับกันสำหรับค่า α ต่ำ ดังนั้น ในการใช้งานจริง สามารถเลือกค่า α ได้ตามความถี่ที่ควรดำเนินการเหล่านี้

โครงสร้าง Lookup ไม่ได้ถูกดัดแปลงจากโครงสร้างต้นไม้ค้นหาแบบไบนารีมาตรฐาน และมีเวลาประมวลผลกรณีเลวร้ายที่สุดคือ ซึ่งแตกต่างจากโครงสร้างต้นไม้แบบ Splayที่มีเวลาประมวลผลกรณีเลวร้ายที่สุดคือการลดภาระหน่วยความจำของโหนดเมื่อเทียบกับต้นไม้ค้นหาแบบไบนารีที่ปรับสมดุลตัวเองอื่นๆ สามารถปรับปรุงการเข้าถึงข้อมูลและการแคช ให้ดียิ่งขึ้นได้${\displaystyle O(\log n)}$${\displaystyle O(n)}$

การแทรกข้อมูลนั้นใช้หลักการพื้นฐานเดียวกันกับต้นไม้ค้นหาแบบไบนารีที่ไม่สมดุลแต่มีการเปลี่ยนแปลงที่สำคัญบางประการ

เมื่อค้นหาจุดแทรก จะต้องบันทึกความลึกของโหนดใหม่ด้วย ซึ่งทำได้โดยใช้ตัวนับอย่างง่ายที่จะเพิ่มขึ้นในแต่ละรอบของการค้นหา โดยจะนับจำนวนขอบระหว่างโหนดรากและโหนดที่แทรกเข้าไป หากโหนดนี้ละเมิดคุณสมบัติความสมดุลของความสูง α (ที่กำหนดไว้ข้างต้น) จะต้องทำการปรับสมดุลใหม่

ในการปรับสมดุลใหม่ โครงสร้างย่อยทั้งหมดที่เริ่มต้นจากโหนดเป้าหมายจะได้รับการดำเนินการปรับสมดุล โหนดเป้าหมายถูกกำหนดให้เป็นบรรพบุรุษของโหนดที่แทรกเข้ามาซึ่งไม่ได้สมดุลตามน้ำหนัก α โดยจะมีบรรพบุรุษดังกล่าวอย่างน้อยหนึ่งรายเสมอ การปรับสมดุลบรรพบุรุษใดๆ เหล่านั้นจะทำให้คุณสมบัติการสมดุลตามความสูง α กลับคืนมา

วิธีหนึ่งในการหาแพะรับบาป คือ การไต่จากโหนดใหม่กลับขึ้นไปยังโหนดราก และเลือกโหนดแรกที่น้ำหนักไม่สมดุล (α-weight-balanced)

การย้อนกลับขึ้นไปยังรากนั้นต้องใช้พื้นที่จัดเก็บ ซึ่งโดยปกติจะจัดสรรไว้ในสแต็กหรือตัวชี้ไปยังพาเรนต์ แต่จริงๆ แล้วสามารถหลีกเลี่ยงปัญหานี้ได้โดยการชี้แต่ละลูกไปยังพาเรนต์ของมันขณะที่ลงไป และทำการซ่อมแซมเมื่อย้อนกลับขึ้นมา ${\displaystyle O(\log n)}$

เพื่อพิจารณาว่าโหนดที่มีศักยภาพนั้นเป็นแพะรับบาปที่เหมาะสมหรือไม่ เราจำเป็นต้องตรวจสอบคุณสมบัติการสมดุลน้ำหนัก α ของโหนดนั้น ในการทำเช่นนี้ เราสามารถย้อนกลับไปดูคำนิยามได้:

ขนาด (ซ้าย) ≤ α*ขนาด (โหนด) ขนาด (ขวา) ≤ α*ขนาด (โหนด) 

อย่างไรก็ตาม การปรับปรุงประสิทธิภาพครั้งใหญ่สามารถทำได้โดยการตระหนักว่าเรารู้ขนาดสองในสามขนาดแล้ว เหลือเพียงขนาดที่สามที่ต้องคำนวณ

ลองพิจารณาตัวอย่างต่อไปนี้เพื่อแสดงให้เห็นถึงสิ่งนี้ สมมติว่าเรากำลังปีนกลับขึ้นไปที่ราก:

ขนาด (โหนดแม่) = ขนาด (โหนดลูก) + ขนาด (โหนดพี่น้อง) + 1 

แต่ดังเช่น:

ขนาด (โหนดที่แทรก) = 1 

คดีนี้ถูกลดทอนให้เหลือเพียงประเด็นเล็กน้อยดังนี้:

ขนาด[x+1] = ขนาด[x] + ขนาด(พี่น้อง) + 1 

โดยที่ x = โหนดนี้, x + 1 = โหนดแม่ และ size(sibling) คือฟังก์ชันเดียวที่จำเป็นในการเรียกใช้จริง ๆ

เมื่อพบแพะรับบาปแล้ว ซับทรีที่มีรากอยู่ที่แพะรับบาปจะถูกสร้างขึ้นใหม่ทั้งหมดเพื่อให้สมดุลอย่างสมบูรณ์แบบ^{[ 1 ]} สามารถทำได้ในเวลาโดยการสำรวจโหนดของซับทรีเพื่อค้นหาค่าของโหนดเหล่านั้นในลำดับที่เรียงแล้ว และเลือกค่ามัธยฐานเป็นรากของซับทรีแบบเรียกซ้ำ ${\displaystyle O(n)}$

เนื่องจากการปรับสมดุลใช้เวลา (ขึ้นอยู่กับจำนวนโหนดของซับทรี) การแทรกจึงมีประสิทธิภาพในกรณีที่เลวร้ายที่สุดคือเวลา อย่างไรก็ตาม เนื่องจากสถานการณ์ที่เลวร้ายที่สุดเหล่านี้กระจายออกไป การแทรกจึงใช้เวลาโดยเฉลี่ย ${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle O(\log n)}$

ต้นไม้แพะรับบาปมีการปรับสมดุลความสูงอย่างหลวมๆ โดยมีความสูงสูงสุดไม่เกินซึ่งอยู่ในช่วง 0.5 < α < 1 ต้นทุนในการค้นหาจุดแทรกและวางโหนดนั้นถูกจำกัดด้วยความสูง ซึ่งคือหลังจากแทรกแล้ว อาจมีการปรับสมดุลใหม่ซึ่งอาจมีต้นทุนสูงถึง ต่อไปนี้เราจะแสดงให้เห็นว่าต้นทุนของการปรับสมดุลนั้นถูกเฉลี่ยต่อการแทรกแต่ละครั้ง ${\displaystyle \lfloor \log _{1/\alpha }n\rfloor }$${\displaystyle O(\log n)}$${\displaystyle O(\log n)}$${\displaystyle O(n)}$${\displaystyle O(\log n)}$

กำหนดให้ความไม่สมดุลของโหนดv คือค่าสัมบูรณ์ของผลต่างขนาดระหว่างโหนดซ้ายและโหนดขวา ลบด้วย 1 หรือ 0 แล้วแต่ว่าค่าใดมากกว่า กล่าวอีกนัยหนึ่งคือ:

${\displaystyle I(v)=\operatorname {max} (|\operatorname {left} (v)-\operatorname {right} (v)|-1,0)}$

นอกจากนี้ เรากำหนดความไม่สมดุลของซับทรีให้เป็นผลรวมของความไม่สมดุลของโหนดในซับทรีนั้น

บทตั้งที่ 1:ก่อนที่จะสร้างซับทรีที่รากอยู่ที่ ขึ้นใหม่ทันที( คือสัญลักษณ์บิ๊กโอเมก้า ) ${\displaystyle v}$${\displaystyle I(v)\in \โอเมก้า (|v|)}$${\displaystyle \Omega }$

การพิสูจน์:

ตามนิยามแล้ว โหนดแพะรับบาปจะไม่สมดุลน้ำหนัก α ดังนั้นซับทรีลูกจะมีขนาดอย่างน้อยและซับทรีพี่น้องจะมีขนาดอย่างมากความไม่สมดุลของโหนดจึงเป็นและเนื่องจากเป็นค่าคงที่ที่กำหนดไว้ดังนั้น ความไม่สมดุลของซับทรีที่รากอยู่ที่จึงเป็น เช่นกัน ${\displaystyle \alpha ||}$${\displaystyle (1-\alpha )|v|}$${\displaystyle v}$${\displaystyle I(v)\geq |\alpha |v|-(1-\alpha )|v||-1=|2\alpha -1||v|-1}$${\displaystyle \alpha >0.5}$${\displaystyle I(V)=\โอเมก้า (|V|)}$${\displaystyle v}$${\displaystyle \Omega (|V|)}$

บทพิสูจน์ย่อยที่ 2:ทันทีหลังจากสร้างซับทรีขึ้นใหม่โดยมีรากอยู่ที่, . ${\displaystyle v}$${\displaystyle I(v)=0}$

การพิสูจน์:

ต้นไม้ที่สร้างขึ้นใหม่มีความสมดุลอย่างสมบูรณ์ โดยที่ขนาดของต้นไม้ย่อยที่รากอยู่ที่ระดับเดียวกันจะแตกต่างกันไม่เกิน 1 ตามคำจำกัดความของความไม่สมดุลข้างต้น ความไม่สมดุลของโหนดทั้งหมดในต้นไม้ย่อยจึงเป็น 0

ทฤษฎีบทที่ 3:ต้นทุนการติดตั้งโดยเฉลี่ยคือ. ${\displaystyle O(\log n)}$

การพิสูจน์:

เนื่องจากการสร้างใหม่ใดๆ จะลดลงตามบทพิสูจน์เสริมข้อที่ 1 และ 2 ต้นทุนในการซ่อมแซมความไม่สมดุลแต่ละหน่วยจึงลดลง ${\displaystyle O(|v|)}$${\displaystyle I(v)}$${\displaystyle \โอเมก้า (|v|)-0=\โอเมก้า (|v|)}$

${\displaystyle {O(|v|) \over \Omega (|v|)}=O(1)}$.

การแทรกโหนดแต่ละครั้งจะทำให้เกิดความไม่สมดุลได้มากที่สุด 1 หน่วยในทุกซับทรีที่โหนดนั้นมีอยู่ โหนดที่แทรกเข้าไปสามารถอยู่ในซับทรีได้มากที่สุด 1 ซับทรีต่อระดับของต้นไม้เท่านั้น ซึ่งหมายความว่าจำนวนซับทรีที่รวมโหนดนั้นอยู่จะถูกจำกัดด้วยความสูงของต้นไม้ ซึ่งก็คือเนื่องจากความไม่สมดุลแต่ละหน่วยมีค่าใช้จ่ายในการแก้ไข ส่งผลให้ค่าใช้จ่ายเฉลี่ยในการปรับสมดุลต่อการแทรกโหนดแต่ละครั้งคือ ${\displaystyle O(\log n)}$${\displaystyle O(1)}$

${\displaystyle O(\log n)O(1)=O(\log n)}$.

เมื่อรวมต้นทุนของขั้นตอนการค้นหาเบื้องต้นและการปรับสมดุลแล้ว ต้นทุนการแทรกโดยเฉลี่ยจึงเป็นดังนี้

${\displaystyle O(\log n)+O(\log n)=O(\log n)}$.

ขอบเขตนี้ใช้ได้กับค่า 0.5 < α < 1 ทั้งหมด

ต้นไม้แพะรับบาปมีความพิเศษตรงที่การลบทำได้ง่ายกว่าการแทรก เพื่อให้สามารถลบได้ ต้นไม้แพะรับบาปจำเป็นต้องจัดเก็บค่าเพิ่มเติมไว้ในโครงสร้างข้อมูลของต้นไม้ คุณสมบัตินี้ ซึ่งเราจะเรียกว่า MaxNodeCount นั้นแสดงถึงจำนวนโหนดสูงสุดที่ได้รับ โดยจะถูกตั้งค่าเป็น NodeCount ทุกครั้งที่ต้นไม้ทั้งหมดได้รับการปรับสมดุล และหลังจากแทรกแล้วจะถูกตั้งค่าเป็น max(MaxNodeCount, NodeCount)

ในการลบโหนด เราเพียงแค่ลบโหนดออกเหมือนกับการลบโหนดในต้นไม้ค้นหาแบบไบนารีทั่วไป แต่ถ้า...

จำนวนโหนด ≤ α*จำนวนโหนดสูงสุด 

จากนั้นเราจะปรับสมดุลโครงสร้างต้นไม้ทั้งหมดรอบโหนดราก โดยอย่าลืมตั้งค่า MaxNodeCount ให้เท่ากับ NodeCount

วิธีนี้ทำให้การลบมีประสิทธิภาพในกรณีที่เลวร้ายที่สุดคือเวลา ในขณะที่เวลาเฉลี่ยคือ ${\displaystyle O(n)}$${\displaystyle O(\log n)}$

สมมติว่าต้นไม้แพะรับบาปมีองค์ประกอบและเพิ่งถูกสร้างขึ้นใหม่ (กล่าวคือ เป็นต้นไม้ไบนารีสมบูรณ์) สามารถทำการลบได้มากที่สุดก่อนที่จะต้องสร้างต้นไม้ใหม่ การลบแต่ละครั้งใช้เวลา (เวลาที่ใช้ในการค้นหาองค์ประกอบและทำเครื่องหมายว่าถูกลบ) การลบทำให้ต้นไม้ต้องถูกสร้างขึ้นใหม่และใช้ เวลา (หรือเพียง) เมื่อใช้การวิเคราะห์แบบรวม จะเห็นได้ชัดว่าต้นทุนเฉลี่ยของการลบคือ: ${\displaystyle n}$${\displaystyle n/2-1}$${\displaystyle O(\log n)}$${\displaystyle n/2}$${\displaystyle O(\log n)+O(n)}$${\displaystyle O(n)}$${\displaystyle O(\log n)}$

${\displaystyle {\sum _{1}^{n/2}O(\log n)+O(n) \over n/2}={{n \over 2}O(\log n)+O(n) \over n/2}=O(\log n)\ }$

ชื่อต้นไม้แพะรับบาป"[...] มาจากภูมิปัญญาทั่วไปที่ว่า เมื่อมีบางอย่างผิดพลาด สิ่งแรกที่ผู้คนมักจะทำคือหาคนมาตำหนิ (แพะรับบาป)" ^{[ 3 ]}ในพระคัมภีร์แพะรับบาป คือสัตว์ที่ถูก แบกรับบาปของผู้อื่นตามพิธีกรรม แล้วถูกขับไล่ออกไป

• ต้นไม้แผ่กว้าง
• ต้นไม้
• การหมุนเวียนต้นไม้
• ต้นไม้ AVL
• บี-ทรี
• ที-ทรี

• Galpern, Igal (กันยายน 1996). ว่าด้วยการปรึกษาผู้เชี่ยวชาญและการค้นหา (PDF) (วิทยานิพนธ์ปริญญาเอก). MIT .
• Morin, Pat. "บทที่ 8 - ต้นไม้แพะรับบาป" . โครงสร้างข้อมูลแบบเปิด (ในรูปแบบรหัสเทียม) (0.1G β ed.) . สืบค้นเมื่อ2017-09-16 .