อัลกอริทึมด้านล่างควรใช้ได้กับ B-Trees ที่มีจำนวนคีย์ขั้นต่ำใน node = d และ maximum = 2*d ฉันคิดว่ามันสามารถวางนัยทั่วไปสำหรับคีย์สูงสุด 2*d + 1 ได้หากทราบวิธีการเลือกค่ามัธยฐาน
อัลกอริทึมด้านล่างได้รับการออกแบบมาเพื่อลดจำนวนโหนด ไม่ใช่แค่ความสูงของต้นไม้เท่านั้น
วิธีการขึ้นอยู่กับแนวคิดในการใส่คีย์ลงใน leaf ที่ไม่เต็ม หรือถ้า leaf ทั้งหมดเต็มเพื่อใส่คีย์ไว้ใต้โหนดที่ไม่เต็มต่ำสุด
แม่นยำยิ่งขึ้น ต้นไม้ที่สร้างโดยอัลกอริธึมที่เสนอนั้นตรงตามข้อกำหนดต่อไปนี้: มีความสูงขั้นต่ำที่เป็นไปได้ มีโหนดที่ไม่เต็มจำนวนไม่เกินสองโหนดในแต่ละระดับ (เป็นสองโหนดที่ถูกต้องที่สุดเสมอ)
เนื่องจากเรารู้ว่าจำนวนโหนดในระดับใด ๆ ยกเว้นรากจะเท่ากับผลรวมของหมายเลขโหนดและหมายเลขคีย์ทั้งหมดในระดับที่สูงกว่าอย่างเคร่งครัด เราสามารถพิสูจน์ได้ว่าไม่มีการจัดเรียงโหนดใหม่ที่ถูกต้องระหว่างระดับซึ่งจะลดจำนวนโหนดทั้งหมด ตัวอย่างเช่น การเพิ่มจำนวนคีย์ที่แทรกเหนือระดับใดระดับหนึ่งจะนำไปสู่การเพิ่มขึ้นของโหนดในระดับนั้น และส่งผลให้จำนวนโหนดทั้งหมดเพิ่มขึ้นด้วย แม้ว่าความพยายามที่จะลดจำนวนคีย์ที่สูงกว่าระดับที่กำหนดจะส่งผลให้จำนวนโหนดลดลงในระดับนั้น และไม่สามารถใส่คีย์ทั้งหมดในระดับนั้นได้โดยไม่เพิ่มความสูงของต้นไม้ นอกจากนี้ยังเห็นได้ชัดว่าการจัดเรียงปุ่มในระดับใดระดับหนึ่งถือเป็นระดับที่เหมาะสมที่สุด การใช้เหตุผลข้างต้นอาจสร้างการพิสูจน์ที่เป็นทางการมากขึ้นผ่านการอุปนัยทางคณิตศาสตร์ได้
แนวคิดคือการเก็บรายการตัวนับ (ขนาดรายการไม่ใหญ่เกินความสูงของต้นไม้) เพื่อติดตามจำนวนคีย์ที่เพิ่มในแต่ละระดับ เมื่อฉันได้เพิ่มคีย์ d ในบางระดับ หมายความว่าโหนดถูกเติมเต็มครึ่งหนึ่งที่สร้างขึ้นในระดับนั้น และหากมีคีย์เพียงพอที่จะเติมอีกครึ่งหนึ่งของโหนดนี้ เราควรข้ามคีย์นี้และเพิ่มรูทสำหรับระดับที่สูงกว่า ด้วยวิธีนี้ รูทจะถูกวางไว้ระหว่างครึ่งแรกของทรีย่อยก่อนหน้าและครึ่งแรกของทรีย่อยถัดไป มันจะทำให้เกิดการแตกแยก เมื่อรูทเข้ามาแทนที่และทรีย่อยสองครึ่งจะถูกแยกออกจากกัน สถานที่สำหรับกุญแจที่ข้ามจะปลอดภัยในขณะที่เราผ่านกุญแจที่ใหญ่กว่าและสามารถเติมได้ในภายหลัง
นี่คือโค้ดที่เกือบจะใช้งานได้ (หลอก) จำเป็นต้องเรียงลำดับอาร์เรย์:
PushArray(BTree bTree, int d, key[] Array)
{
List<int> counters = new List<int>{0};
//skip list will contain numbers of nodes to skip
//after filling node of some order in half
List<int> skip = new List<int>();
List<Pair<int,int>> skipList = List<Pair<int,int>>();
int i = -1;
while(true)
{
int order = 0;
while(counters[order] == d) order += 1;
for(int j = order - 1; j >= 0; j--) counters[j] = 0;
if (counters.Lenght <= order + 1) counters.Add(0);
counters[order] += 1;
if (skip.Count <= order)
skip.Add(i + 2);
if (order > 0)
skipList.Add({i,order}); //list of skipped parts that will be needed later
i += skip[order];
if (i > N) break;
bTree.Push(Array[i]);
}
//now we need to add all skipped keys in correct order
foreach(Pair<int,int> p in skipList)
{
for(int i = p.2; i > 0; i--)
PushArray(bTree, d, Array.SubArray(p.1 + skip[i - 1], skip[i] -1))
}
}
ตัวอย่าง:
นี่คือวิธีการจัดเรียงตัวเลขและคีย์ตัวนับที่สอดคล้องกันสำหรับ d = 2 ในขณะที่ส่งผ่านอาร์เรย์ครั้งแรก ฉันทำเครื่องหมายคีย์ที่กดเข้าไปใน B-Tree ระหว่างการส่งครั้งแรก (ก่อนวนซ้ำด้วยการเรียกซ้ำ) ด้วย 'o' และข้ามด้วย 'x'
24
4 9 14 19 29
0 1 2 3 5 6 7 8 10 11 12 13 15 16 17 18 20 21 22 23 25 26 27 28 30 ...
o o x x o o o x x o o o x x x x x x x x x x x x o o o x x o o ...
1 2 0 1 2 0 1 2 0 1 2 0 1 ...
0 0 1 1 1 2 2 2 0 0 0 1 1 ...
0 0 0 0 0 0 0 0 1 1 1 1 1 ...
skip[0] = 1
skip[1] = 3
skip[2] = 13
เนื่องจากเราไม่วนซ้ำผ่านคีย์ที่ข้ามไป เราจึงมีความซับซ้อนของเวลา O(n) โดยไม่ต้องเพิ่มให้กับ B-Tree และสำหรับอาร์เรย์ที่เรียงลำดับ
ในรูปแบบนี้อาจไม่ชัดเจนว่ามันทำงานอย่างไรเมื่อมีคีย์ไม่เพียงพอที่จะเติมครึ่งหลังของโหนดหลังจากข้ามบล็อก แต่เรายังสามารถหลีกเลี่ยงการข้ามคีย์ข้าม [ลำดับ] ทั้งหมดได้หากความยาวรวมของอาร์เรย์น้อยกว่า ~ i + 2 * ข้าม[สั่งซื้อ] และข้ามเพื่อข้ามคีย์ [สั่งซื้อ - 1] แทน สตริงดังกล่าวหลังจากเปลี่ยนตัวนับ แต่ก่อนที่จะเปลี่ยนตัวแปร ฉันอาจถูกเพิ่ม:
while(order > 0 && i + 2*skip[order] > N) --order;
มันจะเป็นสาเหตุที่ถูกต้องหากจำนวนคีย์ทั้งหมดในระดับปัจจุบันน้อยกว่าหรือเท่ากับ 3*d คีย์เหล่านั้นจะยังคงถูกแบ่งอย่างถูกต้องหากเพิ่มคีย์เหล่านั้นในลำดับดั้งเดิม ดังกล่าวจะนำไปสู่การจัดเรียงคีย์ที่แตกต่างกันเล็กน้อยระหว่างสองโหนดสุดท้ายในบางระดับ แต่จะไม่ฝ่าฝืนข้อกำหนดใดๆ ที่อธิบายไว้ และอาจจะทำให้พฤติกรรมเข้าใจง่ายขึ้น
อาจสมเหตุสมผลที่จะค้นหาแอนิเมชันและดูวิธีการทำงาน นี่คือลำดับที่ควรสร้างขึ้นในช่วง 0..29: 0 1 4 5 6 9 10 11 24 25 26 29 /สิ้นสุดการส่งผ่านครั้งแรก< /em>/ 2 3 7 8 14 15 16 19 20 21 12 13 17 18 22 23 27 28 
person
Lurr
schedule
03.08.2014
