Tôi vẫn đang nghĩ, nhưng nhanh hơn nhiều so với việc đi ngang qua cây sẽ là position_id cho mọi vị trí có thể. Nếu bạn nhìn vào một cây hoàn chỉnh ở một cấp độ nhất định, bạn sẽ hiểu ý tôi - ví dụ của bạn trông giống như vậy.
Các kết nối giữa position và position_id là một cái gì đó với số học int đơn giản (div và modulo).
Tất cả các nút trong cây con chia sẻ một số thuộc tính đó - ví dụ:các nút con trực tiếp của nút 4 (nút thứ ba ở hàng thứ hai) là số
1 + 5 + (3-1)*5 + 1
1 + 5 + (3-1)*5 + 2
1 + 5 + (3-1)*5 + 3
1 + 5 + (3-1)*5 + 4
1 + 5 + (3-1)*5 + 5
Vì vậy, bạn vẫn phải duyệt qua các mức trong một vòng lặp, nhưng không phải các nút nếu bạn quản lý số vị trí đó trong mọi nút.
Bước 2:
Hàng r có 5 ^ r phần tử (bắt đầu bằng hàng 0).
Lưu trữ trong mọi nút hàng và cột, trong mọi hàng, cột bắt đầu bằng 0. Vì vậy, hàng thứ hai không phải là 2,3,4,5,6 mà là 1 | 0, 1 | 1, 1 | 2, 1 | 3, 1 | 4.
Nếu gốc tìm kiếm của bạn là 1 | 1 (hàng 1, phần tử thứ hai, trong cây đẹp của bạn có tên "3"), thì tất cả các con trong hàng 2 đều có
col / 5 = 1
tất cả trẻ em trong hàng 3 đều có
col / 25 = 1
và như vậy.
Một cấp dưới nút 2 | 10 là nút 3 | (5 * 10) cho đến 3 | (5 * 11-1) =50 .. 55-1
hai cấp bên dưới là các nút 4 | (50 * 5) cho đến 4 | (55 * 5-1)
và như vậy.
Bước 3
Mã giả:
getFreeNode($node){
$rowMax = 100;
$row = $node->row + 1;
$from = 5 * $node->col;
$to = $from + 5;
while($row <= $rowMax){
if ($id = query("select id from member "
."where row = $row and col >= $from and col < $bis"
." and empty_position > 0"))
{
return $id;
}
$row++;
$from *= 5;
$to *= 5;
}
}
insertNode($parent, $node){
$node->row = $parent->row + 1;
$node->col = 5*$parent->col + (5 - $parent->freeNodeCount);
$node->parent_id = $parent->member_id
}
Vui lòng hỏi nếu cần thêm chi tiết.
