ความรู้เบื้องต้นเกี่ยวกับต้นไม้ในการเขียนโปรแกรม: ออกซิเจนของการเข้ารหัสที่มีประสิทธิภาพ

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

และเพื่อที่จะเพิ่มประสิทธิภาพชนิดของโปรแกรมนี้ผู้คนจำนวนมากมาร์ทการพัฒนาสิ่งแปลกบางอย่างที่เราเรียกว่าโครงสร้างข้อมูล วันนี้ฉันจะพูดถึงพื้นฐานบางอย่างเกี่ยวกับหัวข้อนี้และฉันจะพูดถึงโครงสร้างเฉพาะอย่างหนึ่งที่มักจะถูกถามในระหว่างการสัมภาษณ์การเขียนโค้ดและทำให้ทุกคนคลั่งไคล้: ต้นไม้

ฉันจะไม่ดำดิ่งลงไปในโค้ดมากนักเพียง แต่เป็นทฤษฎีว่าทุกอย่างทำงานอย่างไร มีตัวอย่างโค้ดหลายล้านตัวอย่างออนไลน์ดังนั้นลองดูทีละตัวอย่างหลังจากที่คุณเข้าใจว่าต้นไม้ทำงานอย่างไร!

โครงสร้างข้อมูลคืออะไร?

อ้างอิงจาก Wikipedia:

โครงสร้างข้อมูลคือการจัดระเบียบข้อมูลและรูปแบบการจัดเก็บที่ช่วยให้สามารถเข้าถึงและแก้ไขได้อย่างมีประสิทธิภาพ”

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

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

แต่คุณจะวัดได้อย่างไรว่าโครงสร้างข้อมูลมีประสิทธิภาพเพียงใด

คุณเคยเห็นสัญลักษณ์แปลก ๆ ที่คนใช้ออนไลน์เช่น O (n) หรือไม่? ซึ่งเรียกว่า Big O Notation และเป็นวิธีมาตรฐานในการประเมินประสิทธิภาพของโครงสร้างและอัลกอริทึม O ตัวใหญ่ที่เราใช้เป็นตัวแทนของสถานการณ์ที่เลวร้ายที่สุด: การมีบางอย่างที่เป็น O (n) (โดยnเป็นจำนวนองค์ประกอบภายใน) หมายความว่าในกรณีที่เลวร้ายที่สุดต้องใช้เวลาnซึ่งเป็นสิ่งที่ดีจริงๆ

ในวงเล็บที่เราเขียนny = x →ซึ่งเป็นเทียบเท่าของการเขียนการแสดงออก มันชั่งตามสัดส่วน แต่บางครั้งเราก็มีการแสดงออกที่แตกต่างกัน:

  • O (1)
  • O (บันทึก (n))
  • บน)
  • O (n²)
  • O (n³)
  • บน!)
  • O (e ^ n)

ยิ่งผลลัพธ์ของฟังก์ชันต่ำลงโครงสร้างก็จะยิ่งมีประสิทธิภาพมากขึ้น

มีต้นไม้หลายประเภท เราจะพูดถึง BST (Binary-Search Trees) และ AVL Trees (ต้นไม้ที่สมดุลอัตโนมัติ) ซึ่งมีคุณสมบัติที่แตกต่างกัน:

โอเคคุณพูดถึงสัญกรณ์แปลก ๆ ทั้งหมดนี้แล้ว…แล้วต้นไม้ทำงานอย่างไร?

ต้นไม้ชื่อมาจากการแสดงที่แท้จริง: มีรากใบและกิ่งก้านและมักจะแสดงในลักษณะนี้:

มีไม่กี่นิกายที่เราใช้ ได้แก่ parent และ child ซึ่งมีความสัมพันธ์เฉพาะตัว ถ้าxเป็นแม่ของปีแล้วปีเป็นลูกของx ในภาพนี้ 2 คือพาเรนต์ของ 5 จากนั้น 5 คือชายด์ของ 2 แต่ละโหนด - แต่ละตำแหน่งที่มีค่าสามารถมีพาเรนต์ได้ 1 พาเรนต์และ 2 ลูกเท่านั้น

แต่นอกเหนือจากทั้งหมดนี้ยังไม่มีรูปแบบที่เป็นไปตามดังนั้นต้นไม้นี้จึงไม่เป็นประโยชน์จริงๆ ... ดังนั้นเราควรเพิ่มกฎอีกสองสามข้อเพื่อสร้างโครงสร้างข้อมูลที่ดี

