CoE KKU

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

คุณสมบัติของ binary search tree คือ binary search tree ยังคงเป็น binary tree ซึ่งทุก ๆ โนด X ใด ๆ ในทรีต้องมีค่าของ keys ทั้งหมดทางทรีย่อยซ้าย (left subtree) ของมันต้องน้อยกว่าค่าของ key คือ X, และค่าทั้งหมดของ keys ทางด้านทรีย่อยขวา (right subtree) ต้องมากกว่าค่าของ key คือ X จะเห็นได้ว่าด้วยคุณสมบัติดังกล่ามมานี้ทำให้สมาชิกในทรีมีการจัดลำดับในโครงสร้างทรีขึ้น รูปที่ 4.15 แสดง binary tree ที่มีทรีรูปด้านซ้ายเป็น binary search tree แต่รูปด้านขวาไม่เป็นเนื่องจากโนดที่มีค่า 7 ไปอยู่ตำแหน่งที่เป็นทรีย่อยซ้ายของโนดที่มีค่า 6 (ซึ่งก็คือโนดราก)

เนื่องจากว่าเรากำหนดนิยามทรีในแบบ recursive จึงมักจะเขียนฟังก์ชันการทำงานของทรีเป็นแบบ recursive ด้วย เนื่องจากว่าความลึกเฉลี่ยของ binary search tree เป็น $O(log\ N)$ ดังนั้นจึงไม่ต้องกังวลกับเรื่องที่จะเกิด stack overflow

ข้อมูลทั้งหมดในโครงสร้างของ binary search tree จะต้องสามารถจัดเรียงลำดับได้ ดังนั้นจะต้องเขียน generic class ที่ต้องประกอบด้วย interface ที่มีคุณสมบัติที่สามารถทำสิ่งนี้ได้ และในที่นี้คือ interface ชื่อ Comparable โดยจะเปรียบเทียบข้อมูล 2 หน่วยข้อมูลในทรีด้วยฟังก์ชัน CompareTo โดยจะให้ค่าเป็นลบหรือค่า 0 หรือค่าบวกขึ้นอยู่กับว่าค่าของออปเจ็กต์ Comparable นั้นจะน้อยกว่าหรือเท่ากับหรือมากกว่าค่าของออปเจ็กต์ที่เป็นพารามิเตอร์ของฟังก์ชันถ้าข้อมูลมีค่าเท่ากัน รูปที่ 4.16 แสดงคลาสของโนดใน binary search tree

รูปที่ 4.17 แสดงโครงร่างของคลาส BinarySearchTree มี data member ตัวเดียวที่ใช้สำหรับอ้างถึงโนดรากของทรีเท่านั้นและจะมีค่า (หรืออ้างถึง) ค่า null กรณีที่ทรีเป็นทรีว่าง วิธีที่ใช้ทั่วไปคือจะใช้ public method ในการเรียกใช้งาน private method ที่เป็นแบบ recursive อีกชั้นหนึ่ง private method ชื่อ elementAt ให้ค่ากลับเป็น (ตัวอ้างอิงถึง) หน่วยข้อมูลที่เก็บอยู่ในโนดที่อ้างอิงโดย t หรือก็จะเป็น null ถ้า t เป็น null

class BinaryNode 
{
  	// Constructors
    BinaryNode( Comparable theElement )
    {	this( theElement, null, null );	}
    BinaryNode( Comparable theElement, BinaryNode lt, BinaryNode rt )
    {   element = theElement; left = lt; right = rt;}
 
    // Friendly data; accessible by other package routines
 
    Comparable element;     	// The data in the node
    BinaryNode left;         	// Left child
    BinaryNode right;        	// Right child
}

รูปที่ 4.16 คลาส BinaryNode

