21.1. Khái niệm về cây nhị phân tìm kiếm (1/4)
Khái niệm:
Cây nhị phân tìm kiếm là cây rỗng hoặc cây mà node có
chứa các khóa.
Các khóa của node trên cây con bên trái nhỏ hơn khóa của
root, khóa của các node trên cây con bên phải lớn hơn khóa
của root.
Cây con bên trái và phải cũng là cây nhị phân tìm kiếm.
Việc quản lý cây nhị phân thông qua node root.
21.1. Khái niệm về cây NPTK (2/4)
21.1. Khái niệm về cây NPTK (3/4)
Một số tính chất của cây NPTK:
Cây nhị phân tìm kiếm là tập con của cây nhị phân, nên nó
cũng có các cách duyệt LNR, LRN, NLR.
Với cây nhị phân tìm kiếm, nếu duyệt cây theo kiểu inorder ta
sẽ được một dãy đã sắp theo chiều tăng dần.
Cây nhị phân tìm kiếm là cấu trúc tìm kiếm hiệu quả. Việc tìm
kiếm trên cây nhị phân tìm kiếm nhanh hơn tìm kiếm tuần tự.
Tuy nhiên, việc biểu diễn cây dạng mảng sẽ gây khó khăn cho
việc thêm, bớt.
Với việc biểu diễn dạng liên kết, ta có độ phức tạp của việc tìm
kiếm là O( logn).
14 trang |
Chia sẻ: thanhle95 | Lượt xem: 582 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 21: Cây nhị phân tìm kiếm - Ngô Hữu Phước, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Giảng viên: TS. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
Cấu trúc dữ liệu và giải thuật
Bài 21. Cây nhị phân tìm kiếm
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University1
Bài 21: Cây nhị phân tìm kiếm
Nội dung:
21.1. Khái niệm cây nhị phân tìm kiếm.
21.2. Các thao tác trên cây nhị phân tìm kiếm.
21.3. Một vài ví dụ sử dụng cây nhị phân tìm kiếm.
Tham khảo:
1. Deshpande Kakde: C and Data structures.chm, Chapter 20: Linked Lists
2. Elliz Horowitz – Fundamentals of Data Structures.chm, Chapter 4: Linked Lists
3. Kyle Loudon: Mastering Algorithms with C.chm, Chapter 5 Linked Lists.
4. Bài giảng TS Nguyễn Nam Hồng
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University2
21.1. Khái niệm về cây nhị phân tìm kiếm (1/4)
Khái niệm:
Cây nhị phân tìm kiếm là cây rỗng hoặc cây mà node có
chứa các khóa.
Các khóa của node trên cây con bên trái nhỏ hơn khóa của
root, khóa của các node trên cây con bên phải lớn hơn khóa
của root.
Cây con bên trái và phải cũng là cây nhị phân tìm kiếm.
Việc quản lý cây nhị phân thông qua node root.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University3
21.1. Khái niệm về cây NPTK (2/4)
Ví dụ về cây nhị phân tìm kiếm
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University4
50
30
25 40
35
60
70
65
21.1. Khái niệm về cây NPTK (3/4)
Một số tính chất của cây NPTK:
Cây nhị phân tìm kiếm là tập con của cây nhị phân, nên nó
cũng có các cách duyệt LNR, LRN, NLR.
Với cây nhị phân tìm kiếm, nếu duyệt cây theo kiểu inorder ta
sẽ được một dãy đã sắp theo chiều tăng dần.
Cây nhị phân tìm kiếm là cấu trúc tìm kiếm hiệu quả. Việc tìm
kiếm trên cây nhị phân tìm kiếm nhanh hơn tìm kiếm tuần tự.
Tuy nhiên, việc biểu diễn cây dạng mảng sẽ gây khó khăn cho
việc thêm, bớt...
Với việc biểu diễn dạng liên kết, ta có độ phức tạp của việc tìm
kiếm là O( logn).
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University5
21.1. Khái niệm về cây NPTK (4/4)
Cấu trúc cây nhị phân tìm kiếm:
template
struct tbnode
{
TreeEntry data;
struct tbnode *lchild, *rchild;
};
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University6
21.2. Các thao tác trên cây NPTK (1/)
Một số thao tác trên cây nhị phân tìm kiếm:
1. Khởi tạo cây NPTK.
2. TBInsert: Thêm một node vào cây NPTK.
3. TBCount: đếm số node trên cây NPTK.
4. TBRInorder: duyệt cây dạng inorder.
5. TBRPostorder: duyệt cây dạng postorder.
6. TBRPreorder: duyệt cây dạng preorder.
7. TBLevelorder: duyệt cây dạng levelorder.
8. TBDelete: xóa node trên cây NPTK.
9. TBGetptr: định vị một node và node cha của nó.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University7
21.2. Các thao tác trên cây NPTK (2/)
Khai báo lớp cây nhị phân tìm kiếm:
template class TBTree {
public:
TBTree();
int TBInsert(TreeEntry value);
int TBCount();
void TBRInorder(tbnode* treenode, QueueClassC *q);
void TBRPostorder(tbnode* treenode, QueueClassC *q);
void TBRPreorder(tbnode* treenode, QueueClassC *q);
void TBInorder(QueueClassC* q);
void TBPostorder(QueueClassC* q);
void TBPreorder(QueueClassC* q);
void TBLevelorder(QueueClassC* q);
void TBGetptr(tbnode **father, tbnode **curr, TreeEntry value);
int TBDelete(TreeEntry value);
template friend void TreePrint(TBTree tree, int type);
private: tbnode * root; };
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University8
21.2. Các thao tác trên cây NPTK (3/)
Khởi tạo cây NPTK:
template
TBTree::TBTree()
{
root=NULL;
}
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University9
root
NULL
21.2. Các thao tác trên cây NPTK (4/)
Thêm một node vào cây NPTK:
Nếu cây rỗng, cấp phát ô nhớ cho con
trỏ root.
Nếu cây không rỗng:
Sử dụng 2 con trỏ temp và temp1 để
xác định vị trí cần thêm (con trỏ temp1
sẽ trỏ vào NULL, con trỏ temp sẽ trỏ
vào node là cha của node mới).
Tùy thuộc vào giá trị mới được thêm
vào sẽ cấp phát ô nhớ cho temp->left
hay temp->right.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University10
root
50
NULL NULL
1
250
30
25 40
35
60
70
65
Thêm node
có giá trị
45 vào cây
temp
45NULL
NULL NULL
21.2. Các thao tác trên cây NPTK (5/)
template
int TBTree::TBInsert(TreeEntry value)
{ int kt=0;
tbnode * temp, *temp1;
if(root==NULL) {
root = (tbnode *)
malloc(sizeof(tbnode));
if (root==NULL) {
printf("Khong du bo nho");
return kt; }
kt=1;
root->data=value;
root->lchild=root->rchild=NULL;
}
else
{ temp1=root;
while(temp1!=NULL) {
temp=temp1;
if(temp1->data>value)
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University11
Thêm một node vào cây NPTK
temp1=temp1->lchild;
else
temp1=temp1->rchild; }
if(temp->data>value) {
temp->lchild = (tbnode *)
malloc(sizeof(tbnode));
if(temp->lchild==NULL) {
printf("Khong du bo nho");
return kt; }
kt=1;
temp=temp->lchild;
temp->data=value;
temp->lchild=temp->rchild=NULL;
}
else {
temp->rchild = (tbnode *)
malloc(sizeof(tbnode));
if(temp->rchild==NULL) {
printf("Khong du bo nho");
return kt; }
kt=1;
temp=temp->rchild;
temp->data=value;
temp->lchild=temp->rchild=NULL; }
}
return kt;
}
Tháng 09 năm 2009
21.2. Các thao tác trên cây NPTK (6/)
Xóa một node trên cây NPTK:
Xóa node không có con
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University12
21.2. Các thao tác trên cây NPTK (7/)
Xóa một node trên cây NPTK:
Xóa node có 1 con
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13
21.2. Các thao tác trên cây NPTK (8/)
Xóa một node trên cây NPTK:
Xóa node có 2 con
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University14