โดย นายภัทร สุขประเสริฐ
5231041421
2110211 Intro to Data Structure
What Red-Black Tree?
Red-Black Tree เป็นโครงสร้างข้อมูลประเภท self-balancing binary search tree ซึ่งใช้จัดการข้อมูลชนิดที่สามารถเปรียบเทียบได้ เช่น Integer, String โดยสามารถจัดการข้อมูลได้อย่างมีประสิทธิภาพ และมีประสิทธิภาพเชิงเวลาโดยรวมดี
Time complexity |
||
|---|---|---|
| Average | Worst Case | |
| Space | O(n) | O(n) |
| Search | O(logn) | O(logn) |
| Insert | O(logn) | O(logn) |
| Delete | O(logn) | O(logn) |
Why Red-Black Tree?
เป็นที่รู้กันว่าต้นไม้ค้นหาทวิภาค หรือ Binary search tree นั้นมีหลายชนิด ไม่ว่าจะเป็น Binary search tree แบบปกติ, AVL tree, AA tree, Scapegoat tree, Splay tree แต่ว่าคำถามที่น่าสนใจคือทำไม Java Collection Framework ซึ่งเป็น Libary ของภาษา JAVA หรือ STL ซึ่งเป็น Libary ของภาษา C++ ถึงเลือกใช้ Red-Black Tree ในการ implemented Set,Map? แต่ก่อนจะตอบคำถามนี้ได้จะต้องศึกษาก่อนว่า Red-Black Tree ทำงานอย่างไร? ดีกว่าต้นไม้อื่นอย่างไร? มีข้อด้อยอะไรมั้ย? ซึ่งเราจะศึกษาต่อไป
ตัวอย่าง Red-Black Tree
คุณสมบัติของ Red-Black Tree
Red-Black Tree เป็นต้นไม้ค้นหาทวิภาคซึ่งแต่ละ Node ของต้นไม้จะมีสีกำกับ, แดง หรือไม่ก็ดำ มีข้อกำหนดต่างๆตามต้นไม้ค้นหาทวิภาค และมีข้อบังคับเพิ่มเติมคือ
1.Node เป็นสีแดงหรือสีดำ
2.ราก(Root)เป็นสีดำ
3.ใบ(leaves)ทุกใบเป็นสีดำ
4.ลูกของ Node ที่เป็นสีแดงต้องเป็นสีดำ
5.ทุกๆทางเดินอย่างง่าย(simple path; ทางเดินที่ผ่านแต่ละ Node เพียงครั้งเดียว)จากรากไปยังใบจะผ่านจำนวน Node สีดำเท่ากัน
*black-height : จำนวน Node สีดำจากรากไปยังใบ
จากการที่ Red-Black Tree มีคุณสมบัติเช่นนี้เองทำให้ ระยะทางจากรากไปยังใบที่อยู่ใกล้ที่สุด กับระยะทางจากรากไปยังใบที่อยู่ไกลที่สุดห่างกันไม่เกิน สองเท่า (พิสูจน์โดย Contradiction ให้ระยะทางห่างกันเกินสองเท่า แต่จำนวน Nodeสีดำจะต้องเท่ากันตามคุณสมบัติของ Red-Black Tree ดังนั้นจำนวน Node สีแดงของเส้นทางที่ไกลย่อมต้องมากกว่า black-height และมากกว่าจำนวน Nodeสีแดงของเส้นทางที่ใกล้ แต่ว่าลูกของNodeสีแดงจะต้องเป็นสีดำเสมอทำให้เกิดข้อขัดแย้ง)จึงสามารถบอกได้ว่า Red-Black Tree นี้ค่อนข้างได้ดุลย์ และเนื่องจากประสิทธิภาพเชิงเวลาของการกระทำต่างๆในต้นไม้ค้นหาทวิภาคนั้นขึ้นอยู่กับความสูงทำให้การทำงานมีประสิทธิภาพที่ดีแม้จะอยู่ในกรณีย่ำแย่(ช้ากว่าไม่เกินสองเท่า ของกรณีที่ดี) ซึ่งต่างจาก Binary search tree ทั่วไป
ในต้นไม้ค้นหาทวิภาคทั่วๆไปนั้น เป็นไปได้ว่ามีบาง Nodeที่จะมีลูกเพียงฝั่งใดฝั่งหนึ่งเท่านั้น และ Node ที่เป็นใบจะเก็บข้อมูลได้ ซึ่งเราสามารถ implement Red-Black Tree ให้มีลักษณะเช่นนั้นได้ แต่จะเพิ่มความยุ่งยากและความซับซ้อนมากขึ้น ดังนั้นจะกำหนดให้ Node ที่เป็นใบ เป็น null leaf คือ Node ที่ไม่ได้เก็บข้อมูลใดๆ (sentinel) การกระทำแบบนี้จะทำให้มีความสะดวกให้การ implementเพิ่มขึ้น โดย Node ภายในต้นไม้ Node ใดๆจะมีลูกทั้งทางฝั่งซ้ายและฝั่งขวาเสมอ การกระทำเช่นนี้ทำให้รับประกันได้ว่าNode สีแดงจะต้องมีลูกเป็น Node สีดำที่เป็น Node ภายในทั้ง 2 Node หรือไม่ก็เป็น ใบทั้ง 2 Node, Node ภายในสีดำที่มีลูกเป็นใบ 1 Node นั้น ลูกอีกฝั่งจะต้องเป็น ใบหรือไม่ก็ Node ภายในสีแดงที่มีลูกเป็นใบเสมอ
*การแสดงสีอาจแสดงด้วย edge แทนที่จะเป็นสีของ nodeซึ่งไม่ได้ทำให้เกิดข้อแตกต่างแต่อย่างใด
Implementation
ออกแบบ Node ให้เก็บ parent,child,color,element
source code ส่วนของRed-Black Node
private class RBNode{
RBNode leftChild,rightChild,parent;
Comparable element;
boolean color;
RBNode(RBNode l,RBNode r,RBNode p,Comparable e,boolean c){
leftChild=l;
rightChild=r;
parent=p;
element=e;
color=c;
}
}
field ต่างๆ ใน Red-Black Tree (root,sentinel)
source code ประกาศ root,sentinel
private static final boolean BLACK=false,RED=true; private RBNode NIL=new RBNode(null,null,null,null,BLACK); private RBNode root=NIL;
ต่อไปจะทำการ implement ส่วนของบริการพื้นฐานต่างๆที่มีให้อันได้แก่ Insert, Search, Delete โดยจะเริ่มจาก Search ก่อน ซึ่งในส่วนของ Search นี้จะทำเหมือนกับของ Binary Search Tree โดยจะเริ่มค้นหาจากรากของต้นไม้ ถ้าค่าของตัวที่ต้องการค้นหามากกว่าเท่ากับค่าของ Node ที่กำลังค้นหา ก็คืนค่านั้นไป(พบค่านั้นในต้นไม้) แต่ถ้าค่ามากกว่าค่าของ Node ที่กำลังค้นหา ให้ไปค้นใน Sub Tree ทางด้านขวาแทน มิฉะนั้นก็ไปค้นใน Subtree ทางด้านซ้ายแทน โดยถ้าค้นหาจนถึง Sentinel แปลว่าไม่เจอให้คืนค่า null ออกมา
source code ส่วนของ search
public Comparable search(Comparable e){
RBNode re=search(root,e);
if(re==null)return null;
return re.element;
}
private RBNode search(RBNode cur,Comparable e){
if(cur==NIL)return null;
if(cur.element.compareTo(e)==0)return cur;
if(cur.element.compareTo(e)<0)return search(cur.rightChild,e);
else return search(cur.leftChild,e);
}
สำหรับการ Insert นั้นจะทำเหมือน Binary Search Tree ทั่วไปคือ ท่องไปในต้นไม้จนกว่าจะเจอที่ๆ element ตัวที่กำลัง insert ควรจะอยู่แล้วสร้าง Node สำหรับเก็บ elementนั้นๆ (ใน code นี้จะถือว่าต้นไม้ไม่เก็บข้อมูลซ้ำ ดังนั้นถ้าพบnode ที่เก็บelementนั้นๆอยู่แล้วก็จะไม่ต้องทำอะไร)
source code ส่วนของ insert
public void insert(Comparable e){
RBNode z=new RBNode(null,null,null,e,RED);
RBNode y=NIL;
RBNode x=root;
while(x!=NIL){
y=x;
if(z.element.compareTo(x.element)<0)x=x.leftChild;
else if(z.element.compareTo(x.element)==0)return;
else x=x.rightChild;
}
z.parent=y;
if(y==NIL)root=z;
else if(z.element.compareTo(y.element)<0)y.leftChild=z;
else y.rightChild=z;
z.leftChild=NIL;
z.rightChild=NIL;
insertFixup(z);
}
แต่การ Insert อาจทำให้ Red-Black Tree สูญเสียคุณสมบัติตามข้อกำหนดของมันได้! ดังนั้นหลังจาก Insert แล้วเราจะต้องพิจารณาว่าการ Insert นั้นทำให้มันสูญเสียข้อกำหนดข้อไหนไปบ้าง ซึ่งข้อ 1,3,5 จะยังคงเป็นจริงอยู่ ดังนั้นที่จะต้องพิจารณาคือข้อ 2 และ 4โดยข้อ 2จะเกิดความขัดแย้งเมื่อตัวที่เรา Insert เข้าไปเป็น root และข้อ 4 จะเกิดความขัดแย้งเมื่อ parent ของตัวที่เรา Insert เข้าไปเป็นสีแดง ซึ่งในการแก้ไขนั้นเราจะต้องเล่นกับสีและ reference ต่างๆของ Node ที่เราพึ่งใส่เข้าไป Parent และ Uncle (Node ที่ share Parent เดียวกับ Parent ของ Node ที่เราพึ่งใส่เข้าไป) โดยจะใช้ Operationที่เรียกว่า Left Rotate และ Right Rotate ซึ่งเขียนได้ดังนี้
source code ส่วนของ rotation
private void leftRotate(RBNode cur){
RBNode tmp=cur.rightChild;
cur.rightChild=tmp.leftChild;
if(tmp.leftChild!=NIL)tmp.leftChild.parent=cur;
tmp.parent=cur.parent;
if(cur.parent==NIL)root=tmp;
else if(cur.parent.leftChild==cur)cur.parent.leftChild=tmp;
else cur.parent.rightChild=tmp;
tmp.leftChild=cur;
cur.parent=tmp;
}
// สำหรับ rightRotate นั้นทำแบบเดียวกับ leftRotate แต่กลับข้างกันระหว่าง left,right
การ fixup หลังจาก insert เป็น operation ที่ทำเพื่อแก้ไขข้อขัดแย้งที่เกิดขึ้น โดยสามารถเขียน code ได้ดังนี้ (คำอธิบายจะเพิ่มเติมภายหลัง)
source code ส่วนของ insertFixup
private void insertFixup(RBNode z){
while(z.parent.color==RED){
if(z.parent==z.parent.parent.leftChild){
RBNode y=z.parent.parent.rightChild;
if(y.color==RED){
z.parent.color=BLACK;
y.color=BLACK;
z.parent.parent.color=RED;
z=z.parent.parent;
}
else {
if(z==z.parent.rightChild){
z=z.parent;
leftRotate(z);
}
z.parent.color=BLACK;
z.parent.parent.color=RED;
rightRotate(z.parent.parent);
}
}
else{
RBNode y=z.parent.parent.leftChild;
if(y.color==RED){
z.parent.color=BLACK;
y.color=BLACK;
z.parent.parent.color=RED;
z=z.parent.parent;
}
else{
if(z==z.parent.leftChild){
z=z.parent;
rightRotate(z);
}
z.parent.color=BLACK;
z.parent.parent.color=RED;
leftRotate(z.parent.parent);
}
}
}
root.color=BLACK;
}
สำหรับการ delete ก็จะเป็นลักษณะเดียวกับการทำ insert คือ operation ของการทำ delete ทั่วๆไปจะมีลักษณะเหมือนกับ delete ของ Binary Search Tree เริ่มจากพิจารณาว่า Node ที่จะทำการ delete นั้นไม่มีลูกเป็น Node ภายใน , มีลูก 1 Node เป็น Node ภายใน, ลูกทั้ง 2 Node เป็น Node ภายใน โดยถ้าเป็นกรณีที่ Node ที่จะทำการ delete ไม่มีลูกเป็น Node ภายในก็จะลบ Node นั้นทิ้งแล้วแทนด้วย sentinelเลย แต่ถ้ามี 1 Node ภายใน ก็จะแทน Node ที่ต้องการลบด้วยลูกของ Node นั้นเลย และในกรณีสุดท้ายจะหา successor (ตัวที่มีค่าน้อยที่สุดที่มีค่ามากกว่า Node นั้น) มาแล้วทำการลบ successor แทน แล้วย้ายค่าของ successor มาไว้ใน Node นั้น จากนั้นก็ต้องพิจารณาว่าการลบนั้นทำให้เกิดข้อขัดแย้งในคุณสมบัติ 5 ข้อหรือไม่ โดยจะเกิดข้อขัดแย้งขึ้นเมื่อ Node ที่เราทำการลบไป เป็นสีดำก็จะต้องทำการ fixup เพื่อขจัดข้อขัดแย้งไป (ซึ่งจะอธิบาย fixup ในโอกาสต่อไป)
source code ส่วนของ delete
public void delete(Comparable e){
RBNode z=search(root, e);
if(z!=null)delete(z);
}
private void delete(RBNode z){
RBNode x,y;
if(z.leftChild==NIL||z.rightChild==NIL)y=z;
else {
y=z.rightChild;
while(y.leftChild!=NIL)y=y.leftChild;
}
if(y.leftChild!=NIL)x=y.leftChild;
else x=y.rightChild;
x.parent=y.parent;
if(y.parent==NIL)root=x;
else if(y==y.parent.leftChild)y.parent.leftChild=x;
else y.parent.rightChild=x;
if(y!=z)z.element=y.element;
if(y.color==BLACK)deleteFixup(x);
}
source code ส่วนของ deleteFixup
private void deleteFixup(RBNode x){
while(x!=root&&x.color==BLACK){
if(x==x.parent.leftChild){
RBNode w=x.parent.rightChild;
if(w.color==RED){
w.color=BLACK;
x.parent.color=RED;
leftRotate(x.parent);
w=x.parent.rightChild;
}
if(w.leftChild.color==BLACK&&w.rightChild.color==BLACK){
w.color=RED;
x=x.parent;
}
else{
if(w.rightChild.color==BLACK){
w.leftChild.color=BLACK;
w.color=RED;
rightRotate(w);
w=x.parent.rightChild;
}
w.color=x.parent.color;
x.parent.color=BLACK;
w.rightChild.color=BLACK;
leftRotate(x.parent);
x=root;
}
}
else{
RBNode w=x.parent.leftChild;
if(w.color==RED){
w.color=BLACK;
x.parent.color=RED;
rightRotate(x.parent);
w=x.parent.leftChild;
}
if(w.rightChild.color==BLACK&&w.leftChild.color==BLACK){
w.color=RED;
x=x.parent;
}
else{
if(w.leftChild.color==BLACK){
w.rightChild.color=BLACK;
w.color=RED;
leftRotate(w);
w=x.parent.leftChild;
}
w.color=x.parent.color;
x.parent.color=BLACK;
w.leftChild.color=BLACK;
rightRotate(x.parent);
x=root;
}
}
}
x.color=BLACK;
}
เป็นอันเสร็จสิ้นการ Implement Red-Black Tree ในภาษา JAVA และต่อไปจะเป็นการทดสอบเทียบประสิทธิภาพระหว่าง Red-Black Tree กับ Binary Search Tree ที่เขียนขึ้นโดยจะขอแสดงโค้ดเต็มๆของต้นไม้ทั้งสองแบบดังต่อไปนี้
Red-Black Tree source code
import java.util.ArrayDeque;
import java.util.ArrayList;
public class RBTree {
private static final boolean BLACK=false,RED=true;
private RBNode NIL=new RBNode(null,null,null,null,BLACK);
private RBNode root=NIL;
private class RBNode{
RBNode leftChild,rightChild,parent;
Comparable element;
boolean color;
RBNode(RBNode l,RBNode r,RBNode p,Comparable e,boolean c){
leftChild=l;
rightChild=r;
parent=p;
element=e;
color=c;
}
}
private void leftRotate(RBNode cur){
RBNode tmp=cur.rightChild;
cur.rightChild=tmp.leftChild;
if(tmp.leftChild!=NIL)tmp.leftChild.parent=cur;
tmp.parent=cur.parent;
if(cur.parent==NIL)root=tmp;
else if(cur.parent.leftChild==cur)cur.parent.leftChild=tmp;
else cur.parent.rightChild=tmp;
tmp.leftChild=cur;
cur.parent=tmp;
}
private void rightRotate(RBNode cur){
RBNode tmp=cur.leftChild;
cur.leftChild=tmp.rightChild;
if(tmp.rightChild!=NIL)tmp.rightChild.parent=cur;
tmp.parent=cur.parent;
if(cur.parent==NIL)root=tmp;
else if(cur.parent.leftChild==cur)cur.parent.leftChild=tmp;
else cur.parent.rightChild=tmp;
tmp.rightChild=cur;
cur.parent=tmp;
}
public Comparable search(Comparable e){
RBNode re=search(root,e);
if(re==null)return null;
return re.element;
}
private RBNode search(RBNode cur,Comparable e){
if(cur==NIL)return null;
if(cur.element.compareTo(e)==0)return cur;
if(cur.element.compareTo(e)<0)return search(cur.rightChild,e);
else return search(cur.leftChild,e);
}
public void insert(Comparable e){
RBNode z=new RBNode(null,null,null,e,RED);
RBNode y=NIL;
RBNode x=root;
while(x!=NIL){
y=x;
if(z.element.compareTo(x.element)<0)x=x.leftChild;
else if(z.element.compareTo(x.element)==0)return;
else x=x.rightChild;
}
z.parent=y;
if(y==NIL)root=z;
else if(z.element.compareTo(y.element)<0)y.leftChild=z;
else y.rightChild=z;
z.leftChild=NIL;
z.rightChild=NIL;
insertFixup(z);
}
private void insertFixup(RBNode z){
while(z.parent.color==RED){
if(z.parent==z.parent.parent.leftChild){
RBNode y=z.parent.parent.rightChild;
if(y.color==RED){
z.parent.color=BLACK;
y.color=BLACK;
z.parent.parent.color=RED;
z=z.parent.parent;
}
else {
if(z==z.parent.rightChild){
z=z.parent;
leftRotate(z);
}
z.parent.color=BLACK;
z.parent.parent.color=RED;
rightRotate(z.parent.parent);
}
}
else{
RBNode y=z.parent.parent.leftChild;
if(y.color==RED){
z.parent.color=BLACK;
y.color=BLACK;
z.parent.parent.color=RED;
z=z.parent.parent;
}
else{
if(z==z.parent.leftChild){
z=z.parent;
rightRotate(z);
}
z.parent.color=BLACK;
z.parent.parent.color=RED;
leftRotate(z.parent.parent);
}
}
}
root.color=BLACK;
}
public void delete(Comparable e){
RBNode z=search(root, e);
if(z!=null)delete(z);
}
private void delete(RBNode z){
RBNode x,y;
if(z.leftChild==NIL||z.rightChild==NIL)y=z;
else {
y=z.rightChild;
while(y.leftChild!=NIL)y=y.leftChild;
}
if(y.leftChild!=NIL)x=y.leftChild;
else x=y.rightChild;
x.parent=y.parent;
if(y.parent==NIL)root=x;
else if(y==y.parent.leftChild)y.parent.leftChild=x;
else y.parent.rightChild=x;
if(y!=z)z.element=y.element;
if(y.color==BLACK)deleteFixup(x);
}
private void deleteFixup(RBNode x){
while(x!=root&&x.color==BLACK){
if(x==x.parent.leftChild){
RBNode w=x.parent.rightChild;
if(w.color==RED){
w.color=BLACK;
x.parent.color=RED;
leftRotate(x.parent);
w=x.parent.rightChild;
}
if(w.leftChild.color==BLACK&&w.rightChild.color==BLACK){
w.color=RED;
x=x.parent;
}
else{
if(w.rightChild.color==BLACK){
w.leftChild.color=BLACK;
w.color=RED;
rightRotate(w);
w=x.parent.rightChild;
}
w.color=x.parent.color;
x.parent.color=BLACK;
w.rightChild.color=BLACK;
leftRotate(x.parent);
x=root;
}
}
else{
RBNode w=x.parent.leftChild;
if(w.color==RED){
w.color=BLACK;
x.parent.color=RED;
rightRotate(x.parent);
w=x.parent.leftChild;
}
if(w.rightChild.color==BLACK&&w.leftChild.color==BLACK){
w.color=RED;
x=x.parent;
}
else{
if(w.leftChild.color==BLACK){
w.rightChild.color=BLACK;
w.color=RED;
leftRotate(w);
w=x.parent.leftChild;
}
w.color=x.parent.color;
x.parent.color=BLACK;
w.leftChild.color=BLACK;
rightRotate(x.parent);
x=root;
}
}
}
x.color=BLACK;
}
public void dfs(){
if(root.color==RED)System.out.println("bad root");
dfs(root,0);
}
public int dfs(RBNode cur,int bh){
if(cur==NIL){
if(cur.color==RED)System.out.println("BadNIL");
//System.out.println(bh+1);
return bh+1;
}
if(cur.color==BLACK)bh++;
int l,r;
if(cur.color==RED){
if(cur.leftChild.color==RED||cur.rightChild.color==RED){
System.out.println("badcolor");
}
}
l=dfs(cur.leftChild,bh);
r=dfs(cur.rightChild,bh);
if(l!=r){
System.out.println("bad!");
throw new RuntimeException();
}
return l;
}
public void traverse(){
ArrayDeque<RBNode> q=new ArrayDeque<RBNode>();
q.add(root);
while(!q.isEmpty()){
ArrayList<RBNode> pList=new ArrayList<RBNode>();
while(!q.isEmpty())pList.add(q.removeFirst());
for(int i=0;i<pList.size();i++){
if(pList.get(i)==NIL){
System.out.print("NIL ");
}
else{
System.out.print(((Integer)pList.get(i).element).intValue()+" ");
q.add(pList.get(i).leftChild);
q.add(pList.get(i).rightChild);
}
}
System.out.println();
}
}
}
My Binary Search Tree source code
public class BinarySearchTree {
private class BSTNode{
BSTNode(BSTNode l,BSTNode r,Comparable e){
leftChild=l;
rightChild=r;
element=e;
}
private BSTNode leftChild,rightChild;
private Comparable element;
public BSTNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BSTNode leftChild) {
this.leftChild = leftChild;
}
public BSTNode getRightChild() {
return rightChild;
}
public void setRightChild(BSTNode rightChild) {
this.rightChild = rightChild;
}
public Comparable getElement() {
return element;
}
public void setElement(Comparable element) {
this.element = element;
}
}
private BSTNode root=null;
public void insert(Comparable e){
if(root==null){
root=new BSTNode(null,null,e);
return;
}
BSTNode cur=root;
while(true){
if(cur.getElement().compareTo(e)==0)return;
if(cur.getElement().compareTo(e)<0){
if(cur.getRightChild()==null){
cur.setRightChild(new BSTNode(null,null,e));
return;
}
else cur=cur.getRightChild();
}
else{
if(cur.getLeftChild()==null){
cur.setLeftChild(new BSTNode(null,null,e));
return;
}
else cur=cur.getLeftChild();
}
}
}
public Comparable search(Comparable e){
BSTNode re=search(root,e);
if(re==null)return null;
return re.getElement();
}
private BSTNode search(BSTNode cur,Comparable e){
if(cur==null)return null;
if(cur.getElement().compareTo(e)==0)return cur;
if(cur.getElement().compareTo(e)<0)return search(cur.getRightChild(),e);
else return search(cur.getLeftChild(),e);
}
public void delete(Comparable e){
delete(null,root,e);
}
private void delete(BSTNode par,BSTNode cur,Comparable e){
if(cur==null)return;
if(cur.getElement().compareTo(e)<0){
delete(cur,cur.getRightChild(),e);
}
else if(cur.getElement().compareTo(e)>0){
delete(cur,cur.getLeftChild(),e);
}
else{
if(cur.getLeftChild()!=null&&cur.getRightChild()!=null){
//find successor
BSTNode pre=root;
BSTNode suc=root.getRightChild();
while(suc.getLeftChild()!=null){
pre=suc;
suc=suc.getLeftChild();
}
cur.setElement(suc.getElement());
delete(pre,suc,suc.getElement());
}
else if(cur.getLeftChild()!=null||cur.getRightChild()!=null){
if(cur.getLeftChild()!=null){
if(par==null){
root=cur.getLeftChild();
}
else if(par.getLeftChild()==cur){
par.setLeftChild(cur.getLeftChild());
}
else{
par.setRightChild(cur.getLeftChild());
}
}
else{
if(par==null){
root=cur.getRightChild();
}
else if(par.getLeftChild()==cur){
par.setLeftChild(cur.getRightChild());
}
else{
par.setRightChild(cur.getRightChild());
}
}
}
else{
if(par==null)root=null;
else {
if(par.getLeftChild()==cur)par.setLeftChild(null);
else par.setRightChild(null);
}
}
}
}
}
Tester source code
import java.util.ArrayList;
import java.util.Random;
import java.util.Timer;
public class Tester {
long nanoTimeBuildRBTree(ArrayList<Integer> aList){
long now=System.nanoTime();
buildRBTree(aList);
return System.nanoTime()-now;
}
RBTree buildRBTree(ArrayList<Integer> aList){
RBTree RBT=new RBTree();
for(int i=0;i<aList.size();i++)RBT.insert(aList.get(i));
return RBT;
}
double nanoTimeFoundSearchRBTree(ArrayList<Integer> aList,int count){
Random randomizer=new Random();
RBTree RBT=buildRBTree(aList);
long overAll=0;
for(int i=0;i<count;i++){
long now=System.nanoTime();
RBT.search(aList.get(randomizer.nextInt(aList.size())));
overAll+=System.nanoTime()-now;
}
double avg=overAll;
return avg/count;
}
double nanoTimeRandomSearchRBTree(ArrayList<Integer> aList,int count){
Random randomizer=new Random();
RBTree RBT=buildRBTree(aList);
long overAll=0;
for(int i=0;i<count;i++){
long now=System.nanoTime();
RBT.search(new Integer(randomizer.nextInt()));
overAll+=System.nanoTime()-now;
}
double avg=overAll;
return avg/count;
}
double nanoTimeRandomDeleteRBTree(ArrayList<Integer> aList,int count){
Random randomizer=new Random();
RBTree RBT=buildRBTree(aList);
long overAll=0;
for(int i=0;i<count;i++){
long now=System.nanoTime();
RBT.delete(new Integer(randomizer.nextInt()));
overAll+=System.nanoTime()-now;
}
double avg=overAll;
return avg/count;
}
long nanoTimeBuildBSTree(ArrayList<Integer> aList){
long now=System.nanoTime();
buildBSTree(aList);
return System.nanoTime()-now;
}
BinarySearchTree buildBSTree(ArrayList<Integer> aList){
BinarySearchTree BST=new BinarySearchTree();
for(int i=0;i<aList.size();i++)BST.insert(aList.get(i));
return BST;
}
double nanoTimeFoundSearchBinarySearchTree(ArrayList<Integer> aList,int count){
Random randomizer=new Random();
BinarySearchTree BST=buildBSTree(aList);
long overAll=0;
for(int i=0;i<count;i++){
long now=System.nanoTime();
BST.search(aList.get(randomizer.nextInt(aList.size())));
overAll+=System.nanoTime()-now;
}
double avg=overAll;
return avg/count;
}
double nanoTimeRandomSearchBinarySearchTree(ArrayList<Integer> aList,int count){
Random randomizer=new Random();
BinarySearchTree BST=buildBSTree(aList);
long overAll=0;
for(int i=0;i<count;i++){
long now=System.nanoTime();
BST.search(new Integer(randomizer.nextInt()));
overAll+=System.nanoTime()-now;
}
double avg=overAll;
return avg/count;
}
double nanoTimeRandomDeleteBinarySearchTree(ArrayList<Integer> aList,int count){
Random randomizer=new Random();
BinarySearchTree BST=buildBSTree(aList);
long overAll=0;
for(int i=0;i<count;i++){
long now=System.nanoTime();
BST.delete(new Integer(randomizer.nextInt()));
overAll+=System.nanoTime()-now;
}
double avg=overAll;
return avg/count;
}
ArrayList<Integer> generateIntegerList(int n){
Random randomizer=new Random();
ArrayList<Integer> re= new ArrayList<Integer>();
for(int i=0;i<n;i++)re.add(new Integer(randomizer.nextInt()));
//for(int i=0;i<n;i++)re.add(new Integer(i));
return re;
}
void testBuildTree(){
Random randomizer=new Random();
long buildBSTTime=0,buildRBTTime=0;
for(int i=0;i<100;i++){
ArrayList<Integer> aList=this.generateIntegerList(randomizer.nextInt(40000)+10000);
buildBSTTime+=this.nanoTimeBuildBSTree(aList);
buildRBTTime+=this.nanoTimeBuildRBTree(aList);
}
double avgBuildBST=buildBSTTime,avgBuildRBT=buildRBTTime;
avgBuildBST/=100;
avgBuildRBT/=100;
avgBuildBST/=1000;
avgBuildRBT/=1000;
System.out.println("Build Time Average : "+ "BST = "+avgBuildBST+" : RBT = "+avgBuildRBT);
}
void testFoundSearch(){
Random randomizer=new Random();
double BSTtime=0,RBTtime=0;
RBTree RBT;
BinarySearchTree BST;
for(int i=0;i<100;i++){
ArrayList<Integer> aList=this.generateIntegerList(randomizer.nextInt(40000)+10000);
BSTtime+=this.nanoTimeFoundSearchBinarySearchTree(aList, aList.size()*2);
RBTtime+=this.nanoTimeFoundSearchRBTree(aList,aList.size()*2);
}
double avgBST=BSTtime;
double avgRBT=RBTtime;
avgBST/=100;
avgRBT/=100;
avgBST/=1000;
avgRBT/=1000;
System.out.println("Found Search Time Average : "+ "BST = "+avgBST+" : RBT = "+avgRBT);
}
void testRandomSearch(){
Random randomizer=new Random();
double BSTtime=0,RBTtime=0;
RBTree RBT;
BinarySearchTree BST;
for(int i=0;i<100;i++){
ArrayList<Integer> aList=this.generateIntegerList(randomizer.nextInt(40000)+10000);
BSTtime+=this.nanoTimeRandomSearchBinarySearchTree(aList, aList.size()*2);
RBTtime+=this.nanoTimeRandomSearchRBTree(aList,aList.size()*2);
}
double avgBST=BSTtime;
double avgRBT=RBTtime;
avgBST/=100;
avgRBT/=100;
avgBST/=1000;
avgRBT/=1000;
System.out.println("Random Search Time Average : "+ "BST = "+avgBST+" : RBT = "+avgRBT);
}
void testDelete(){
Random randomizer=new Random();
double BSTtime=0,RBTtime=0;
RBTree RBT;
BinarySearchTree BST;
for(int i=0;i<100;i++){
ArrayList<Integer> aList=this.generateIntegerList(randomizer.nextInt(40000)+10000);
BSTtime+=this.nanoTimeRandomDeleteBinarySearchTree(aList, aList.size()/2);
RBTtime+=this.nanoTimeRandomDeleteRBTree(aList,aList.size()/2);
}
double avgBST=BSTtime;
double avgRBT=RBTtime;
avgBST/=100;
avgRBT/=100;
avgBST/=1000;
avgRBT/=1000;
System.out.println("Delete Time Average : "+ "BST = "+avgBST+" : RBT = "+avgRBT);
}
public static void main(String[] arg){
Tester test=new Tester();
test.testBuildTree();
test.testFoundSearch();
test.testRandomSearch();
test.testDelete();
}
}
ผลการทดสอบ จากข้อมูลตัวอย่างสุ่มขนาด 10000-50000 จำนวน 100 ชุด
| BST | RBT | (millisecond) | |
| BuildTree | 30832.241550000002 | 34689.584520000004 | |
| Search | 1.4585315736377533 | 1.3168435331842412 | |
| Delete | 1.5076367025227122 | 1.337538208969618 |
ผลการทดสอบ จากข้อมูลตัวอย่างซึ่งเรียงจากน้อยไปมากขนาด 1000-50000
| BST | RBT | (millisecond) | |
| BuildTree | 83328.20776 | 1717.41572 | |
| Search | 43.89119303149893 | 0.6463051038974514 | |
| Delete | 32.40159233736944 | 0.636036849835586 |
จากการทดสอบจะเห็นได้ว่าในกรณีทั่วๆไปนั้น ประสิทธิภาพของ Red-Black Tree และ Binary search treeจะทำได้พอๆกัน แต่ให้กรณีย่ำแย่คือข้อมูลมีการเรียงจากน้อยไปมาก หรือจากมากไปน้อยนั้น Red-Black Tree จะทำได้ดีกว่ามาก จนกระทั่งไม่สมควรที่จะใช้ต้นไม้ค้นหาทวิภาคทำงานเลย (นอกจากนี้ถ้าเพิ่มปริมาณข้อมูลแล้ว การค้นหาใน Binary search tree จะทำให้เกิด Stack overflow อีกด้วย) ดังนั้นเมื่อเทียบกันแล้ว Library ต่างๆก็คงจะไม่เลือกที่จะเขียน Template ด้วย Binary search tree แบบปกติแน่นอน แต่ว่ายังมีต้นไม้ชนิดอื่นๆที่น่าสนใจดังนั้นในโอกาสต่อไปจะนำต้นไม้ชนิดอื่นๆ เช่น AVL Tree, AA Tree มาเปรียบเทียบเพื่อให้เห็นถึงประสิทธิภาพและข้อดีข้อด้อย เพื่อจะตอบคำถามว่า Red-Black Tree จึงเป็นต้นไม้ค้นหาที่ถูกนิยมใช้กันทั่วไปทั้งใน Java Collection Framework ,STL หรือแม้กระทั้งใน Shceduler ของ Linux kernel
Reference
- Red-black tree from Wikipedia
- THOMAS H. CORMEN ,CHARLES E. LEISERSON ,RONALD L. RIVEST ,CLIFFORD STEIN. INTRODUCTION TO ALGORITHMS 2nd edition: The MIT Press (2001)
- Comparison of Binary Search Trees(BSTs)
- Dr Dobbs – STL’s Red-Black Trees
pattarasps 
Leave a Reply