Why? … ทำไมโครงสร้างแบบ Tree ถึงเร็วกว่า Array กันนะ

โครงสร้างแบบ Tree (หรือเจาะจงหน่อยก็ binary tree) นั้นเป็นอะไรที่ค่อนข้างใช้ยาก แม้ว่าเราจะมี library สำเร็จมาให้เรียกใช้หรือเขียนโค้ดขึ้นเองทั้งหมดก็ตาม

งั้นถ้ามันใช้ยากแล้วมันดีกว่าโครงสร้างแบบ Array ที่เราเข้าใจมันได้ง๊ายง่ายยังไงเนี่ย

คำตอบมันอยู่ที่ จำนวนครั้งในการทำงานให้เสร็จ ของ Tree กับ Array นั่นเอง

ตัวอย่างเช่น เรามาพูดถึงความสามารถพื้นฐานอย่างนึงของ Data Structure นั่นคือการ "Search" หรือ "Find" ข้อมูลข้างในกัน

สำหรับ Array นั่นการจะหาว่าข้อมูลตัวเนี้ยอยู่ที่ไหนก็ไม่ยากเท่าไหร่

x = Array( 76, 40, 93, 84, 37, 41, 100, 20, 66, 11, 28, 52, 20, 32, 50);

find = 52

for( i=0 ; i < x.length ; i++ ){
    if( x[ i ] == find ){
        //ทำอะไรซักอย่าง ก็เจอแล้วอ่ะ
    }
}

ไม่ยากใช่มั้ย ก็คือวนลูปวิ่งหาไปทีละตัวจนกว่าจะเจอนั่นแหละ แต่ถามว่าวิธีแบบนี้ช้าไหม?

แน่นอนว่ามันช้าถ้าข้อมูลของเราซัก 10,000,000,000,000 ตัว ไอ้ for loop ของเรามันจะต้องวนกี่รอบกันล่ะ

ถ้าคิดแบบ big O ก็ตอบว่า O(n) เพราะเราจะถือว่า worst-case ของกรณีนี้คือกว่าเราจะหามันเจอก็คือตัวสุดท้ายซะแล้ว

อ่ะ ลองมาตีค่าง่ายๆ โดยไม่ต้องสนใจ big O กัน ... คิดแบบถัวเฉลี่ยเลยละกัน ตีซะว่าโอกาสที่จะเจอตัวที่เราจะหาอยู่แถวๆ กลางๆ แถวละกันนะ

n = 10,000,000,000,000 ดังนั้นเราต้องใช้จำนวนครั้งประมาณ 5,000,000,000,000 กว่าจะหามันเจอ

อืม = =" ไม่ได้ช่วยเท่าไหร่เลยนะ

งั้นลองมาดูการ Search ของ Tree แบบ Binary Tree กันบ้าง

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

เริ่มต้นค้นหาที่ root บนสุด

เราต้องการค้น หาค่า 52 ซึ่ง root ของเราตอนนี้เป็น 50 ... ตามกฎของ Binary Tree Node ทางซ้ายจะต้องมีค่าน้อยกว่าทางขวาเสมอ -> ก็คือค่า 52 ที่เราจะหาจะต้องอยู่ฝั่งขวามืออย่างแน่นอน, ตัดฝั่งซ้ายทิ้งไปเลย ไม่ต้องไปหามันแล้ว

ลงมาที่ Node ถัดไปคือ 76 ค่า52ของเรามีค่าน้อยกว่าดังนั้นเราจะวกกลับไปทาง child ด้านซ้าย

แล้วต่อๆ ไปเราก็ทำแบบนี้ไปเรื่อยๆ จนกว่าเราจะเจอข้อมูลที่เราจะหาน่ะนะ

ทีนี้ปัญหาคือมันใช้กี่ครั้งกันล่ะกว่าจะหาเจอ แล้วมันใช้จำนวนครั้งน้อยกว่า Array จริงๆ น่ะเหรอ?

สมมุติว่าจำนวนข้อมูลของเราตอนนี้มี n = 100 ตัว ถ้าเป็น Array ก็จะใช้อย่างแย่ที่สุด 100 ครั้งเลย หรือคิดแบบประมาณก็ 50 ครั้งอ่ะ

ส่วน Tree ครั้งแรกมี n = 100 ตัว แต่หลังจากการหาครั้งแรก เราตัดข้อมูลทางซ้ายทิ้งไปจนเหลือข้อมูล n = 50

ห๊ะ O_O ข้อมูลหายไปครึ่งนึงเลยนะ!

ใช่แล้ว และครั้งต่อๆ ไปก็จะลดลงไปอีกครี่งๆๆๆ ไปเรื่อยๆๆๆ

เราเริ่มต้นที่ n ตัว ในครั้งต่อไปมันจะเหลือ n/2 กว่าจะเหลือ n = 1 ตัว ถือซะว่าใช้ไป X ครั้งละกัน

เมื่อแต่ละรอบโดยหารออกไปทีละครี่ง นั่นหมายถึงว่าเราจะใช้ 2^x จะได้ประมาณ n ตัว ค่อยๆ คิดตามนะ ดูรูปข้างบนประกอบไปด้วย

เมื่อ X มันเป็นเลขชี้กำลังอยู่ เราอยากจะหาค่า X เราก็ดึง X ลงมาแล้วย้าย 2 ไปเป็นฐานของอีกฝั่งนึง (อันนี้เป็นกฎของ log นะ) สรุปเราจะได้ x = log2(n)

ลองเอาไปเปรียบเทียบกับการหาแบบ Array ดูหน่อยซิ

n = 10,000,000,000,000

Array ซัดไป 10,000,000,000,000 ในกรณีที่แย่ที่สุด ถ้าถัวเฉลี่ยด็ดีขึ้นมาเล็กน้อย ที่ 5,000,000,000,000 ครั้ง

ส่วน Tree ใช้แค่ log2(10,000,000,000,000) ซึ่งจะมีค่าประมาณ 43.1850652335 ... อย่างมากแค่ 44 ครั้งเองนะ ย้ำ! 44 แถมนี่เป็นกรณีที่แย่ที่สุดด้วยแล้วนะ

เหตุผลคือการหาแบบ Tree จะตัดชุดข้อมูลที่ไม่ต้องหาแล้วออกไปได้ครั้งนึงก็ครี่งหนึ่งแล้ว ทำให้เราหาได้เร็วมาก

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