DTS 10-16/09/2552

Sorting

การเรียงลำดับ (sorting) เป็นการจัดให้เป็นระเบียบ
มีแบบแผน ช่วยให้การค้นหาสิ่งของหรือข้อมูล ซึ่งจะสามารถ
กระทำได้รวดเร็วและมีประสิทธิภาพ เช่น การค้นหา
ความหมายของคำในพจนานุกรม ทำได้ค่อนข้างง่ายและ
รวดเร็วเนื่องจากมีการเรียงลำดับคำตามตัวอักษรไว้อย่างมี
ระบบและเป็นระเบียบ หรือ การค้นหาหมายเลขโทรศัพท์ใน
สมุดโทรศัพท์ ซึ่งมีการเรียงลำดับ ตามชื่อและชื่อสกุลของ
เจ้าของโทรศัพท์ไว้ ทำให้สามารถค้นหา หมายเลข
โทรศัพท์ของคนที่ต้องการได้อย่างรวดเร็ว เป็นต้น
วิธีการเรียงลำดับสามารถแบ่งออกเป็น
2 ประเภท คือ

(1)การเรียงลำดับแบบภายใน (internal sorting)
เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ใน
หน่วยความจำหลัก เวลาที่ใช้ในการเรียงลำดับจะ
คำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อน
ข้อมูลภายในความจำหลัก

(2) การเรียงลำดับแบบภายนอก
(external sorting) เป็นการเรียงลำดับข้อมูลที่
เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการ
เรียงลำดับข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ใน
การเรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่าง
การถ่ายเทข้อมูลจากหน่วยความจำหลักและ
หน่วยความจำสำรองนอกเหนือจากเวลาที่ใช้
ในการเรียงลำดับข้อมูลแบบภายใน

การเรียงลำดับแบบเลือก (selection sort)

การเรียงลำดับแบบฟอง (Bubble Sort)
เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลใน
ตำแหน่งที่อยู่ติดกัน

การเรียงลำดับแบบเร็ว (quick sort)
เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะ
สำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็ว
ในการทำงาน วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูล
ขึ้นมาหนึ่งค่าเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้อง
ให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูกต้องแล้ว ใช้
ค่าหลักนี้เป็นหลักในการแบ่งข้อมูลออกเป็นสองส่วน
ถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่
ในตอนหน้าข้อมูล ทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่
เป็นตัวแบ่งส่วน

การเรียงลำดับแบบแทรก (insertion sort)
เป็นวิธีการเรียงลำดับที่ทำการเพิ่มสมาชิกใหม่เข้าไปใน
เซต ที่มีสมาชิกทุกตัวเรียงลำดับอยู่แล้ว และทำให้เซตใหม่
ที่ได้นี้มีสมาชิกทุกตัวเรียงลำดับด้วย

การเรียงลำดับแบบฐาน (radix sort)
เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละ
หลัก

DTS-09-02/09/2552

Graph

กราฟ (Graph) เป็นโครงสร้างข้อมูล
แบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็น
โครงสร้างข้อมูลที่มีการนำไปใช้ในงาน
ที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน
เช่น การวางข่าย งานคอมพิวเตอร์

กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น
ที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์
(Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด
ถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่า
กราฟแบบไม่มีทิศทาง (Undirected Graphs)
และถ้ากราฟนั้นมีเอ็จที่มีลำดับ
ความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟ
นั้นว่า กราฟแบบมีทิศทาง
(Directed Graphs)
บางครั้งเรียกว่า ไดกราฟ (Digraph)
ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถ
เขียนชื่อเอ็จกำกับไว้ก็ได้
การเขียนกราฟแสดงโหนดและเส้นเชื่อม
ความสัมพันธ์ ระหว่างโหนดไม่มีรูปแบบที่ตายตัว
การลากเส้นความสัมพันธ์เป็นเส้นลักษณะไหนก็
ได้ที่สามารถแสดงความสัมพันธ์ระหว่างโหนด
ได้ถูกต้อง นอกจากนี้เอ็จจากโหนดใด ๆ สามารถ
วนเข้าหาตัวมันเองได้

กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัด
ของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนด
หรือเอ็จเลยเป็นกราฟว่าง (Empty Graph)
แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือ
เชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการ
เชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็น
โหนดแรก (First Node) หรือไม่มีโหนด
เริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด

กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนด
และเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็น
กราฟว่าง (Empty Graph) แต่ละเอ็จจะเชื่อม
ระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดง
ลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น
(Source Node) และ โหนดสิ้นสุด (Target Node)
รูปแบบต่าง ๆ ของกราฟแบบมีทิศทางเหมือนกับ
รูปแบบ ของกราฟไม่มีทิศทาง ต่างกันตรงที่กราฟ
แบบนี้จะมีทิศทางกำกับด้วยเท่านั้น

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

กราฟที่มีการเปลี่ยนแปลงตลอดเวลา
อาจจะใช้วิธีแอดจาเซนซีลิสต์
(Adjacency List) ซึ่งเป็นวิธีที่คล้ายวิธี
จัดเก็บกราฟด้วยการเก็บโหนดและพอยน์
เตอร์ แต่ต่างกันตรงที่ จะใช้ ลิงค์ลิสต์แทน
เพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข

การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal) คือ
กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการ
ทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับ
การท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว
แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้น
เพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำ
เครื่องหมายบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้ว
เพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไป
ในกราฟมี 2 แบบดังนี้
1. การท่องแบบกว้าง (Breadth First Traversal)
วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนด
อื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุก
โหนดในกราฟ
ผลลัพธ์จากการท่อง 1 4 6 2 3 8 5 7 9
2. การท่องแบบลึก (Depth First Traversal)
การทำงานคล้ายกับการท่องทีละระดับของทรี โดย
กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตาม
แนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น
ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่ง
สามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือน
โหนดอื่น ๆ ต่อไปจนครบทุกโหนด

