CoE KKU

การกำหนดนิยามให้แก่ tree สามารถทำได้หลายวิธี แต่วิธีที่ดูจะเป็นธรรมชาติคือการกำหนดนิยามแบบ recursive กล่าวคือ tree เป็น collection ของโนด (nodes) ซึ่ง collection ดังกล่าวนี้อาจเป็น collection ว่าง (empty) หรือมิฉะนั้น tree ก็จะประกอบด้วยโนดพิเศษหนึ่งโนด (ให้เป็นโนด r) และเรียกโนดนี้ว่า โนดราก (root) และอาจไม่มีหรือมีทรีย่อย (subtree) ในกรณีที่ถ้ามันไม่เป็น tree ว่าง มันก็จะประกอบด้วยทรี (ซึ่งเป็นทรีย่อย) $T1, T2, . . . , Tk$, โดยที่แต่ละทรีย่อยก็จะมีรากของมันเองที่เชื่อมต่อกับ r โดยตรงด้วยตัวเชื่อมที่เรียกว่า edge

โนดรากของทรีย่อยเรียกว่าเป็น child ของ r, และ r เป็น parent ของรากแต่ละรากของทรีย่อย รูปที่ 4.1 แสดงรูปของทรีที่ได้จากนิยามแบบ recursive ที่กล่าวมานี้

เส้นทาง (path) จากโนด n1 ถึง nk กำหนดได้ด้วยลำดับของโนด $n_1, n_2, ... , n_k$ ที่ $n_i$ เป็น parent ของ $n_{i+1}$ เมื่อ $1 < i < k$ และความยาว (length) ของเส้นทาง (path) ดังกล่าวนี้คือ จำนวน edges ของเส้นทางนั้น ซึ่งเท่ากับ k – 1 ความยาว (length) ของเส้นทางจากโนดใด ๆ ไปยังตัวมันเองมีค่าเป็นศูนย์ เส้นทางจากราก (root) ไปยังโนดใด ๆ โนดหนึ่งมีเพียงเส้นทางเดียวเท่านั้น

ความลึก (depth) ของโนด ni ใด ๆ คือ ความยาวของเส้นทางจากโนดรากไปยังโนด ni นั้น ๆ ดังนั้นโนดรากจึงมีค่า depth เป็น 0 (ศูนย์) ความสูง (height) ของโนด ni ใด ๆ คือ เส้นทางที่ยาวที่สุดจากโนด ni ไปยังโนด leaf ใด ๆ ดังนั้น ทุก ๆ leaves จึงมีความสูง (height ) เป็น 0 (ศูนย์) ความสูงของทรีมีค่าเท่ากับความสูงของโนดราก

สำหรับทรีในรูปที่ 4.2, โนด E มี depth เท่ากับ 1,และมี height = 2; โนด F มี depth = 1 และมี height = 1; ค่า height ของทรี คือ 3 ค่า depth ของทรีมีค่าเท่ากับค่า depth ของโนดที่เป็น leaf ที่อยู่ลึกที่สุดซึ่งจะเท่ากับค่าของ height ของทรีเสมอ

ถ้ามีเส้นทางจากโนด n1 ไปยัง n2 เรียกว่า n1 เป็น ancestor ของโนด n2 และโนด n2 เป็น descendant ของโนด n1 ถ้าโนด n1 $\neq$ n2 ก็จะเรียกโนด n1 ว่าเป็นโนด proper ancestor ของโนด n2 และโนด n2 เป็นโนด proper descendant ของโนด n1

เนื่องจากเราไม่สามารถทราบล่วงหน้าได้ว่าโนดแต่ละโนดจะมีโนดลูกจำนวนเท่าใด ดังนั้นเราจึงไม่สามารถสร้างโครงสร้างโนดที่ประกอบด้วยค่าข้อมูลและเส้นเชื่อม (link) ไปยังโนดลูกได้ เพื่อแก้ปัญหานี้ด้วยการกำหนดให้ลูกของโนดใด ๆ โนดหนึ่งอยู่ linked list ของโนด รูปที่ 4.3 แสดงการประกาศโนดของทรี

