Binary Search Tree


บทความชุดนี้จะมี 4 เรื่องนั่นคือ
• Binary Search Tree หรือ BST
• AVL Tree เป็น Balanced BST พื้นฐานที่ต้องรู้
• Red Black Tree เป็น Balanced BST ที่ insert ได้รวดเร็ว
• Splay Tree เป็น Self-Adjusting BST ที่ทำงานได้ดี
Binary Search Tree เป็นพื้นฐานการเก็บข้อมูลที่สำคัญ มีหลักการคือลูกทางซ้ายจะมีค่าน้อยกว่าหรือมาก่อน คุณสมบัตินี้เป็นที่มาของคำว่า search ทำให้ operation พื้นฐานอย่าง search, insert, delete จะใช้เวลาตามความสูงของ tree ก่อนจะไปศึกษา binary search tree ขอเริ่มที่ tree และ binary tree ก่อนครับ
Tree คือ connected graph ที่ไม่มี cycle ประกอบไปด้วย node หรือ vertex และ edge ลักษณะของ tree คือ 
              b        a--b--f
  a-b-c      / \      / \
            a   c    c   d--e
   (A)       (B)      (C)
ในภาพ (A) a,b,c คือ node หรือ vertex ข้อสังเกตที่ควรรู้คือ linked list เป็น tree แบบหนึ่งเหมือนกัน
Binary tree คือ tree ที่แต่ละ node มีลูกไม่เกิน 2 ตัว เช่น 
     a
    / \
   b   c
  /   / \
 d   e   f
จากภาพ a เป็น root ของ binary tree และ มีลูกทางซ้ายคือ b ส่วนลูกทางขวาคือ c binary tree นี้มีความสูง 2 เพราะ root ของ tree มีความสูงคือ 0
Binary search tree คือ binary tree ที่มีคุณสมบัติคือ key ทางซ้ายจะน้อยกว่า parent ส่วน key ทางขวาจะมีมากกว่า parent ในปัจจุบัน binary search tree ไม่นิยมเก็บ key ที่ซ้ำกัน 
    3
   / \
  1   5
 / \   \
0   2   6
การสร้าง binary tree สร้างได้หลายวิธี เช่น ใช้ array จากช่องที่ 0 จะมีลูกทางซ้ายคือช่องที่ 1 และลูกทางขวาคือช่องที่ 2 พูดง่ายๆคือ ลูกทางซ้ายอยู่ที่ n*2+1 และ ลูกทางขวาอยู่ที่ n*2+2
จากภาพข้างบนสามารถเขียน binary tree ด้วย array ได้ดังนี้ 
key    3  1  5  0  2     6
index  0  1  2  3  4  5  6
อีกวิธีในการสร้าง binary tree คือใช้ pointer หรือ reference ถึงที่อยู่ใน memory เช่น 
struct node {
	int key;
	struct node *left, *right;
};

struct node *root = NULL;

ตัวอย่างการใส่ข้อมูลด้วยวิธี recursion เงื่อนไขพื้นฐานคือถ้า r เป็น NULL ต้องสร้าง node ขึ้นมาใหม่แล้วกำหนดค่า key ลงไป 
struct node *bst_insert(struct node *r, int key) {
	if (r == NULL) {
		r = malloc(sizeof(struct node));
		r->key = key;
		r->left = NULL;
		r->right = NULL;
		return r;
	}
	if (key < r->key) r->left  = bst_insert(r->left,  key);
	if (key > r->key) r->right = bst_insert(r->right, key);
	return r;
}
มิฉะนั้นแล้วก็ตรวจสอบ key ของ node ปัจจุบัน หรือ r->key กับ key ที่ต้องการใส่เข้าไป
• ถ้า key ใหม่น้อยกว่าใส่เข้าไปทางซ้าย
• ถ้า key ใหม่มากกว่าก็ใส่เข้าไปทางขวา ตัวอย่างการใส่ข้อมูล 3, 2, 4, 1 คือ 
    3      3      3        3
          /      / \      / \
         2      2   4    2   4
                        /
                       1
ในที่นี้จะใช้วิธีพิมพ์ tree โดยมีวงเล็บเข้ามาช่วย ตัวไหนที่ไม่มีข้อมูลจะพิมพ์เป็น ( ) แทน เช่น 
    a        b            a            b
            / \            \          /
           a   c            b        a

   (a)  ((a)(b)(c))  (( )(a)(b))  ((a)(b)( ))