ต้นไม้ค้นหาแบบไบนารี

นั่นคือเมื่อ Binary-Search Trees เข้ามา! แทนที่จะวางโหนดลูกแบบสุ่ม แต่จะทำตามคำสั่งเฉพาะ

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

สิ่งนี้อาจทำให้รู้สึกสับสนเล็กน้อยในตอนแรก แต่เรามาเขียนโค้ดหลอกเพื่อให้ง่ายขึ้น

//This code won't compile in any language (that I know of) and only serves to demonstrate how the code would look like
def insert(Node n, int v) { if n is NULL: return createNode(v) else if n.value < v: n.right = insert(n.right, v) else: n.left = insert(n.left, v) return n}

ตอนนี้เกิดอะไรขึ้นที่นี่? ก่อนอื่นให้ตรวจสอบว่าสถานที่ที่เราอยู่ตอนนี้ว่างหรือไม่ createNodeถ้าเป็นเราจะสร้างโหนดในสถานที่ที่มีฟังก์ชั่น ถ้ามันไม่ว่างเราก็ต้องดูว่าเราควรวางโหนดของเราไว้ที่ไหน

การสาธิตนี้แสดงให้เห็นว่ามันทำงานอย่างไร:

วิธีนี้เราสามารถค้นหาค่าใด ๆ ในต้นไม้โดยไม่ต้องผ่านโหนดทั้งหมด เยี่ยมมาก!

แต่มันก็ไม่ได้เป็นไปตาม gif ด้านบนเสมอไป เกิดอะไรขึ้นถ้าเราได้รับสิ่งนี้?

ในกรณีนี้ลักษณะการทำงานของต้นไม้ทำให้คุณผ่านโหนดทั้งหมด นั่นเป็นเหตุผลที่ประสิทธิภาพกรณีที่เลวร้ายที่สุดของ BST คือ O (n) ซึ่งทำให้ช้า

การลบออกจาก BST ก็ทำได้ง่ายเช่นกัน:

  • หากโหนดไม่มีลูก→ลบโหนด
  • หากโหนดมีลูกเดียว→เชื่อมต่อโหนดแม่กับโหนดหลานและลบโหนดออก
  • หากโหนดมีลูก 2 ลูก→แทนโหนดลูกที่ใหญ่ที่สุด (ลูกขวาสุดซ้ายสุด) →ดูภาพด้านล่าง

ตอนนี้คุณรู้ทุกสิ่งที่คุณต้องการเกี่ยวกับ BST แล้ว สวยเท่เหรอ?

แต่ถ้าคุณอยากมีต้นไม้ที่มีประสิทธิภาพอยู่เสมอล่ะ? คุณจะทำอะไร?

หากคุณมีความจำเป็นต้นไม้ AVL สามารถทำเพื่อคุณได้อย่างดี ในการแลกเปลี่ยนพวกเขามีความซับซ้อนมากกว่า BST หลายล้านเท่า แต่เป็นไปตามองค์กรเดียวกันกับที่ผ่านมา

An AVL tree is a self-balancing tree that has specific operations (called rotations) that allow the tree to stay balanced . This means that each node in the tree will have a difference of height between its two child branches of maximum 1.

With this, the tree will always have a height of log(n) (n being the number of elements) and this allows you to search for elements in a really efficient way.

So now you see how good and perfect balanced trees are. But how to make them is the real question. I have mentioned the word depth before, so let’s first understand it.

Height is what allows us to understand if our tree is balanced or not. And with it we’re able to determine where the problem is and apply the balancing functions: rotations. These are really simple functions that consist of exchanging nodes between each other in order to remove the height difference, but they might look really strange at first.

There are 4 operations:

  • Rotation Left
  • Rotation Right
  • Rotation Left-Right
  • Rotation Right-Left

Wow that was strange… how do rotations work?

Rotations are strange at first, and I suggest checking out some animations of them working.

Try with your own trees on this website: //www.cs.usfca.edu/~galles/visualization/AVLtree.html

It allows you to dynamically see the rotations happening and is a great tool!

There are only four cases, so understanding them will be easy.

That’s all for now!

Trees are pretty easy to understand, and with practice you can work with them easily. Applying them in your code is a major key to make your programs a lot more efficient.

If you have any questions about something you didn’t understand, disagree with, or would like to suggest, feel free to contact me through Twitter or by email!

Email: tiago.melo.antunes [at] tecnico [dot] ulisboa [dot] pt