public class BinarySearchTree 
 {
    public BinarySearchTree( )   { root = null; }
    public void insert( Comparable x )   { root = insert( x, root ); }
    public void remove( Comparable x ) { root = remove( x, root ); }
    public Comparable findMin( )  { return elementAt( findMin( root ) );}
    public Comparable findMax( ) { return elementAt( findMax( root ) );}
    public Comparable find( Comparable x )  { return elementAt( find( x, root ) );}
    public void makeEmpty( )  { root = null; }
    public boolean isEmpty( )  { return root == null; }
    public void printTree( )  {/* Figure 4.56 */}
 
    private BinaryNode root;  	// The tree root 
 
    private Comparable elementAt( BinaryNode t )  	{ return t == null ? null : t.element; }
    private BinaryNode find( Comparable x, BinaryNode t ) 		{/* Figure 4.18 */}
    private BinaryNode findMin( BinaryNode t )  {/* Figure 4.19 */}
    private BinaryNode findMax( BinaryNode t ) {/* Figure 4.20 */}
    private BinaryNode insert( Comparable x, BinaryNode t )  {/* Figure 4.22 */ }
    private BinaryNode remove( Comparable x, BinaryNode t )  {/* Figure 4.25 */ }
    private void printTree( BinaryNode t )  {/* Figure 4.56 */}
}

รูปที่ 4.17 โครงร่างคลาส BinarySearchTree

การทำงานของ find() ให้ค่ากลับเป็น reference ที่อ้างถึงโนดในทรี T ที่มีหน่วยข้อมูล X, หรือ null ถ้าไม่มีโนดดังกล่าว ถ้า T เป็นทรีว่างก็ให้ค่ากลับเป็น null ถ้าหน่วยข้อมูลที่อยู่ที่ T คือ X ก็ให้ค่ากลับเป็น T ถ้าไม่เป็นดังที่กล่าวมานี้ ก็ให้เรียกใช้ method นี้ในแบบ recursive ที่กระทำต่อทรีย่อยของ T, อาจจะเป็นทรีย่อยซ้ายหรือขวาขึ้นอยู่กับค่า X เมื่อเทียบกับค่าที่อยู่ใน T รูปที่ 4.18 เป็นคำสั่งที่ใช้ตามวิธีที่กล่าวมาข้างบนนี้

จะเห็นว่าลำดับของการตรวจสอบในโปรแกรมนี้มีความสำคัญกล่าวคือจะต้องทดสอบความเป็นทรีว่างเสียก่อนมิฉะนั้นแล้วก็จะเกิดภาวะที่จะเข้าถึงหน่วยข้อมูลที่อ้างอิงที่ null ซึ่งจะเกิด exception (ในกรณีนี้คือ NullPointerEception) อีกประการหนึ่งคือ recursive ที่ใช้ในโปรแกรมนี้เป็นแบบที่เรียกว่า tail recursions ซึ่งความจริงแล้วสามารถใช้คำสั่งลูปของ while แทนได้

/** * Internal method to find an item in a subtree.
    * x is item to search for. t the node that roots the tree.
    * @return node containing the matched item.      */
 
private BinaryNode find( Comparable x, BinaryNode t )
{
    if( t == null )   
        return null;
    if( x.compareTo( t.element ) < 0 )
	    return find( x, t.left );
    else if( x.compareTo( t.element ) > 0 )
        return find( x, t.right );
    else
        return t;    // Match
} 

รูปที่ 4.18 Find operation

ฟังก์ชันนี้ให้ค่ากลับเป็น reference ที่อ้างถึงโนดที่บรรจุค่าที่น้อยที่สุดและมากที่สุดตามลำดับ ฟังก์ชัน findMin เริ่มต้นทำงานที่ตำแหน่งของโนดรากของทรีแล้ว traverse ลงไปด้านซ้ายเรื่อย ๆ ตราบเท่าที่ยังมี left child และจะสิ้นสุดลงที่ค่าที่น้อยที่สุด ส่วนฟังก์ชัน findMax ก็จะทำงานในลักษณะเดียวกันกับฟังก์ชัน findMin เพียงแต่จะทำการท่องลงไปด้าน right child เท่านั้น โปรแกรมของฟังก์ชัน findMin เขียนแบบ recursive และของฟังก์ชัน findMax ไม่เป็นแบบ recursive ดังรูปที่ 4.19 และรูปที่ 4.20 ตามลำดับ

/* Internal method to find the smallest item in a subtree.
 * @param t the node that roots the tree.
 * @return node containing the smallest item. */
 
