Tạo mới cây B-Tree

[cutemutsumi]

Đọc tài liệu về B-Tree, toàn thấy người ta cho sẵn cây B-Tree gòi làm thao tác, nhưng tớ ko biết cách tạo B-Tree.
VD: cho dữ liệu sau để tạo B-Tree bậc 5: 1 2 3 4 5 11 12 13 14 15 6 7 8 9 10 16 17 18 19 20
Sẽ tạo như thế nào? Tạo theo cách tạo cây nhị phân tìm kiếm àh?

[minhmoc]

Trước tiên tìm hiểu lý thuyết nha bạn

Cây là gì?
Cây là một tập hợp T rỗng hoặc gồm nhiều phần tử được gọi là nút, trong đó:
- Một nút được gọi là nút gốc.
- Các nút còn lại được phân chia thành m nhóm (m >= 0) mỗi nhóm là một cây và được gọi là cây con.
Một cây không có một nút nào cả gọi là cây rỗng và được ký hiệu là /\.

Thế còn cây nhị phân?
Bậc của nút là số cây con của nút đó.
Bậc của cây là bậc lớn nhất của các nút của cây. Nếu cây có bậc là n thì ta gọi là cây n-phân.
Vậy cây nhị phân là cây có bậc bằng 2? Đúng vậy.

Và thế nào là cây nhị phân tìm kiếm?
Cây nhị phân tìm kiếm (binary search tree) là cây nhị phân mà tại mỗi nút của cây thì giá trị (thường được gọi là khoá) của nút này lớn hơn khoá của các nút của cây con bên trái và nhỏ hơn khoá của các nút của cây con bên phải của nó.

Nếu ta gọi:
KN - khoá của nút gốc.
KL - khoá của nút con bên trái.
KR - khoá của nút con bên phải.
Thì:
KL < KN < KR

Cấu trúc một nút gồm các trường (thông tin) sau:
- Key (hay Info): chứa nội dung của nút.
- Left: là con trỏ chỉ nút con bên trái.
- Right: là con trỏ chí nút con bên phải.
Việc quản lý cây nhị phân tìm kiếm thông qua con trỏ chỉ nút gốc (Root)

Khai báo kiểu (của một số ngôn ngữ lập trình):
//Pascal
type
ref = ^node;
node = record
Key: integer;
Left,Right: ref;
end;

//C/C++
typedef struct strNode
{
int Key;
strNode *Left, *Right;
}NODE;

//Visual Basic
Type MyNode
Key As Integer
Left As Variant
Right As Variant
End Type

Duyệt cây
Phép duyệt cây là lần lượt đi qua tất cả các nút của cây và mỗi nút chỉ được duyệt một lần.
Có 6 phép duyệt cây dựa vào thứ tự duyệt của các nút bên trái (L), nút gốc (N), các nút bên phải (R) là:
- Thứ tự Preorder: NLR, NRL (nút gốc trước tiên)
- Thứ tự Inorder: LNR, RNL (nút gốc ở giữa)
- Thứ tự Postorder: LRN, RLN (nút gốc sau cùng)
Ta nhận thấy các phép duyệt có tính đối xứng nên ta chỉ xét đến 3 phép duyệt cơ bản là NLR (gốc, trái, phải), LNR (trái, gốc, phải), LRN (trái, phải, gốc).

Tìm kiếm
Đúng như tên gọi cây nhị phân tìm kiếm, cấu trúc của loại cây này giúp cho việc tìm kiếm 1 giá trị trên cây trở nên nhanh chóng và dễ dàng.
Giải thuật tìm kiếm được thực hiện theo các bước như sau:
- Bước 1: Bắt đầu từ nút p là nút gốc.
- Bước 2: Tại nút p này, ta xét:
o Nếu (p->Key = x) thì nút cần tìm là nút p. Giải thuật tìm kiếm kết thúc thành công.
o Nếu (p->Key > x) thì ta đi đến nút con bên trái, gọi là nút q.
o Nếu (p->Key < x) thì ta đi đến nút con bên phải, gọi là nút q.
- Bước 3:
o Nếu (q = NULL) thì giải thuật kết thúc không thành công (không tìm thấy).
o Ngược lại thì cho p = q và lập lại bước 2.

