Tôi đã gặp loại vấn đề sau. Cần phải triển khai bộ chứa lưu trữ dữ liệu cung cấp các chức năng sau:
- chèn phần tử mới
- xóa phần tử theo số sê-ri
- lấy phần tử theo số thứ tự
- dữ liệu được lưu trữ ở dạng được sắp xếp
Dữ liệu liên tục được thêm bớt, kết cấu phải đảm bảo tốc độ hoạt động nhanh. Lúc đầu, tôi đã cố gắng thực hiện điều đó bằng cách sử dụng các vùng chứa tiêu chuẩn từ tiêu chuẩn. Con đường này không thành công và tôi nhận ra rằng tôi cần phải tự mình thực hiện một điều gì đó. Điều duy nhất tôi nghĩ đến là sử dụng cây tìm kiếm nhị phân. Vì nó đáp ứng được yêu cầu chèn, xóa và lưu trữ dữ liệu dưới dạng đã sắp xếp nhanh chóng. Tất cả những gì còn lại là tìm ra cách lập chỉ mục cho tất cả các phần tử và tính toán lại các chỉ số khi cây thay đổi.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Bài viết sẽ chứa nhiều hình ảnh và lý thuyết hơn là code. Mã có thể được xem tại liên kết dưới đây.
Trọng lượng
Để đạt được điều này, cây đã trải qua một sự sửa đổi nhỏ, thêm thông tin bổ sung về cân nặng nút. Trọng lượng nút là số lượng con cháu của nút này + 1 (trọng lượng của một phần tử).
Chức năng lấy trọng lượng nút:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Trọng lượng của tấm tương ứng bằng 0.
Tiếp theo, chúng ta hãy chuyển sang phần trình bày trực quan của một ví dụ về một cái cây như vậy. Đen khóa nút sẽ được hiển thị bằng màu (giá trị sẽ không được hiển thị vì điều này không cần thiết), đỏ - trọng lượng nút thắt, xanh - chỉ số nút.
Khi cây của chúng ta trống, trọng số của nó là 0. Hãy thêm phần tử gốc vào nó:
Trọng số của cây trở thành 1, trọng số của phần tử gốc trở thành 1. Trọng số của phần tử gốc là trọng số của cây.
Hãy thêm một vài yếu tố nữa:
Mỗi khi một phần tử mới được thêm vào, chúng ta sẽ đi xuống các nút và tăng bộ đếm trọng số của mỗi nút được truyền. Khi một nút mới được tạo, trọng số sẽ được gán cho nút đó 1. Nếu một nút có khóa như vậy đã tồn tại thì chúng tôi sẽ ghi đè giá trị và quay trở lại gốc, hủy các thay đổi về trọng số của tất cả các nút mà chúng tôi đã chuyển qua.
Nếu một nút đang bị xóa thì chúng tôi sẽ đi xuống và giảm trọng số của các nút đã truyền.
Chỉ số
Bây giờ hãy chuyển sang cách lập chỉ mục các nút. Các nút không lưu trữ chỉ mục của chúng một cách rõ ràng, nó được tính toán dựa trên trọng số của các nút. Nếu họ lưu trữ chỉ mục của mình thì nó sẽ được yêu cầu O (n) thời gian để cập nhật chỉ mục của tất cả các nút sau mỗi lần thay đổi trong cây.
Hãy chuyển sang một đại diện trực quan. Cây của chúng ta trống, hãy thêm nút đầu tiên vào nó:
Nút đầu tiên có một chỉ mục 0, và lúc này có 2 trường hợp có thể xảy ra. Trong lần đầu tiên, chỉ mục của phần tử gốc sẽ thay đổi, trong lần thứ hai nó sẽ không thay đổi.
Tại gốc, cây con bên trái nặng 1.
Trường hợp thứ hai:
Chỉ số của gốc không thay đổi vì trọng số của cây con bên trái của nó vẫn bằng 0.
Chỉ số của một nút được tính bằng trọng số của cây con bên trái của nó + số được truyền từ nút cha. Con số này là gì?, Đây là bộ đếm chỉ số, ban đầu nó bằng 0, bởi vì gốc không có cha mẹ. Sau đó, tất cả phụ thuộc vào việc chúng ta đi xuống con bên trái hay bên phải. Nếu ở bên trái thì không có gì được thêm vào bộ đếm. Nếu chúng ta thêm chỉ mục của nút hiện tại vào nút bên phải.
Ví dụ: cách tính chỉ mục của một phần tử có khóa 8 (con bên phải của gốc). Đây là "Root Index" + "trọng lượng của cây con bên trái của nút có khóa 8" + "1" == 3 + 2 + 1 == 6
Chỉ mục của phần tử có khóa 6 sẽ là "Root Index" + 1 == 3 + 1 == 4
Theo đó, cần có thời gian để lấy và xóa một phần tử theo chỉ mục O (log n), vì để có được phần tử mong muốn trước tiên chúng ta phải tìm nó (đi từ gốc đến phần tử này).
Độ sâu
Dựa vào trọng lượng, bạn cũng có thể tính được độ sâu của cây. Cần thiết cho việc cân bằng.
Để làm điều này, trọng số của nút hiện tại phải được làm tròn thành số đầu tiên lũy thừa 2, lớn hơn hoặc bằng trọng số đã cho và lấy logarit nhị phân từ nó. Điều này sẽ cho chúng ta độ sâu của cây, giả sử nó cân bằng. Cây được cân bằng sau khi chèn một phần tử mới. Tôi sẽ không đưa ra lý thuyết về cách cân bằng cây. Các mã nguồn cung cấp chức năng cân bằng.
Mã để chuyển đổi trọng lượng sang độ sâu.
/*
* Возвращает первое число в степени 2, которое больше или ровно x
*/
uint64_t bntree::cpl2(uint64_t x) {
x = x - 1;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
x = x | (x >> 32);
return x + 1;
}
/*
* Двоичный логарифм от числа
*/
long bntree::ilog2(long d) {
int result;
std::frexp(d, &result);
return result - 1;
}
/*
* Вес к глубине
*/
uint64_t bntree::weight_to_depth(node_t *p) {
if (p == NULL) {
return 0;
}
if (p->weight == 1) {
return 1;
} else if (p->weight == 2) {
return 2;
}
return this->ilog2(this->cpl2(p->weight));
}Kết quả
- việc chèn một phần tử mới xảy ra trong O (log n)
- việc xóa một phần tử theo số sê-ri xảy ra trong O (log n)
- việc lấy một phần tử theo số sê-ri xảy ra trong O (log n)
tốc độ O (log n) Chúng tôi trả tiền vì thực tế là tất cả dữ liệu được lưu trữ ở dạng được sắp xếp.
Tôi không biết cấu trúc như vậy có thể hữu ích ở đâu. Chỉ là một câu đố để một lần nữa hiểu được cây cối hoạt động như thế nào. Cám ơn vì sự quan tâm của bạn.
tài liệu tham khảo
Dự án chứa dữ liệu thử nghiệm để kiểm tra tốc độ hoạt động. Cây đang lấp đầy 1000000 các phần tử. Và có thao tác xóa, chèn và truy xuất tuần tự các phần tử 1000000 một lần. Đó là 3000000 hoạt động. Kết quả hóa ra khá tốt ~ 8 giây.
Nguồn: www.habr.com