private BinaryNode findMin( BinaryNode t )
{
    if ( t == null )
        return null;
    else if ( t.left == null )
        return t;
    return findMin ( t.left );
} 

รูปที่ 4.19 ฟังก์ชัน findMin

/* Internal method to find the largest item in a subtree.
 * @param t the node that roots the tree.
 * @return node containing the largest item. */
 
private BinaryNode findMax( BinaryNode t )
{
    if( t != null )
        while( t.right != null )
            t = t.right;
        return t;
}

รูปที่ 4.20 ฟังก์ชัน findMax

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

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

รูปที่ 4.22 แสดงโปรแกรมฟังก์ชันการบรรจุ เนื่องจาก t นั้นอ้างอินอยู่ที่ตำแหน่งโนดรากของทรีและรากจะเปลี่ยนไปเมื่อมีการบรรจุครั้งแรก ดังนั้นจึงเขียนโปรแกรมฟังก์ชัน insert ที่ให้ค่ากลับเป็นการอ้างอิงที่รากของทรีใหม่ บรรทัดที่ 4 และ 6 เป็นการบรรจุและเชื่อมต่อ x เข้าในทรีในแบบ recursive

/** x the item to insert.  t the node that roots the tree.
 * @return the new root.  */
        private BinaryNode insert( Comparable x, BinaryNode t )
        {
/* 1*/      if( t == null )
/* 2*/          t = new BinaryNode( x, null, null );
/* 3*/      else if( x.compareTo( t.element ) < 0 )
/* 4*/          t.left = insert( x, t.left );
/* 5*/      else if( x.compareTo( t.element ) > 0 )
/* 6*/          t.right = insert( x, t.right );
/* 7*/      else
/* 8*/          ;  // Duplicate; do nothing
/* 9*/      return t;
        }

รูปที่ 4.22 ฟังก์ชัน insert สำหรับบรรจุค่าลงใน binary search tree

เป็นเรื่องปกติของโครงสร้างข้อมูลแบบต่าง ๆ ที่การทำงานการลบ (remove หรือ delete) เมื่อค้นหาโนดที่ต้องการลบแล้วจะต้องพิจารณาสิ่งที่อาจจะมีประเด็นที่ต้องพิจารณาหลายอย่างด้วยกัน ดังนี้

ถ้าโนดนั้นเป็น leaf ก็ลบออกได้ทันที ถ้าโนดนั้นมีโนดลูก 1 โนด ก็ทำการปรับเส้นเชื่อม (pointer) จากโนดแม่ของมันให้ข้ามโนดที่จะลบนั้นแล้วจึงทำการลบดังแสดงในรูปที่ 4.23

กรณีที่ซับซ้อนขึ้นในการลบโนดคือกรณีที่ถ้าโนดที่จะลบนั้นมีโนดลูก 2 โนด วิธีการทั่วไป คือ ให้แทนที่ค่าของโนดที่ลบนั้นด้วยค่าที่น้อยที่สุดของ right subtree (ซึ่งสามารถค้นหาพบได้โดยง่าย) และให้ทำการ delete โนดนั้นในแบบ recursive เนื่องจากโนดที่มีค่าน้อยที่สุดใน right subtree ย่อมไม่มี left child ดังนั้น การ remove ครั้งหลังจึงทำได้ง่าย

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

private BinaryNode remove( Comparable x, BinaryNode t )
        {
            if( t == null )
                return t;   // Item not found; do nothing
            if( x.compareTo( t.element ) < 0 )
                t.left = remove( x, t.left );
            else if( x.compareTo( t.element ) > 0 )
                t.right = remove( x, t.right );
            else if( t.left != null && t.right != null ) // Two children
            {
                t.element = findMin( t.right ).element;
                t.right = remove( t.element, t.right );
            }
            else
                t = ( t.left != null ) ? t.left : t.right;
            return t;
        }

รูปที่ 4.25 Deletion routine

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