Theo như đề bài bạn nêu ra thì mình nghĩ là sẽ tạo dạng cây nhị phân tìm kiếm. 1 sẽ được cho là Root (gốc), sau đó nó sẽ xét 2, vì 2 > 1 nên 2 sẽ được đưa vào Right của 1, tiếp đến nó xét số 3, vì 3 > 1 nên 3 sẽ đưa vào Right của 1, vì Right của 1 đã có nút 2 nên nó sẽ so sánh tiếp 3 > 2 nên 3 sẽ được đưa vào Right của 2...cứ như vậy đến số 15. Qua đến số 6, lúc đầu nó sẽ so sánh 6 > 1 đưa 6 qua Right của 1, 6 > 2 đưa 6 qua Right của 2...cho đến 6 < 11 thì lúc này 6 sẽ được đưa vào Left của 11...
Bạn cứ tạm hiểu là số đưa vào nếu nhỏ hơn số hiện có thì đưa qua trái, lớn hơn thì đưa qua phải. Đề bài bạn đưa ra nếu tạo cây nhị phân tìm kiếm thì không phải cây bậc 5 mà cây bậc 14 lận, vì 1<2<3<4<5<11<12<13<14<15<16<17<18<19<20 thì nó sẽ tạo ra bấy nhiêu bậc.
Mình có 1 số hình ảnh miêu tả, vì chương trình tạo cây của mình tạo tối đa có 6 bậc nên mình phải cắt ra nhiều phần, mong bạn xem sẽ hiểu.

[expert]

Bạn nào muốn photo cuốn cấu trúc dữ liệu nhị phân nổi tiếng này thì có thể liên hệ với tôi; tôi đã phải bỏ ra 100 USD để mua nó (1024 trang, xuất bản sau 10 năm thai nghén của tác giả Hanan Samet nổi tiếng về chỉ mục cây): Foundations of Multidimensional and Metric Data Structures by Hanan Samet http://www.cs.umd.edu/~hjs/multidime...book-flyer.pdf

[buon_vi_dep_2003]

Giá cả thì sao? Liên hệ thế nào?Chừng nào lấy?Bạn cho thêm thông tin đi bạn nhé!

[boyband2008]

tui cần chỉ giáo phần m-tree

[duabevnh]

Mình đã code lại Btree trên MFC, các bạn cho ý kiến
http://rapidshare.com/files/122124886/B-Tree.rar

[meotrang7x]

B-Tree là cái gì vậy ta?

[tapsu]

Chào

Nếu bạn nào có viết code thì nên chú ý nghiên cứu thêm để làm sao khi cho dữ liệu vào cây luôn được cân bằng, nghĩa là phần trái và phải phải tương xứng nhau.

bye

[cnnedogawa]

Bạn nên tìm hiểu về cây m nhánh trước, B-Tree cũng là một cây nhị phân tìm kiếm nên việc tạo B-Tree cũng phải đảm bảo các tính chất của CNPTK. Tuy nhiên B-Tree có một số đặt điểm cần lưu ý khi tạo:
-Tất cả các cây con rỗng đều thuộc cùng 1 mức
-Số khóa trên 1 node luôn = số nhánh node đó - 1
-Cây B-Tree có tối đa m nhánh thì có tối đa m-1 khóa trên 1 node
-Quan trọng: Nếu bạn thêm khóa vào mà số khóa trên node đó > m-1 thì bạn phải chuyển 1 khóa ở giữa(của node phạm luật) lên nằm chung với node cha của nó(nếu tiếp tục vi phạm thì lặp lại phép chuyển).
Nói ra có vẻ dài dòng nhưng bạn down cái demo của bạn duabevnh về, xóa hết cái cây có sẵn rồi thêm từng node vào thì bạn sẽ hiểu.
Mình còn 1 lưu ý nhỏ về cái khái niệm cây bậc m. Có tài liệu cho là cây B-Tree bậc m thì mỗi node có tối đa 2*m khóa. Tuy nhiên các tài liệu viết theo cây m nhánh thì nói cây B-Tree bậc m là có tối đa m nhánh (tức là tối đa m-1 khóa trên 1 node). Bạn nên xem kỹ cái khái niệm bậc m của tài liệu đang đọc.

[duslidsDign]

Hi,
big thanks for a link!