Thuật toán Tree-based chung



4

Hình  1. Cấu trúc Binary Search với m = 5, k = 4.

    Giả thiết đây là cây nhị phân đầy: tức các nút có 2 con với 2 giá trị 0 và 1 & các nút lá ở cùng mức.

    Cây có chiều cao là k thì số nút của cây là N = 2^(k+1) – 1 ==> k = log2(N+1) – 1.

Thuật toán:

n:  số lượng thẻ có thể có

k:  độ dài của ID của thẻ, cũng là chiều cao của cây nhị phân.

k = log 2 n

m:  số lượng thẻ nằm trong vùng năng lượng của bộ đọc (m <= n)

N xy : node thứ y (tính từ trái qua) có chiều cao x trong cây nhị phân.

T xy : cây con (subtree) mà node gốc của nó là N xy

Thuật toán đc xét như sau:

Bước 1:  Bắt đầu với node gốc của cây N 00 , mọi thẻ thuộc cây con T 00 gửi dữ liệu (ID) tại slot thời gian ứng với N00

Bước 2:  Nếu có từ 2 thẻ trở lên trong cây con T00 thì xung đột xảy ra tại node N00 , qua bc 3.

Bước 3:           T x = T 10

T y = T 11

5

.                Chiều cao

Hình  2. Cấu trúc Binary Tree ( với k = 3, m = 4 )

Bước 4:

Mọi thẻ thuộc cây con Tx gửi dữ liệu tại slot thời gian ứng với N10 .

Sau đó mọi thẻ thuộc cây con Ty gửi dữ liệu tại slot thời gian ứng với N11 .

Bước 5:  Nếu có bất kỳ xung đột nào xảy ra ở Bước 4:

  • Cho đến khi xung đột này được giải quyết, ko có thẻ nào được phép gửi dữ liệu mới.
  • Giải quyết xung đột ở Tx trước khi giải quyết xung đột ở Ty .

    Một xung đột trong Tx (hay Ty) đc giải quyết bằng cách chia Tx (hay Ty) thành 2 cây con A và B, gán Tx = A và Ty = B rồi lặp lại Bước 4 và Bước 5.

/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: