CÂY TÌM KIẾM NHỊ PHÂN

CÂY TÌM KIẾM NHỊ PHÂN (BINARY SEARCH TREES):
Định nghĩa: là cây NHỊ PHÂN mà khóa tại mỗi nút lớn hơn khóa của tất cả các nút thuộc cây con bên trái và nhỏ hơn khóa của tất cả các nút thuộc cây con bên phải. [elcit.forumvi.com]
Nhận xét:
-1). Trên cây TKNP không có 2 nút cùng khóa.
-2). Cây con của một cây TKNP là cây TKNP.
-3). Khi duyện TRUNG TỰ cây TKNP ta được một dãy có thứ tự tăng.

Code ngôn ngữ C:

Code:


Tree Search(KeyType x,Tree Root){
 if(Root==NULL) return NULL; //không tìm thấy khóa x
 else
      if(Root->Key==x) return Root; /*tìm thấy khóa x*/
      else
          if(Root->Key>x) return Search(x,Root->Right);
          else return Search(x,Root->Left);
}


Nhận xét: giải thuật này sẽ rất hiệu quả về mặt thời gian nếu cây TKNP được tổ chức tốt, nghĩa là cây tương đối "cân bằng".
Tổng kết: Cấu trúc cây TKNP như là một ứng dụng cây nhị phân trong tổ chức dữ liệu phục vụ cho tìm kiếm nhanh.
Cây TKNP sẽ phát huy hiệu quả tốt nhất nếu nó "cân bằng". Có nhiều cách cân bằng khác nhau để cho các thao tác trên cây TKNP đạt hiệu quả O(logn) với n là số nút trên cây.
Các trường hợp mà các giải thuật trên cây TKNP:
-Có hiệu quả nhất: cây cân bằng.
-Kém hiệu quả nhất: cây suy biến (mỗi nút trên cây có nhiều nhất một con).

-------------------------------------
ÁP DỤNG
-------------------------------------

[You must be registered and logged in to see this image.]