class TreeNode 
{
  Object 	  element;
	TreeNode  firstChild;
	TreeNode  nextSibling;
};

รูปที่ 4.3 การประกาศโนดของทรี

รูปที่ 4.4 แสดงรูปแบบของโครงทรีของทรีในรูปที่ 4.2 ที่เกิดจากนิยามของทรีจากรูปที่ 4.3 ลูกศรที่ชี้ลงด้านล่างคือเส้นเชื่อม firstChild links ส่วนเส้นลูกศรในแนวนอนคือเส้นเชื่อม nextSibling links ในรูปไม่ได้แสดง null links (มีจำนวนมาก) เอาไว้ด้วย

มีการประยุกต์ใช้ทรีในงานต่าง ๆ จำนวนมาก ที่นิยมใช้กันมากอย่างหนึ่งคือในโครงสร้าง directory ในระบบปฏิบัติการของเครื่องคอมพิวเตอร์ (computer operating systems) ต่าง ๆ เช่นใน UNIX, VAX/VMS, และ DOS รูปที่ 4.5 แสดงรูปแบบทั่วไปของระบบ file ของ UNIX

โนดรากของไดเร็กทอรีคือ /usr (เครื่องหมายดอกจันที่ปรากฏที่ชื่อหมายความว่ามันเป็นไดเร็กทอรี) ใน /usr มีโนดลูก 3 โนดซึ่งล้วนแต่เป็นไดเร็กทอรีและไม่มีโนดลูกที่เป็นแฟ้มปกติ ชื่อแฟ้ม /usr/mark/book/ch1.r เข้าถึงได้หรือได้มาโดยท่องไปทางลูกตัวซ้าย 3 ครั้ง เครื่องหมาย / หมายถึง edge ของทรี

สมมติเราต้องการพิมพ์รายการชื่อแฟ้มทั้งหมดในไดเร็กทอรีโดยรูปแบบที่ต้องการ คือ แฟ้มที่อยู่ที่ระดับความลึก di จะถูกพิมพ์ให้ย่อหน้าเข้าไปด้วยระยะเว้น di ด้วย pseudocode ของอัลกอริทึมแสดงในรูปที่ 4.6 หัวใจของอัลกอริทึมคือฟังก์ชัน listAll ที่เป็นแบบ recursive ฟังก์ชัน listAll ต้องเริ่มต้นทำงานด้วยค่า depth= 0 ซึ่งจะไม่มีการย่อยหน้าสำหรับโนดราก

private	void listAll(int dept)
{
	/* 1 */	 	printName( dept );	// Print the name
	/* 2 */		if ( isDirectory() )
	/* 3 */		    for each file c in this directory
	/* 4 */		         c.listAll( dept + 1 );
}
 
public void listAll()
{
	listAll( 0 ); 	
}	

รูปที่ 4.6 pseudocode ของอัลกอริทึมแสดงรายการแฟ้มในระบบแฟ้ม

ถ้ารายการที่อ่านเป็นไดเร็กทอรีก็จะให้มีการทำงานประมวลผล children ทั้งหมดในแบบrecursive ทีละตัวเสียก่อน children เหล่านี้อยู่ลึกลงไปหนึ่งระดับดังนั้นจึงต้องมีการย่อหน้า ผลที่ได้แสดงดังรูปที่ 4.7

/usr
   mark
     book
       ch1.r
       ch2.r
       ch3.r
     courses
       cop3530
         fall88
           syl.r
         spr89
           syl.r
         sum89
           syl.r
     junk.c
   alex
     junk.c
   bill
     work
     course
       cop3212
         fall88
           grade
           prog1.r
           prog2.r
         fall89
           prog1.r
           prog2.r
           grade