DTS-08-26/08/2552

ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์
ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับ
ชั้น (Hierarchical Relationship)
ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงาน
ต่าง ๆ อย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดง
ความสัมพันธ์ระหว่างข้อมูล แต่ละโหนดจะมีความสัมพันธ์กับโหนดใน
ระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆ โหนด
เรียกโหนดดังกล่าวว่า โหนดแม่ (Parent or
Mother Node)
โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับ
เรียกว่า โหนดลูก (Child or Son Node)
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่
เรียกว่า โหนดราก (Root Node) โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน
เรียกว่า โหนดพี่น้อง (Siblings)
โหนดที่ไม่มีโหนดลูก เรียกว่า
โหนดใบ (Leave Node)
เส้นเชื่อมแสดงความสัมพันธ์ระหว่าง
โหนดสองโหนด
เรียกว่า กิ่ง (Branch)

นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มี
วงจรปิด (loop) ในโครงสร้าง โหนดสองโหนด
ใด ๆ ในทรีต้องมีทางติดต่อกัน
ทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่ง
ทั้งหมด N-1 เส้น
การเขียนรูปแบบทรี อาจเขียนได้ 4

2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรีประกอบด้วยสมาชิกที่เรียกว่า
โหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่า
นัลทรี (Null Tree) และถ้ามีโหนด
หนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็น
ทรีย่อย (Sub Tree)
T1, T2, T3,…,Tk โดยที่ k>=0 และทรีย่อย
ต้องมีคุณสมบัติเป็นทรี

นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest)
หมายถึง กลุ่มของทรีที่เกิดจากการ
เอาโหนดรากของทรีออก
หรือ เซตของทรีที่แยกจากกัน
(Disjoint Trees)

2. ทรีที่มีแบบแผน (Ordered Tree)
หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมี
ความสัมพันธ์ที่แน่นอน เช่น ไปทางขวา
ไปทางซ้าย เป็นต้น

3. ทรีคล้าย (Similar Tree) คือ
ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มี
รูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึง
ข้อมูลที่อยู่ในแต่ละโหนด

4. ทรีเหมือน (Equivalent Tree) คือ
ทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่
คล้ายกันและแต่ละโหนดในตำแหน่ง
เดียวกันมีข้อมูลเหมือนกัน

5. กำลัง (Degree) หมายถึง
จำนวนทรีย่อยของโหนด นั้น ๆ

6. ระดับของโหนด (Level of Node) คือ
ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนด
ราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่ระดับ 1
และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1
หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุด
จากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1
และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่าง
จากโหนดราก เรียกว่า ความสูง (Height) หรือความ
ลึก (Depth)


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


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


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


2. แทนทรีด้วยไบนารีทรี
เป็นวิธีแก้ปัญหาเพื่อลดการ สิ้นเปลืองเนื้อที่ในหน่วยความจำก็คือ
กำหนดลิงค์ฟิลด์ให้มีจำนวนน้อยที่สุดเท่าที่จำเป็นเท่านั้น
โดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์
-ลิงค์ฟิลด์แรกเก็บที่อยู่ของโหนดลูกคนโต
-ลิงค์ฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไป
โหนดใดไม่มีโหนดลูกหรือไม่มีโหนดพี่น้องให้ค่าพอยน์เตอร์ใน
ลิงค์ฟิลด์มีค่าเป็น Null


