Xem mã nguồn của Cây van Emde Boas

{| class="infobox" style="width: 20em"
! colspan="2" style="font-size: 125%; text-align: center" | cây van Emde Boas
|-
! [[Danh sách cấu trúc dữ liệu|Thể loại]]
| [[cấu trúc dữ liệu cây|cây]]
|-
! Năm phát minh
| 1977
|-
! Phát minh bởi
| [[Peter van Emde Boas]] 
|-
! colspan="2" style="text-align: center; background-color: #CCCCFF; color: #000000;" | Độ phức tạp<br />theo [[ký hiệu O lớn]]
|-
! Bộ nhớ
| ''O''(''M'')
|-
! Tìm kiếm
| ''O''(log log ''M'')
|-
! Chèn
| ''O''(log log ''M'')
|-
! Xóa
| ''O''(log log ''M'') 
|}

'''Cây van Emde Boas''' (hay '''hàng đợi ưu tiên van Emde Boas'''), còn gọi là cây vEB, là một [[cấu trúc dữ liệu cây]] để biểu diễn [[mảng liên hợp]] có khóa là số tự nhiên ''m'' bit. Nó thực hiện mỗi thao tác trong thời gian O(log ''m''). [[Cấu trúc dữ liệu]] này được tìm ra bởi một nhóm lãnh đạo bởi [[Peter van Emde Boas]] năm 1977.<ref>[[Peter van Emde Boas]], [[R. Kaas]], and [[E. Zijlstra]]: ''Design and Implementation of an Efficient Priority Queue'' (''Mathematical Systems Theory'' 10: 99-127, 1977)</ref>

==Các thao tác==
Cây vEB cho phép thực hiện các thao tác của ''[[mảng liên hợp]] có thứ tự'', bao gồm:<ref>[[Gudmund Skovbjerg Frandsen]]: ''[http://www.daimi.au.dk/~gudmund/dynamicF04/vEB.pdf Dynamic algorithms: Course notes on van Emde Boas trees (PDF)] {{Webarchive|url=https://web.archive.org/web/20150923212438/http://www.daimi.au.dk/~gudmund/dynamicF04/vEB.pdf |date=2015-09-23 }}'' ([[University of Aarhus]], Department of Computer Science)</ref>
*''Chèn'': chèn một cặp khóa/giá trị với 1 khóa ''m'' bit
*''Xóa'': xóa một cặp khóa/giá trị với 1 khóa cho trước
*''Tìm'': tìm giá trị liên hợp với 1 khóa cho trước
*''Tìm phần tử sau'': tìm cặp khóa/giá trị có khóa nhỏ nhất lớn hơn hoặc bằng ''k''
*''Tìm phần tử trước'': tìm cặp khóa/giá trị có khóa lớn nhất nhỏ hơn hoặc bằng ''k''.

==Phương thức hoạt động==
[[Hình:VebDiagram.svg|thumb|alt=Ví dụ cây van Emde Boas|Một cây Van Emde Boas cùng với cấu trúc hỗ trợ của nút gốc sau khi đã chèn 1, 2, 3, 5, 8 và 10.]]

Cho đơn giản, giả sử ''log<sub>2</sub> m = k'' với ''k'' là [[số tự nhiên]]. Giả sử M=2<sup>m</sup>. Một cây vEB ''T'' cho tập hợp {0,..., ''M''-1} có nút gốc chứa 1 mảng mang tên ''T.con'' có kích thước ''M<sup>1/2</sup>''. ''T.con[i]'' là con trỏ đến cây vEB con lưu trữ các giá trị trong khoảng {''iM<sup>1/2</sup>,...,(i+1)M<sup>1/2</sup>-1''}. Ngoài ra ''T'' chứa hai giá trị ''T.min'' và ''T.max'' cùng với một cây vEB hỗ trợ ''T.aux''.

Dữ liệu trong cây vEB được lưu trữ như sau. Giá trị nhỏ nhất được lưu trong ''T.min'' và giá trị lớn nhất được lưu trong ''T.max''. Hai giá trị này không được lưu tại bất kì nơi nào khác trong cây. Nếu ''T'' là rỗng, ta quy ước ''T.max=-1'' và ''T.min=M''. Các giá trị còn lại được lưu trong các cây con. Giá trị ''x'' được lưu trong cây con ''T.con[i]'' trong đó <math>i=\lfloor x/M^{1/2}\rfloor</math>. Cây hỗ trợ ''T.aux'' lưu trữ các cây con khác rỗng. Nghĩa là ''T.aux'' chứa giá trị ''j'' khi và chỉ khi ''T.con[j]'' là khác rỗng.

==Tham khảo==
* Erik Demaine, Shantonu Sen, and Jeff Lindy. Massachusetts Institute of Technology. 6.897: Advanced Data Structures (Spring 2003). [http://theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L1/lecture1.pdf Lecture 1 notes: Fixed-universe successor problem, van Emde Boas]. [http://theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L2/lecture2.pdf Lecture 2 notes: More van Emde Boas,...].
==Ghi chú==
{{Tham khảo}}

{{Cây trong khoa học máy tính}}

[[Thể loại:Cây (cấu trúc)]]