รูปที่ 4.7 ผลที่ได้จากการแสดงรายการไดเร็กทอรีแบบ preorder

การท่องไป (traversal) ในทรีด้วยวิธีการแบบนี้เรียกว่า preorder traversal การท่องไปในทรีแบบนี้จะทำงานโนดนั้น ๆ ก่อนที่จะไปทำงานต่อไปที่โนดลูกของมัน จากโปรแกรมจะเห็นว่ามีการทำงานของบรรทัด 1 หนึ่งครั้งต่อหนึ่งโนด, เนื่องจากมีการส่งออก output โนดละเพียงครั้งเดียว เนื่องจากบรรทัดที่ 1 ทำงานหนึ่งครั้งต่อหนึ่งโนดดังนั้นบรรทัดที่ 2 ก็จะทำงานหนึ่งครั้งต่อโนดเช่นกัน บรรทัดที่ 4 ทำงานมากที่สุดเพียงครั้งเดียวสำหรับโนดลูกแต่ละโนดของแต่ละโนดนั้น ๆ แต่จำนวน children จะมีจำนวนน้อยกว่าจำนวนโนดอยู่ 1 สุดท้ายจะมีการทำงานในลูป 1 รอบต่อการทำงานของบรรทัดที่ 4, รวมกับการทำงานหนึ่งครั้งเมื่อจบลูป ดังนั้นงานที่ทำทั้งหมดจึงเป็นค่าคงที่สำหรับแต่ละโนด ถ้ามีชื่อแฟ้ม $N$ ชื่อที่ต้องพิมพ์รายงานออกจึงต้องใช้ running time เป็น $O(N)$

การท่องไปใน tree อีกแบบที่ใช้บ่อย คือ postorder ใน postorder traversal จะมีการทำงานที่โนดนั้น ๆ ภายหลัง (post) หลังจากการทำงานที่โนดลูกทั้งหมดของมันก่อน รูปที่ 4.8 เป็นโครงสร้างไดเร็กทอรีเดียวกับตัวอย่างก่อนหน้า แต่ได้แสดงตัวเลขจำนวน disk blocks ที่ใช้เอาไว้ในวงเล็บด้วยเท่านั้น

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

public int size()
{
/*1*/ 	int totalSize = sizeOfThisFile;
/*2*/    	if ( isDirectory() )
/*3*/       	for each file c in this directory;
/*4*/     			totalSize += c.size();
/*5*/ 	return( totalSize ); 
}

รูปที่ 4.9 pseudocode เพื่อคำนวณขนาดของบล็อก

ถ้า object ขณะนั้นไม่ใช่ไดเร็กทอรีก็ให้ค่ากลับเป็นจำนวน blocks ที่ใช้ มิฉะนั้น (ก็จะเป็น directory) ก็จะรวมจำนวนบล็อกที่ใช้โดยไดเร็กทอรีเข้ากับจำนวนบล็อก (recursively) ที่ใช้ในโนดลูกทั้งหมด รูปที่ 4.10 แสดงขนาดของไดเร็กทอรีหรือแฟ้มที่ได้จากอัลกอริทึมในรูปที่ 4.9

            ch1.r             3
            ch2.r             2
            chr.3	            4
        book	               10
                  syl.r	      1
               fall88	        2
                   syl.r	    5
                spr89	        6
                   syl.r	    2
                sum89	        3
            cop3530	         12
        course	             13
        junk.c	              6
    mark	                   30
        junk.c	              8
    alex	                    9
        work	                1
                    grades	  3
                    prog1.r	  4
                    prog2.r	  1
                fall88	      9
                    prog2.r	  2
                    prog1.r	  7
                    grades	  9
                fall89	     19
            cop3212	         29
        course	             30
    bill	                   32
/usr	                       72

รูปที่ 4.10 ขนาดของไดเร็กทอรีจากฟังก์ชัน size()