ตัวอย่าง code สำหรับพิมพ์ binary tree 
void print(struct node *r) {
	if (r == NULL) {
		printf("( )");
		return;
	}
	if (r->left == NULL && r->right == NULL) {
		printf("(%d)", r->key);
		return;
	}
	printf("(");
	print(r->left );
	printf("(%d)", r->key);
	print(r->right);
	printf(")");
}
การลบข้อมูลมี 3 กรณีคือ
• 1. ตัวที่ต้องการลบไม่มีลูกเลยก็สามารถลบได้ทันที
• 2. ตัวที่ต้องการลบมีลูกตัวเดียวใช้วิธีการดึงลูกขึ้นมาแทน
• 3. ตัวที่ต้องการลบมีลูกทั้งสองด้าน copy ข้อมูลตัวน้อยที่สุดทางขวามาแทนตัวที่ต้องการลบ (หรือจะ copy ตัวมากที่สุดทางซ้ายขึ้นมาแทนก็ได้) 
   b                   b
  / \     remove c    / \        c ไม่มีลูกลบได้ทันที
 a   d               a   d
    /
   c

   b                   b
  / \     remove d    / \        d มีลูก 1 ตัว ดึงลูกขึ้นมาแทน
 a   d               a   c
    /
   c

   b                   c
  / \     remove b    / \        b มีลูก 2 ตัว หาค่าน้อยที่สุดทางขวา
 a   d               a   d       เอามาแทนที่ แล้วลบตัวนั้นออกไป
    /
   c

struct node *bst_delete(struct node *r, int key) {
	if (r == NULL) { return NULL; }
	/* case 1: no child */
	if (r->key == key && r->left == NULL && r->right == NULL) {
		free(r);
		return NULL;
	}
	/* case 2: only right child */
	if (r->key == key && r->left == NULL) {
		free(r);
		return r->right;
	}
	/* case 2: only left child */
	if (r->key == key && r->right == NULL) {
		free(r);
		return r->left;
	}
	/* case 3: both children */
	if (r->key == key && r->left != NULL && r->right != NULL) {
		int min = bst_minimum(root->right);
		r->key = min;
		r->right = bst_delete(root->right, min);
	}
	
	if (r->key >  key) {
		r->left = bst_delete(r->left, key);
	}
	if (r->key <  key) {
		r->right = bst_delete(r->right, key);
	}
	return r;
}

ในการลบข้อมูลมีการหาค่าที่น้อยที่สุดด้วย หลักการคือวิ่งไปทางซ้ายเรื่อยๆ จนไม่มีทางไป เพราะใน binary search tree ลูกทางซ้ายจะมี key น้อยกว่าทางขวา ส่วนการหาค่ามากที่สุดก็ทำตรงข้าม คือวิ่งไปทางขวา 
int bst_minimum(struct node *r) {
	if (r == NULL) return INT_MAX;
	if (r->left == NULL) return r->key;
	return bst_minimum(r->left);
}

int bst_maximum(struct node *r) {
	if (r == NULL) return -INT_MIN;
	if (r->right == NULL) return r->key;
	return bst_maximum(r->right);
}

ตัวอย่าง code ทั้งหมดของบทความนี้ 
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct node {
	int key;
	struct node *left, *right;
};

struct node *root = NULL;

struct node *bst_insert(struct node *r, int key) {
	if (r == NULL) {
		r = malloc(sizeof(struct node));
		r->key = key;
		r->left = NULL;
		r->right = NULL;
		return r;
	}
	if (key < r->key) r->left  = bst_insert(r->left,  key);
	if (key > r->key) r->right = bst_insert(r->right, key);
	return r;
}

void print(struct node *r) {
	if (r == NULL) {
		printf("( )");
		return;
	}
	if (r->left == NULL && r->right == NULL) {
		printf("(%d)", r->key);
		return;
	}
	printf("(");
	print(r->left );
	printf("(%d)", r->key);
	print(r->right);
	printf(")");
}

int bst_minimum(struct node *r) {
	if (r == NULL) return INT_MAX;
	if (r->left == NULL) return r->key;
	return bst_minimum(r->left);
}

int bst_maximum(struct node *r) {
	if (r == NULL) return -INT_MIN;
	if (r->right == NULL) return r->key;
	return bst_maximum(r->right);
}

struct node *bst_delete(struct node *r, int key) {
	if (r == NULL) { return NULL; }
	/* case 1: no child */
	if (r->key == key && r->left == NULL && r->right == NULL) {
		free(r);
		return NULL;
	}
	/* case 2: only right child */
	if (r->key == key && r->left == NULL) {
		free(r);
		return r->right;
	}
	/* case 2: only left child */
	if (r->key == key && r->right == NULL) {
		free(r);
		return r->left;
	}
	/* case 3: both children */
	if (r->key == key && r->left != NULL && r->right != NULL) {
		int min = bst_minimum(root->right);
		r->key = min;
		r->right = bst_delete(root->right, min);
	}

	if (r->key >  key) {
		r->left = bst_delete(r->left, key);
	}
	if (r->key <  key) {
		r->right = bst_delete(r->right, key);
	}
	return r;
}

int main(void) {
	root = bst_insert(root, 2);
	root = bst_insert(root, 1);
	root = bst_insert(root, 4);
	root = bst_insert(root, 3);
	print(root);printf("\n");
	root = bst_delete(root, 1); print(root);printf("\n");
	root = bst_delete(root, 2); print(root);printf("\n");
	root = bst_delete(root, 4); print(root);printf("\n");
	root = bst_delete(root, 3); print(root);printf("\n");

	return 0;
}