โครงสร้างทรีที่แต่ละโหนดมีลิงค์ฟิลด์
แค่สองลิงค์ฟิลด์ ซึ่งช่วยให้ประหยัดเนื้อที่ใน
การจัดเก็บได้มาก เรียกโครงสร้างทรี
ที่แต่ละโหนดมีจำนวนโหนดลูกไม่เกินสอง
หรือแต่ละโหนดมีจำนวน
ทรีย่อยไม่เกินสองนี้ว่า ไบนารีทรี (Binary Tree)


ไบนารีทรีที่ทุก ๆ โหนดมีทรีย่อยทางซ้ายและ
ทรีย่อยทางขวา ยกเว้นโหนดใบ และโหนดใบทุกโหนด
จะต้องอยู่ที่ระดับเดียวกัน
เรียกว่า ไบนารีทรีแบบสมบูรณ์ (complete binary tree)
สามารถคำนวณจำนวนโหนดทั้งหมดใน
ไบนารีทรีแบบสมบูรณ์ได้
ถ้ากำหนดให้ L คือระดับของโหนดใด ๆ และ
N คือจำนวนโหนดทั้งหมดในทรีจะได้ว่า
ระดับ 1 มีจำนวนโหนด 1 โหนด
ระดับ 2 มีจำนวนโหนด 3 โหนด
ระดับ 3 มีจำนวนโหนด 7 โหนด


การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็น
ไบนารีทรี มีลำดับขั้นตอนการแปลง ดังต่อไปนี้
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบ
ความสัมพันธ์ ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา


การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญในไบนารีทรี คือ การท่องไปใน
ไบนารีทรี (Traversing Binary Tree) เพื่อเข้าไปเยือนทุก ๆ
โหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบ
แผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้ง
วิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับ
ขั้นตอนการเยือนอย่างไร โหนดที่ถูกเยือน
อาจเป็นโหนดแม่ (แทนด้วย N)
ทรีย่อยทางซ้าย (แทนด้วย L)
หรือทรีย่อยทางขวา (แทนด้วย R)


มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR
LNR LRN NRL RNL และ RLN แต่
วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้
กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรก
เท่านั้นคือ NLR LNR และ LRN ซึ่งลักษณะ
การนิยามเป็นนิยามแบบ รีเคอร์ซีฟ
(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละ
แบบมีดังนี้


1. การท่องไปแบบพรีออร์เดอร์
(Preorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี
NLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์


2.การท่องไปแบบอินออร์เดอร์
(Inorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LNR
มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์


3. การท่องไปแบบโพสออร์เดอร์
(Postorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
(3) เยือนโหนดราก


เอ็กซ์เพรสชันทรี (Expression Tree)
เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์
ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนด
เก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ
(Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรือ
อาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression)
นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอน
ในการคำนวณตามความสำคัญของเครื่องหมายด้วย
โดยมีความสำคัญตามลำดับดังนี้

- ฟังก์ชัน
- วงเล็บ
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน (unary)
- คูณ หรือ หาร
- บวก หรือ ลบ
- ถ้ามีเครื่องหมายที่ระดับเดียวกัน
ให้ทำจากซ้ายไปขวา

ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree)
เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนด
ในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุก
โหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่า
หรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวา
และในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน


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


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


(2) การดึงโหนดในไบนารีเซิร์ชทรี
หลังจากดึงโหนดที่ต้องการออกจากทรีแล้ว
ทรีนั้นต้องคงสภาพไบนารีเซิร์ชทรีเหมือน
เดิมก่อนที่จะทำการดึงโหนดใด ๆ ออกจาก
ไบนารีเซิร์ชทรี ต้องค้นหาก่อนว่าโหนดที่
ต้องการดึงออกอยู่ที่ตำแหน่งไหนภายในทรี
และต้องทราบที่อยู่ของโหนดแม่โหนดนั้นด้วย
แล้วจึงทำการดึงโหนดออกจากทรีได้ ขั้นตอน
วิธีดึงโหนดออกอาจแยกพิจารณาได้ 3

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


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


ค. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้าย
และทรีย่อยทางขวาต้องเลือกโหนดมาแทนโหนดที่ถูก
ดึงออก โดยอาจจะเลือกมาจากทรีย่อยทางซ้ายหรือ
ทรีย่อยทางขวาก็ได้
- ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรี
ย่อยทางซ้ายต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อย
ทางซ้ายนั้น
- ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมา
จากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุด
ในทรีย่อยทางขวานั้น