Data structures & Algorithms by Wasrek | Treaps ทรีพ Part 1

Treaps ต้นไม้มากประโยชน์

Treap คืออะไร?
Data structure ที่ได้นำ binary tree และ binary heap มารวมตัวกัน
[ tree + heap — > Treap ]
Treap เป็นทั้ง Self-balancing binary search tree และ Cartesian Tree

Definitions

Self-balancing binary search tree
เป็น BST(Binary Search Tree) ชนิดหนึ่งที่มีการปรับความสูงของ tree ให้มีความสมดุลอัตโนมัติ เช่น
AVL tree, Red-black tree และ Splay tree เป็นต้น
อ่านเพิ่มเติมได้ที่:
ต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้
GeeksforGeeks

Cartesian Tree
เป็น Tree ที่มีการเก็บค่าไว้สองค่าในแต่ละโหนดคือ
1. ค่าสำหรับ Heap property (min หรือ max ก็ได้แล้วแต่เรากำหนด)
สมมุติกรณีเป็น max heap ค่า Heap property ของโหนดพ่อจะต้องมีค่ามากกว่า Heap property ของโหนดลูก (ค่า Heap property ของ root ใน subtree ใดๆ จะต้องมีค่ามากที่สุดเสมอ)
2. ค่าสำหรับ BST — Inorder traversal
ค่าที่เราจะใช้สำหรับ BST ที่จะถูกเรียงโดยหลักการ ค่าของลูกซ้ายจะน้อยกว่าค่าของโหนดพ่อ และค่าของโหนดพ่อจะน้อยกว่าค่าของลูกขวา เมื่อเราเรียงตามหลัก BST แล้ว ลำดับของ Inorder traversal จะเป็นลำดับเลขจากน้อยไปมากเสมอ
อ่านเพิ่มเติมได้ที่:
ต้นไม้คาร์ทีเซียน
GeeksforGeeks

Treap

โครงสร้างของ Treap จะเป็น Cartesian Tree ที่
1. ค่าสำหรับ Heap property จะเป็นค่าที่ถูก random ขึ้นมา (ทำให้บางครั้ง Treap จึงอาจถูกเรียกว่า Randomized Binary Search Tree)
2. ค่าสำหรับ BST จะเป็นค่าที่เราจะใช้สำหรับการเก็บค่าในต้นไม้ของเราตามโจทย์ในแต่ละรูปแบบ มักจะเก็บเป็นค่าของ index
(หากยังไม่เข้าใจในจุดนี้ ตัวอย่างในหัวข้อด้านล่าง รวมถึง blog ของ part ถัดๆไป จะช่วยเพิ่มความเข้าใจได้)

ทำไมต้องมี Heap property?
Heap property จะมาช่วยในเรื่องของความสูงต้นไม้ เนื่องจาก BST ปกติทั่วไปนั้นมีความสูงสุดได้ถึง N ซึ่งจะทำให้ time complexity ของเราแย่มากๆ เราต้องการจะให้ความสูงของ Treap นั้นมีค่าใกล้เคียงมากที่สุดกับ logN ซึ่งเป็นค่าที่น้อยที่สุดของความสูง เพื่อให้ operations ต่างๆ สามารถทำงานได้อย่างรวดเร็วประมาณ O(log N) แทนที่จะเป็น O(N) (เพื่อให้เป็น Self Balancing Binary Search Tree)

หากเราจัดเรียงต้นไม้ตาม Heap property ซึ่งถูก random มาจะทำให้ได้ค่าของความสูงต้นไม้ใกล้เคียง log N จริงเหรอ?
มีการพิสูจน์ทางคณิตศาสตร์ว่าการ random ค่า Heap property ในลักษณะนี้นั้น มีความน่าจะเป็นสูงที่จะทำให้ได้ความสูงของต้นไม้ที่ใกล้เคียง log N
อ่านเปเปอร์: Paper-randomized binary search tree
ดูวีดีโอเพิ่มเติม: Treap Tutorial with Statistical Analysis by Stable Sort
ตั้งแต่นาทีที่ 4:25