เราคาดหวังว่าการทำงานทั้งหมดที่ได้กล่าวถึงมาแล้วในหัวข้อก่อนหน้านี้จะใช้เวลาเป็น $O(log\ N)$ เนื่องจากเราใช้เวลาคงที่ในการเคลื่อนที่ลงในทรีแต่ละระดับ ความจริงแล้ว running time ของการทำงานที่กล่าวมาแล้วนั้น คือ $O(d)$, เมื่อ $d$ คือ depth ของโนดที่มีข้อมูลที่จะประมวลผล

ในหัวข้อนี้จะได้แสดงให้เห็นว่าค่าความลึกเฉลี่ย (average depth) ของโนดทั้งหมดใน tree คือ $O(log\ N)$ โดยมีสมมุติฐานว่าทุกลำดับการบรรจุโนดลงในทรีมีโอกาสเกิดขึ้นได้เท่า ๆ กันทุกรูปแบบของลำดับที่เป็นไปได้ ผลบวกของความลึกของโนดทุกโนดใน tree เรียกว่า internal path length เราจะคำนวณหาค่าเฉลี่ยของ internal path length ของ binary search tree โดยใช้ความเป็นไปได้ทั้งหมดของลำดับการบรรจุโนดลง binary search trees

ให้ $D(N)$ เป็น internal path length ของ tree T ใด ๆ ที่มีจำนวนโนดทั้งสิ้น $N$ โนด ซึ่ง $D(1) = 0$ และทรีที่มี N-node ประกอบด้วยโนดในทรีย่อยซ้ายจำนวน $i$ โนด และดังนั้นก็จะมีโนดในทรีย่อยขวาจำนวน $(N - i - 1)$ โนดรวมกับโนดที่รากที่ความลึกเป็นศูนย์ สำหรับ $0 < i < N$ ดังนั้น $D(i)$ จึงเป็นค่า internal path length ของทรีย่อยซ้ายเมื่อคิดจากโนดรากของตัวทรีย่อยเอง ถ้ามองจากทรีใหญ่เดิมเอง (main tree) แล้วโนดของทรีย่อยที่กล่าวเหล่านี้จะอยู่ในระดับลึกลงไปหนึ่งระดับ และสภาพดังที่กล่าวนี้ก็จะเป็นเช่นเดียวกันกับในทรีย่อยขวา ดังนั้น เราจะได้สมการ recurrence ดังนี้

$$D(N) = D(i) + D(N - i -1) + N -1$$

ถ้าขนาดของทรีย่อยที่เป็นไปได้มีโอกาสเกิดขึ้นได้ทุกขนาดเท่า ๆ กัน ก็หมายความว่า ค่าเฉลี่ยของทั้ง $D(i)$ และ $D(N - i -1)$ ก็คือ $(1/N) ∑_{j=0}^{N-1}D(j)$ ซึ่งจะได้

$$D(N)=2/N [∑_{j=0}^{N-1} D(j)]+N-1$$

ซึ่งเมื่อแก้สมการ recurrence (ดูหัวข้อ 7.7.5 บทที่ 7) นี้ก็จะได้ค่าเฉลี่ยเป็น $D(N) = O(N\ log\ N)$ ดังนั้น ค่า expected depth ของโนดใด ๆ ก็คือ $O(log\ N)$ รูปที่ 4.26 แสดงทรีที่สร้างจากตัวเลข 500 ตัว มีค่า expected depth เป็น 9.98

อย่างไรก็ตาม ไม่ใช่ว่าจะเป็นความจริงเสียทั้งหมดที่ average running time ของการทำงานต่าง ๆ ของทรีที่กล่าวมาจะเป็น $O(log\ N)$ เสมอ ทั้งนี้เนื่องจากมีการทำงานการลบ อีกทั้งไม่แน่นอนว่าทุก ๆ binary search trees จะมีโอกาสเกิดขึ้นได้เท่า ๆ กัน โดยเฉพาะอย่างยิ่งอัลกอริทึมของการลบที่ใช้นั้นจะทำให้ทรีย่อยซ้ายมีความลึกมากขึ้นกว่าทรีย่อยขวา เนื่องจากว่าเราจะใช้โนดจากทรีย่อยขวามาแทนที่โนดที่จะทำการลบ ผลที่แน่นอนของกรรมวิธีนี้ยังไม่เป็นที่ทราบแน่ชัดเป็นแต่เพียงคำที่กล่าวในทางทฤษฎีเท่านั้น มีผู้แสดงให้เห็นว่าถ้าทำการลบและบรรจุโนดสลับกันเป็นจำนวน $\Theta(N^2)$ ครั้งแล้ว จะได้ค่า expected depth เป็น $\Theta(\sqrt N)$ หลังทำการบรรจุ/ลบแบบสุ่มเป็นจำนวน ¼ ล้านครั้งในทรีรูปที่ 4.26 ทำให้ทรีที่ได้ไม่สมดุล (ความลึกเฉลี่ย = 12.51) ดังรูปที่ 4.27

