Tìm Kiếm(Searching) trong java

Khi bạn lập trình java gặp bài toán tìm kiếm:

- Tìm kiếm xuất hiện trong cuộc sống hằng ngày và trong cả xử lý tin học:
- Có n bản ghi, mỗi bản ghi ứng với một khóa, và hãy tìm bản ghi có giá trị khóa tương ứng bằng X cho trước

1. Tìm kiếm tuần tự(sequential searching)

- Đây là một kĩ thuật đơn giản và cổ điển(mình nghĩ các bạn lúc mới học chắc toàn dùng phép tìm kiếm này) : TÌm bắt đầu từ khóa thứ nhất, lần lượt só sánh khóa tìm kiếm với khóa tương ứng của các bản ghi trong bảng cho tới khi tìm được bản ghi mong muốn hoặc đã hế bảng mà chưa tìm thấy.
Sau đây là giải thuật:

1. Sequen-Search(k,n,X) (Dãy khóa K gồm có n phần tử, X là khóa tìm kiếm)
2. i=1; k[n+1]=X
3. while k != X do i =i+1
   [*]if i=n+1 write(không tìm thấy)
   [*]else tìm thấy

2.Tìm kiếm nhị phân(Binary searching)

- Đây là một phương pháp tìm kiếm khá thông dụng
- ví dụ khi tra số điện thoại trong danh bạ, hay khi tìm một từ trong từ điển ta chọn ngẫu nhiên một khóa bất kì rồi bắt đầu tiến lên hoặc xuống. Và tìm kiến nhị phân cũng vậy, tuy nhiên thay vì chọn bất kì một phần tử thì ta chọn phần tử ở giữa dãy khóa đang xét để so sánh với khóa cần tìm

Giải thuật sau đây thực hiện phép tìm kiếm ::

1. Binary search(k,n,X)
2. (dãy k gồm n khóa đuộc sắp xếp theo thứ tự tăng dần l: chỉ số phần tử đầu, r chỉ số phần tử cuối)
3. l=1,r=n.
4. m=(l+r)/2
5. while l<r
6. {
7. if X<k[m] r= m-1
8. else if X>k[m] l = m+1
9. else write (tìm đc X)
10. }
11. write không tìm được X
12. Giải thuật tìm kiếm nhị phân có thể viết dưới dạng đệ qui như sau:
13. if X<k[m]
14. call Binary search(l,m-1,X)
15. else
16. if X>k[m]
17. call Binary search(m+1,r,X )
18. else tìm thấy phần tử cần tìm kiếm.

- So với tìm kiếm tuần tự thì phép tìm kiếm nhị phân, chi phí tìm kiếm là giảm đi rất nhiều
nhưng trước khi tìm kiếm nhị phân chúng ta phải sắp xếp, mà chi phí cho sắp xếp rất có thể lớn và đay chính là nhược điểm của phương pháp này.

3.Cây nhị phân tìm kiếm

- Định nghĩa cây nhị phân tìm kiếm:

mọi khóa thuộc cây con trái nút đó đều nhỏ hơn khóa tương ứng với nút đó
mọi khóa của cây con phải nút đó lớn hơn khóa tương ứng với nút đó

- Giải thuật tìm kiếm bằng cây nhị phân tìm kiếm:

So sánh với gốc của cây nếu khoogn có gốc thì phép tìm kiếm không thỏa
Nếu bằng gốc thì pháp tìm kiếm được thỏa
nếu lớn hơn gốc thì ta tìm kiếm tiếp sang cây con phải và lặp lại cách làm tương tự

Nếu nhỏ hơn gốc thì ta chuyển sang tìm kiếm bằng cây con trái lặp lại 4 bước tương tự như tìm kiếm với gốc ban đầu.
- Để dễ dàng cho việc tìm kiếm ta sẽ giả sử mỗi nút của cây nhị phân tìm kiếm gồm có 4 trường

LPTR: chứa con trỏ chỉ vào gốc cây con trái
RPTR: chứa con trỏ chỉ vào gốc cây con trái
Key: nhận giá trị tương ứng với từng nú làm khóa để tìm kiếm
info: ghi nhận thông tin khác của từng nút và không có giá trị tìm kiếm.

Ta có giải thuật tìm kiếm trên cây nhị phân tìm kiếm sẽ là như sau:
Tìm kiếm thực hiện trên cây có gốc đuộc trỏ bởi T nút khóa tìm kiếm có giá trị là X, nếu tìm kiếm được thỏa là đưa ra con trỏ q trỏ tới nút đó, nếu tìm kiếm không thỏa thì bổ sung nút mới có khóa là X vào cây và đưa con trỏ q trỏ tới nút đó, đưa ra thông báo: unsuccesfully

Procedure Binary searh tree(T,X,q)

1. khởi tại giá trị cho con trỏ:
2. p=null, q= T.
3. while q#null
4. {
5. case
6. X< key p=q; q= LPTR (q)
7. X= key write successfully
8. X> key p=q; q= RPTR (q)
9. }
10. gọi một nút q mới
11. key (q)= X
12. LPTR (q) = RPTR(q) =null
13. case T = null: T= q
14. X< Key(p) : LPTR (p) = q
15. X> Key(p): RPTR (p)=q
16. else write (unsuccessfull),

- Từ một cây rỗng bừng cách bổ sung liên tục các nút thì ta có thể có một cây nhị phân tìm kiếm ứng với một dãy khóa.

- Chú ý: Ta không thể biết trước cây phát triển ra sao, hình dạng của nó sẽ là thế nào hoặc là một cây nhị phân hoàn chỉ, hoặc là một cây nhị phân gần đầy