นี่คือโปรแกรม C++ สำหรับหาตัวเลขอันดับ i ที่ใหญ่สุด (i-th Largest) จากรายการที่กำหนด โดยใช้ Order-Statistic Algorithm
อัลกอริทึม
เริ่มต้น ฟังก์ชัน Insert() เพื่อแทรกโหนดลงในต้นไม้: อาร์กิวเมนต์: root, d ส่วนตัวของฟังก์ชัน: ถ้าต้นไม้เป็น NULL ทั้งหมด ให้แทรกโหนดใหม่เป็น root ถ้า d = tmp->data เพิ่ม count ของโหนดนั้น ถ้า d < tmp->data ย้ายพอยน์เตอร์ tmp ไปลูกซ้าย ถ้า d > tmp->data ย้ายพอยน์เตอร์ tmp ไปลูกขวา จบ เริ่มต้น ฟังก์ชัน AssignRank() เพื่อกำหนด Rank ให้แต่ละโหนดของต้นไม้: อาร์กิวเมนต์: Root ส่วนตัวของฟังก์ชัน: ถ้าลูกซ้ายของ root ไม่เป็น NULL ให้กำหนด Rank ให้ลูกซ้ายของ root เพิ่มจำนวน Rank ถ้าลูกขวาของ root ไม่เป็น NULL ให้กำหนด Rank ให้ลูกขวาของ root จบ เริ่มต้น ฟังก์ชัน Select() เพื่อค้นหาองค์ประกอบอันดับ K ที่น้อยที่สุด (Kth Smallest) จากข้อมูลในต้นไม้: อาร์กิวเมนต์: Root, ค่าที่ค้นหา k ส่วนตัวของฟังก์ชัน: ถ้าพบว่าเท่ากัน คืนค่าไป main และพิมพ์ผลลัพธ์ มิฉะนั้น ถ้ามากกว่า เลื่อนตัวแปรชั่วคราวไปลูกขวา มิฉะนั้น เลื่อนตัวแปรชั่วคราวไปลูกซ้าย จบ
ตัวอย่างโค้ด
#include<iostream> using namespace std; static int cnt = 0; struct nod //ประกาศโหนด { int data; int rank; nod *l; nod *r; }; nod* CreateNod(int d) //สร้างโหนดใหม่ { nod *newnod = new nod; newnod->data = d; newnod->rank = 0; newnod->l = NULL; newnod->r = NULL; return newnod; } nod* Insert(nod* root, int d) //แทรกข้อมูล { nod *tmp = CreateNod(d); nod *t = new nod; t = root; if(root == NULL) root = tmp; else { while(t != NULL) { if(t->data < d ) { if(t->r== NULL) { t->r = tmp; break; } t = t->r; } else if(t->data > d) { if(t->l == NULL) { t->l= tmp; break; } t = t->l; } } } return root; } void AssignRank(nod *root) //กำหนด Rank ให้โหนด { if(root->l!= NULL) AssignRank(root->l); root->rank = cnt; cnt++; if(root->r != NULL) AssignRank(root->r); } int Select(nod* root, int k) //เลือกองค์ประกอบอันดับ k ที่ใหญ่สุด { if(root->rank == k) return root->data; else if(root->rank > k) return Select(root->l, k); else return Select(root->r, k); } void display(nod *root) //แสดงต้นไม้ { if(root->l != NULL) display(root->l); cout<<"\n data: "<<root->data<<" rank: "<<root->rank; if(root->r != NULL) display(root->r); } int main() { char c; int n, i, k, a[10]={4,7,6,1,10,3,2,15,16,20}; nod *root = new nod; root = NULL; for(i = 0; i < 10; i++) root = Insert(root, a[i]); //เรียกฟังก์ชัน insert() cout<<"Enter the value of k: "; cin>>k; AssignRank(root); //เรียกฟังก์ชัน Assignrank() cout<<"\nRank associated to each node:-"; display(root); //เรียกฟังก์ชัน display() cout<<"\n\nThe kth Largest element is: "<<Select(root, 10-k); return 0; }
ผลลัพธ์
Enter the value of k: 7 Rank associated to each node:- data: 1 rank: 0 data: 2 rank: 1 data: 3 rank: 2 data: 4 rank: 3 data: 6 rank: 4 data: 7 rank: 5 data: 10 rank: 6 data: 15 rank: 7 data: 16 rank: 8 data: 20 rank: 9 The kth Largest element is: 4