ปัญหาที่กล่าวนี้สามารถขจัดได้ด้วยการสุ่มเลือกใช้สมาชิกที่มีค่าน้อยที่สุดในทรีย่อยขวาและสมาชิกที่มีค่ามากที่สุดในทรีย่อยซ้ายเพื่อนำมาแทนค่าลงในโนดที่ถูกลบ แต่ก็ยังไม่สามารถพิสูจน์ได้ว่าการทำเช่นนี้จะทำให้ในที่สุดแล้วทรีที่ได้จะสมดุล ประเด็นสำคัญของสิ่งที่กล่าวมาก็คือการกำหนดความหมายที่แท้จริงของคำว่า “เฉลี่ย” เป็นสิ่งที่ดูยุ่งยากมากอีกทั้งยังต้องอาศัยการใช้สมมติฐานหลาย ๆ อย่างที่อาจจะเป็นหรือไม่เป็นจริงก็ได้ แต่สำหรับกรณีที่ไม่มีการทำงานการลบหรือใช้การลบแบบ lazy deletion แล้วเราสามารถสรุปได้ว่าเวลา average running time ของการทำงานที่กล่าวมาแล้วนั้นก็จะเป็น $O(log N)$

ถ้าหากว่าชุดข้อมูลของอินพุตที่จะนำมาบรรจุลงในทรีเป็นชุดข้อมูลที่มีการจัดเรียงลำดับค่ามาก่อนแล้ว ก็จะทำให้ต้องใช้เวลาการบรรจุค่าชุดข้อมูลดังกล่าวนี้เป็น quadratic time และการทำงานจะแพงมากขึ้นในการใช้ linked list เนื่องจาก tree จะมีเฉพาะโนดที่ไม่มีทรีย่อยซ้าย วิธีการหนึ่งที่ใช้ในการแก้ปัญหาดังกล่าวนี้ คือการเพิ่มเติมเงื่อนไขของโครงสร้างให้รักษาการสภาพความสมดุล (balance) ของทรีเอาไว้ตลอดเวลา คือไม่ยอมให้มีโนดใดที่อยู่ลึกเกินไป

มีอัลกอริทึมไม่มากนักที่ใช้ในการจัดการกับทรีแบบสมดุลและที่มีก็จะค่อนข้างซับซ้อนกว่าการใช้ binary search tree และใช้เวลาในการปรับปรุงค่ามากกว่า หัวข้อข้างหน้าจะได้กล่าวถึงทรีที่เรียกว่า AVL tree ซึ่งเป็นรูปแบบหนึ่งของ search tree แบบสมดุล

อีกวิธีที่จะกล่าวถึงเป็นวิธีที่ใหม่กว่า AVL เรียกว่า spray tree โครงสร้างทรีแบบนี้ไม่ได้กำหนดเรื่องความสมดุลแต่แรกและยอมให้ tree มีความลึกเท่าไรก็ได้ แต่หลังการดำเนินการใด ๆ แล้วก็จะต้องดำเนินการตามกฎการจัดโครงสร้างใหม่ที่จะทำให้การทำงานคราวต่อ ๆ มามีประสิทธิภาพมากขึ้น การทำเช่นนี้ไม่ประกันว่าการดำเนินการใด ๆ ครั้งหนึ่งจะมี time bound เป็น $O(log\ N)$ แต่การดำเนินการที่ต่อเนื่องกัน $$ ครั้ง จะใช้เวลาทั้งสิ้นเป็น $O(M\ log\ N)$ ในกรณี worst case