Splay Tree và ứng dụng

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về cấu tr&uacute;c dữ liệu c&acirc;y Splay hay Splay tree. Ngo&agrave;i ra, ta sẽ triển khai c&acirc;y Splay bằng ng&ocirc;n ngữ lập tr&igrave;nh C, v&agrave; minh họa kiểu cấu tr&uacute;c dữ liệu n&agrave;y bằng c&aacute;c h&igrave;nh ảnh minh họa.</p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">C&acirc;y Splay l&agrave; một c&acirc;y t&igrave;m kiếm nhị ph&acirc;n tự c&acirc;n bằng nhằm cung cấp khả năng truy cập nhanh v&agrave;o c&aacute;c phần tử được truy cập thường xuy&ecirc;n trong c&acirc;y. C&acirc;y thực hiện c&aacute;c thao t&aacute;c ch&iacute;nh như ch&egrave;n, t&igrave;m kiếm v&agrave; x&oacute;a n&uacute;t trong c&acirc;y. C&acirc;y Splay thực hiện c&aacute;c thao t&aacute;c cơ bản n&agrave;y kết hợp với thao t&aacute;c Splay.</p> <p style="text-align: justify;">Splaying bao gồm việc sắp xếp lại c&acirc;y để đưa một phần tử nhất định v&agrave;o n&uacute;t gốc của c&acirc;y. Điều n&agrave;y được thực hiện bằng c&aacute;ch sử dụng thao t&aacute;c c&acirc;y t&igrave;m kiếm nhị ph&acirc;n ti&ecirc;u chuẩn (BST) kết hợp với ph&eacute;p xoay cho c&acirc;y để đưa phần tử v&agrave;o n&uacute;t gốc của c&acirc;y. C&aacute;c ph&eacute;p xoay n&agrave;y sẽ kh&ocirc;ng l&agrave;m thay đổi thuộc t&iacute;nh BST của c&acirc;y.</p> <p id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;"><strong>Ưu điểm của c&acirc;y Splay:</strong></p> <ul style="text-align: justify;"> <li>C&acirc;y Splay đảm bảo rằng c&aacute;c phần tử được truy cập thường xuy&ecirc;n ở gần n&uacute;t gốc của c&acirc;y để ch&uacute;ng c&oacute; thể dễ d&agrave;ng truy cập.</li> <li>Hiệu suất trường hợp trung b&igrave;nh của c&acirc;y Splay c&oacute; thể tương đương với c&aacute;c c&acirc;y c&acirc;n bằng kh&aacute;c l&agrave; O(log\space n) O(log n).</li> <li>C&acirc;y splay kh&ocirc;ng cần dữ liệu lưu trữ, do đ&oacute;, n&oacute; chỉ c&oacute; một kh&ocirc;ng gian bộ nhớ nhỏ.</li> </ul> <p id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;"><strong>Nhược điểm:</strong></p> <ul style="text-align: justify;"> <li>Nhược điểm lớn của c&acirc;y Splay l&agrave; việc tự sắp xếp tuyến t&iacute;nh. Do đ&oacute;, hiệu suất trong trường hợp xấu nhất của c&acirc;y Splay sẽ l&agrave; O(n).</li> <li>C&aacute;c hoạt động đa luồng c&oacute; thể g&acirc;y ra sự phức tạp v&igrave; ngay cả trong qu&aacute; tr&igrave;nh chỉ đọc, c&acirc;y Splay cũng sẽ tự sắp xếp lại.</li> </ul> <h2 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">2. C&aacute;c thao t&aacute;c tr&ecirc;n Splay Tree</h2> <p style="text-align: justify;">Sau khi một phần tử được truy cập, thao t&aacute;c Splay sẽ được thực hiện, đưa phần tử đ&oacute; về n&uacute;t gốc của c&acirc;y. Nếu phần tử kh&ocirc;ng nằm ở vị tr&iacute; của n&uacute;t gốc, Splaying c&oacute; thể c&oacute; một trong ba bước như sau:</p> <ol style="text-align: justify;"> <li>Bước zig (hoặc zag)</li> <li>Bước zig-zig (hoặc zag-zag)</li> <li>Bước zig-zag (hoặc zag-zig)</li> </ol> <p style="text-align: justify;">C&aacute;c bước m&agrave; ta thực hiện sẽ phụ thuộc v&agrave;o vị tr&iacute; của n&uacute;t. Nếu n&uacute;t l&agrave; n&uacute;t gốc, n&oacute; sẽ được trả về ngay lập tức.</p> <h3 id="ftoc-heading-5" class="ftwp-heading" style="text-align: justify;">2.1. Zig (hoặc zag)</h3> <p style="text-align: justify;">Khi kh&ocirc;ng c&oacute; n&uacute;t &ocirc;ng (n&uacute;t cha của n&uacute;t cha) n&agrave;o tồn tại, thao t&aacute;c Splay sẽ di chuyển n&uacute;t đ&oacute; đến n&uacute;t cha chỉ với một lần xoay. Xoay b&ecirc;n tr&aacute;i l&agrave; đường zag v&agrave; xoay b&ecirc;n phải l&agrave; đường zig.</p> <p style="text-align: justify;"><strong>Ch&uacute; &yacute;: Việc xoay b&ecirc;n tr&aacute;i tương ứng với vị tr&iacute; b&ecirc;n phải (n&uacute;t l&agrave; n&uacute;t b&ecirc;n phải của n&uacute;t cha) v&agrave; ngược lại.</strong></p> <p><strong><img style="width: 100%;" src="../../../public_files/14a89a57-364b-4957-97dd-5701cddf8d21" alt="cay-splay" /></strong></p> <h3 id="ftoc-heading-6" class="ftwp-heading">2.2. Zig-zig (hoặc zag-zag)</h3> <p style="text-align: justify;">Khi một n&uacute;t &ocirc;ng v&agrave; n&uacute;t cha tồn tại v&agrave; được đặt theo một hướng giống nhau (V&iacute; dụ, n&uacute;t cha ở b&ecirc;n tr&aacute;i của n&uacute;t &ocirc;ng v&agrave; n&uacute;t hiện tại nằm b&ecirc;n tr&aacute;i của n&uacute;t cha), th&igrave; thao t&aacute;c sẽ l&agrave; zig-zig (tr&aacute;i) hoặc zag-zag (phải ).</p> <p><img style="width: 100%;" src="../../../public_files/6cdc2773-d103-4121-827e-de9fa8537607" alt="cay-splay-3" /><img style="width: 100%;" src="../../../public_files/6a8b6d81-5e3b-40da-8927-ffe8aa013827" alt="cay-splay-2" /></p> <h3 id="ftoc-heading-7" class="ftwp-heading">2.3. Zig-zag (hoặc zag-zig)</h3> <p style="text-align: justify;">Một thao t&aacute;c zig-zag sẽ tương ứng với n&uacute;t cha nằm ở b&ecirc;n tr&aacute;i của n&uacute;t &ocirc;ng v&agrave; n&uacute;t b&ecirc;n phải của n&uacute;t cha. Một thao t&aacute;c zag-zig th&igrave; sẽ ngược lại.</p> <p><img style="width: 100%;" src="../../../public_files/c6b400d5-efed-42f4-8696-47e3212b09e4" alt="cay-splay-5" /><img style="width: 100%;" src="../../../public_files/39bc79b5-dae6-4451-8fbd-9ed2901f7355" alt="cay-splay-4" /></p> <p>V&iacute; dụ: Triển khai Splay tree bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <pre class="language-cpp"><code>#include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; struct node { int data; struct node *left, *right; }; struct node* create_node(int data) { struct node* new_node = (struct node*)malloc(sizeof(struct node)); new_node-&gt;data = data; new_node-&gt;left = new_node-&gt;right = NULL; return (new_node); } struct node *right_rotation(struct node *x) { struct node *y = x-&gt;left; x-&gt;left = y-&gt;right; y-&gt;right = x; return y; } struct node *left_rotation(struct node *x) { struct node *y = x-&gt;right; x-&gt;right = y-&gt;left; y-&gt;left = x; return y; } struct node *splaying(struct node *root, int data) { if (root == NULL || root-&gt;data == data) return root; if (root-&gt;data &gt; data) { if (root-&gt;left == NULL) return root; if (root-&gt;left-&gt;data &gt; data) { root-&gt;left-&gt;left = splaying(root-&gt;left-&gt;left, data); root = right_rotation(root); } else if (root-&gt;left-&gt;data &lt; data) { root-&gt;left-&gt;right = splaying(root-&gt;left-&gt;right, data); if (root-&gt;left-&gt;right != NULL) root-&gt;left = left_rotation(root-&gt;left); } return (root-&gt;left == NULL)? root: right_rotation(root); } else { if (root-&gt;right == NULL) return root; if (root-&gt;right-&gt;data &gt; data) { root-&gt;right-&gt;left = splaying(root-&gt;right-&gt;left, data); if (root-&gt;right-&gt;left != NULL) root-&gt;right = right_rotation(root-&gt;right); } else if (root-&gt;right-&gt;data &lt; data) { root-&gt;right-&gt;right = splaying(root-&gt;right-&gt;right, data); root = left_rotation(root); } return (root-&gt;right == NULL)? root: left_rotation(root); } } struct node *find_node(struct node *root, int data) { return splaying(root, data); } struct node *add_node(struct node *root, int k) { if (root == NULL) return create_node(k); root = splaying(root, k); if (root-&gt;data == k) return root; struct node *new_node = create_node(k); if (root-&gt;data &gt; k) { new_node-&gt;right = root; new_node-&gt;left = root-&gt;left; root-&gt;left = NULL; } else { new_node-&gt;left = root; new_node-&gt;right = root-&gt;right; root-&gt;right = NULL; } return new_node; } struct node* delete_data(struct node *root, int data){ struct node *temp; if (!root) return NULL; root = splaying(root, data); if (data != root-&gt;data) return root; if (!root-&gt;left) { temp = root; root = root-&gt;right; } else { temp = root; root = splaying(root-&gt;left, data); root-&gt;right = temp-&gt;right; } free(temp); return root; } void preOrder(struct node *root) { if (root != NULL) { printf("%d ", root-&gt;data); preOrder(root-&gt;left); preOrder(root-&gt;right); } } int main() { struct node *root = create_node(89); root-&gt;left = create_node(38); root-&gt;right = create_node(100); root-&gt;left-&gt;left = create_node(38); root-&gt;left-&gt;left-&gt;left = create_node(24); root-&gt;left-&gt;left-&gt;left-&gt;left = create_node(16); preOrder(root); printf("\n"); root = find_node(root, 10); int data = 24; root = delete_data(root, data); printf("\n"); preOrder(root); root = add_node(root, 27); printf("\n"); preOrder(root); return 0; }</code></pre> <p>Kết quả:</p> <pre class="language-cpp"><code>89 38 38 24 16 100 16 38 38 89 100 27 16 38 38 89 100</code></pre> <h2 id="ftoc-heading-8" class="ftwp-heading" style="text-align: justify;">3. Ứng dụng của c&acirc;y Splay</h2> <ul style="text-align: justify;"> <li>Splay tree sẽ rất hữu &iacute;ch tr&ecirc;n c&aacute;c cấu tr&uacute;c dữ liệu được sửa đổi thường xuy&ecirc;n. V&iacute; dụ ckassic l&agrave; cấu tr&uacute;c dữ liệu dạng c&acirc;y gồm c&aacute;c đoạn chuỗi, đ&acirc;y l&agrave; một c&aacute;ch để cố gắng tối ưu h&oacute;a tr&igrave;nh soạn thảo văn bản bằng c&aacute;ch loại bỏ c&aacute;c bản sao ch&eacute;p lớn. So với thuật to&aacute;n c&acirc;y c&acirc;n bằng tất định như RB-tree, thuật to&aacute;n c&acirc;y Splay c&oacute; ưu thế hơn.</li> <li>Một v&iacute; dụ kh&aacute;c l&agrave; bộ định tuyến mạng. Một bộ định tuyến mạng nhận c&aacute;c g&oacute;i mạng với tốc độ cao từ c&aacute;c kết nối đến v&agrave; phải nhanh ch&oacute;ng quyết định chọn đường đi n&agrave;o để gửi từng g&oacute;i, dựa tr&ecirc;n địa chỉ IP trong g&oacute;i. Bộ định tuyến cần một bảng lớn c&oacute; thể được sử dụng để tra cứu địa chỉ IP v&agrave; t&igrave;m ra kết nối để sử dụng. Nếu một địa chỉ IP đ&atilde; được sử dụng một lần, n&oacute; c&oacute; khả năng được sử dụng lại, c&oacute; thể l&agrave; nhiều lần. Splay tree c&oacute; thể mang lại hiệu quả tốt trong t&igrave;nh huống n&agrave;y.</li> </ul> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về cấu tr&uacute;c dữ liệu c&acirc;y Splay. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="../../../">tek4</a>&nbsp;nh&eacute;!</p>