ต้นไม้ที่ถูกเรียงตามหลักการของ Heap และ BST แต่ละชุดข้อมูลนั้น จะเป็นไปได้แบบรูปเดียวเท่านั้น Treap จะเรียงตัวได้รูปแบบเดียว
Heap property จะทำให้เรารู้ได้ว่า root ของ subtree ใดๆ คือค่าไหน เมื่อเรารู้ว่า root คือโหนดใด เราจะจัดเรียงต่อตามหลักของ BST ทำให้ค่าที่น้อยกว่าจะถูกนำไปเรียงตัวใน subtree ฝั่งซ้ายของ root และค่าที่มากกว่าจะถูกนำไปเรียงอยู่ใน subtree ฝั่งขวาของ root แล้วจึงเลือก root ของ subtree ต่อไปโดยอาศัย Heap property

ตอนนี้เราได้อะไร?
Treap เป็นต้นไม้ที่ประกอบไปด้วยค่า Heap property และค่าสำหรับ BST ซึ่งจะทำให้เราได้ Self Balancing Binary Search Tree

เอา Treap ไปทำอะไรได้?
โจทย์ที่มีการ merge, split, insert และ delete ไม่ว่าจะเป็นข้อความ string หรือชุดข้อมูล นอกจากนั้นยังมี implicit treap ที่ยังสามารถใช้แก้ปัญหาในโจทย์จำพวกเดียวกันกับที่ปกติใช้ interval tree เช่น segment tree หรือ Fenwick tree ในการแก้ รวมถึงยังสามารถใช้ lazy propagation ได้อีกด้วย (จะมีการกล่าวถึง และยกตัวอย่างใน blog part ถัดๆไป)

ตัวอย่างการเก็บ String ในรูปแบบของ Treap

เรามี string ที่เก็บคำว่า ‘gooddays’ เราต้องการจะเก็บ string นี้ในรูปแบบของ Treap เพื่อให้สามารถตัดหรือต่อ string ได้ row ของ index จะเก็บค่า index ของ char แต่ละตัวใน string โดย index จะมีค่าตั้งแต่ 1 ถึง len(string) ตัวอย่างจะมีทั้งหมด
2 ตัวอย่าง โดยตัวอย่างแรกค่า Heap property จะใช้ค่าของ Random 1 และตัวอย่างที่ 2 จะใช้ค่าของ Random 2

ตัวอย่างที่ 1

ตัวอย่างที่ 2

สังเกตได้ว่าหากเราหาลำดับ Inorder traversal ของ BST ทั้ง 2 ตัวอย่าง จะได้คำว่า ‘gooddays’ ทั้งคู่ (เรียกตัวอักษรโดยใช้ idex ที่เก็บไว้) เนื่องจากลำดับ Inorder traversal ของ BST จะเป็นเลขที่เรียงจากน้อยไปมากเสมอ เพราะฉะนั้นไม่ว่า Heap property จะถูกเรียงยังไงก็ตาม เมื่อเราทำ BST โดยใช้ค่า index แล้วนั้น ลำดับ Inorder traversal ของเรา ก็จะทำให้เราสามารถเรียกค่าตั้งแต่ index 1 ถึง N ตามลำดับที่ถูกต้องได้เสมอ

References:
Treaps : One Tree to Rule 'em all ..!! Part-1
Treaps : One Tree to Rule ’em all ..!! Part-2
Page on washington.edu (Original research)
https://cp-algorithms.com/data_structures/treap.html https://www.geeksforgeeks.org/treap-a-randomized-binary-search-tree/
https://medium.com/carpanese/a-visual-introduction-to-treap-data-structure-part-1-6196d6cc12ee
https://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture19/sld017.htm

Written By Wichada Chaiprasertsud — Wasrek
ผู้เขียน: วิชาดา ชัยประเสริฐสุด