Query Tree



.

Cấu trúc:

Query Tree:

  • Là một cây nhị phân đầy đủ
  • Mỗi node có 2 hoặc ko có node con nào.
  • Số lượng các node trong QT = số lượng chu kỳ bắt đầu bởi đầu đọc.
  • Đối với node x ko phải là node lá sẽ có 2 node con trái và phải lần lượt: l(x) và r(x)
  • Nếu x là node lá thì: l(x) = r(x) = NIL.

    Đầu chu kỳ, Reader gửi một chuỗi truy vấn thuộc Q, node gốc của QT chính là chuỗi truy vấn . Nếu node x tương ứng với chuỗi truy vấn q thì l(x) và r(x) tương ứng với chuỗi truy vấn q0 và q1. Một node ko phải là lá tương ứng với chuỗi truy vấn tại đó xảy ra xung đột trên kênh truyền. Ngược lại, nếu một node là lá tương ứng với chuỗi truy vấn tại đó ko nhận đc phản hồi nào từ các Tag hoặc chỉ có duy nhất một Tag phản hồi.

aHình 1.          internal node: node xảy ra xung đột

                      white leaf: node ko nhận được phản hồi

                      black leaf: node nhận đc một phản hồi

.

Thuật toán:

    Giống như DBT, thuật toán QT gồm các chu kỳ trong đó Reader truy vấn và các Tag phản hồi. Trong mỗi chu kỳ, Reader truy vấn ID của các Tag với một prefix. Nếu có nhiều hơn 1 Tag phản hồi, ít nhất có 2 Tag có cùng prefix, Reader sẽ thêm 0 hay 1 vào prefix và tiếp tục truy vấn với chuỗi prefix dài hơn. Đến khi chỉ còn 1 Tag phản hồi, ID của Tag đc xác định. Quá trình lặp lại cho đến khi xác định đc tất cả các Tag trong vùng nhận dạng.

capture

capture

hieuunganh-com_589c9ff73b0f7

capture

hieuunganh-com_589ca0f635605

Bảng 1: Quá trình của Query Tree

Ví dụ:

hieuunganh-com_589ca1d0e5314

Hình 2: Query Tree

capture

hieuunganh-com_589ca29b8d8d3

Bảng 2: Ngăn xếp của Bộ đọc

.

.

/sangnx.bkfet


Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: