Cây nhị phân tìm kiếm

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ t&igrave;m hiểu về c&aacute;ch hoạt động của c&acirc;y nhị ph&acirc;n t&igrave;m kiếm hay Binary Search Tree. Ngo&agrave;i ra, ta sẽ triển khai v&iacute; dụ về c&acirc;y t&igrave;m kiếm nhị ph&acirc;n bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</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 nhị ph&acirc;n t&igrave;m kiếm, tiếng anh l&agrave; Binary Search Tree (BST), l&agrave; một cấu tr&uacute;c dữ liệu cho ph&eacute;p ch&uacute;ng ta nhanh ch&oacute;ng duy tr&igrave; một danh s&aacute;ch c&aacute;c gi&aacute; trị đ&atilde; được sắp xếp.</p> <ul style="text-align: justify;"> <li>N&oacute; được gọi l&agrave; c&acirc;y nhị ph&acirc;n v&igrave; mỗi n&uacute;t c&acirc;y c&oacute; tối đa hai n&uacute;t con.</li> <li>N&oacute; được gọi l&agrave; c&acirc;y t&igrave;m kiếm v&igrave; n&oacute; c&oacute; thể được sử dụng để t&igrave;m kiếm sự hiện diện của một gi&aacute; trị trong thời gian O(log(n)).</li> </ul> <p style="text-align: justify;">C&aacute;c thuộc t&iacute;nh nhằm ph&acirc;n biệt giữa c&acirc;y nhị ph&acirc;n t&igrave;m kiếm v&agrave; c&acirc;y nhị ph&acirc;n th&ocirc;ng thường bao gồm:</p> <ul style="text-align: justify;"> <li>Tất cả c&aacute;c n&uacute;t của c&acirc;y con b&ecirc;n tr&aacute;i đều nhỏ hơn n&uacute;t gốc.</li> <li>Tất cả c&aacute;c n&uacute;t của c&acirc;y con b&ecirc;n phải đều lớn hơn n&uacute;t gốc.</li> <li>Cả hai c&acirc;y con của mỗi n&uacute;t cũng l&agrave; c&acirc;y t&igrave;m kiếm nhị ph&acirc;n BST, tức l&agrave; ch&uacute;ng c&oacute; hai thuộc t&iacute;nh tr&ecirc;n</li> </ul> <p style="text-align: justify;">H&igrave;nh b&ecirc;n dưới đ&acirc;y sẽ minh họa v&iacute; dụ về c&acirc;y nhị ph&acirc;n t&igrave;m kiếm.</p> <p><img style="width: 100%;" src="../../../public_files/b1d2021a-d555-4578-8a6a-52829e5bd2cd" alt="cay-nhi-phan-tim-kiem" /></p> <p style="text-align: justify;">C&acirc;y nhị ph&acirc;n ở b&ecirc;n phải kh&ocirc;ng phải l&agrave; c&acirc;y t&igrave;m kiếm nhị ph&acirc;n v&igrave; c&acirc;y con b&ecirc;n phải của n&uacute;t c&oacute; gi&aacute; trị l&agrave; 3 chứa gi&aacute; trị nhỏ hơn n&oacute;.</p> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. C&aacute;c thao t&aacute;c thực hiện tr&ecirc;n c&acirc;y nhị ph&acirc;n t&igrave;m kiếm</h2> <p style="text-align: justify;">C&oacute; hai thao t&aacute;c cơ bản m&agrave; ta c&oacute; thể thực hiện tr&ecirc;n c&acirc;y nhị ph&acirc;n t&igrave;m kiếm.</p> <h3 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">2.1. Thao t&aacute;c t&igrave;m kiếm</h3> <p style="text-align: justify;">Thuật to&aacute;n phụ thuộc v&agrave;o thuộc t&iacute;nh của c&acirc;y nhị ph&acirc;n t&igrave;m kiếm BST m&agrave; trong đ&oacute;, nếu mỗi c&acirc;y con b&ecirc;n tr&aacute;i c&oacute; gi&aacute; trị nhỏ hơn n&uacute;t gốc v&agrave; mỗi c&acirc;y con b&ecirc;n phải c&oacute; gi&aacute; trị lớn hơn n&uacute;t gốc.</p> <p style="text-align: justify;">Nếu gi&aacute; trị nhỏ hơn n&uacute;t gốc, ch&uacute;ng ta c&oacute; thể chắc chắn rằng gi&aacute; trị đ&oacute; kh&ocirc;ng nằm trong c&acirc;y con b&ecirc;n phải; ch&uacute;ng ta chỉ cần t&igrave;m kiếm trong c&acirc;y con b&ecirc;n tr&aacute;i v&agrave; nếu gi&aacute; trị lớn hơn n&uacute;t gốc, ch&uacute;ng ta c&oacute; thể n&oacute;i chắc chắn rằng gi&aacute; trị đ&oacute; kh&ocirc;ng nằm trong c&acirc;y con b&ecirc;n tr&aacute;i; ch&uacute;ng ta chỉ cần t&igrave;m kiếm trong c&acirc;y con b&ecirc;n phải.</p> <p style="text-align: justify;">Giải thuật như sau:</p> <pre class="language-markup"><code>Nếu n&uacute;t gốc bằng gi&aacute; trị NULL Trả về gi&aacute; trị NULL Nếu gi&aacute; trị cần t&igrave;m bằng gi&aacute; trị lưu trữ trong n&uacute;t gốc Trả về gi&aacute; trị của n&uacute;t gốc Nếu gi&aacute; trị cần t&igrave;m nhỏ hơn gi&aacute; trị lưu trữ trong n&uacute;t gốc Thực hiện t&igrave;m kiếm c&acirc;y con b&ecirc;n tr&aacute;i của n&uacute;t gốc Nếu gi&aacute; trị cần t&igrave;m lớn hơn gi&aacute; trị lưu trữ trong n&uacute;t gốc Thực hiện t&igrave;m kiếm c&acirc;y con b&ecirc;n phải của n&uacute;t gốc</code></pre> <ul> <li>Ch&uacute;ng ta sẽ m&ocirc; h&igrave;nh h&oacute;a n&oacute; như sau:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/90d5f35e-1be1-4215-8566-40e470f6a428" alt="cay-nhi-phan-tim-kiem-2" /></p> <ul> <li>Giả sử gi&aacute; trị cần t&igrave;m l&agrave; 5 trong h&igrave;nh c&acirc;y b&ecirc;n tr&ecirc;n.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/264e5371-a9eb-448f-9d97-7a096a97e5df" alt="cay-nhi-phan-tim-kiem-3" /></p> <ul> <li>V&igrave; kh&ocirc;ng t&igrave;m thấy gi&aacute; trị 5, do đ&oacute;, ta sẽ duyệt qua c&aacute;c n&uacute;t b&ecirc;n tr&aacute;i của n&uacute;t gốc c&oacute; gi&aacute; trị l&agrave; 10.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/1d73b474-6401-413f-a66a-162ad57c1d4c" alt="cay-nhi-phan-tim-kiem-4" /></p> <ul> <li>Kh&ocirc;ng t&igrave;m thấy gi&aacute; trị 5, do đ&oacute;, ta sẽ duyệt qua c&aacute;c n&uacute;t b&ecirc;n phải của n&uacute;t gốc c&oacute; gi&aacute; trị l&agrave; 4.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/65d8394b-3920-4792-a3d4-be9ef103816a" alt="cay-nhi-phan-tim-kiem-5" /></p> <ul> <li>Ta sẽ duyệt qua c&aacute;c n&uacute;t b&ecirc;n phải của n&uacute;t gốc c&oacute; gi&aacute; trị l&agrave; 6.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/75812f2d-a0f1-4312-bee3-33442e277687" alt="cay-nhi-phan-tim-kiem-6" /></p> <ul> <li style="text-align: justify;">V&agrave; cuối c&ugrave;ng l&agrave; ta đ&atilde; t&igrave;m ra được gi&aacute; trị l&agrave; 5.</li> <li style="text-align: justify;">Nếu gi&aacute; trị được t&igrave;m thấy, ch&uacute;ng ta sẽ trả về gi&aacute; trị để n&oacute; được truyền trong mỗi bước đệ quy như thể hiện trong h&igrave;nh dưới đ&acirc;y.</li> <li style="text-align: justify;">Ch&uacute;ng ta đ&atilde; gọi h&agrave;m t&igrave;m kiếm bốn lần. Khi ch&uacute;ng ta trả về n&uacute;t mới hoặc gi&aacute; trị NULL, gi&aacute; trị sẽ được trả về nhiều lần cho đến khi h&agrave;m t&igrave;m kiếm cho n&uacute;t gốc trả về kết quả cuối c&ugrave;ng.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/926b211a-12a8-4eb1-b254-1c374552c4d1" alt="cay-nhi-phan-tim-kiem-7" /></p> <ul> <li style="text-align: justify;">Nếu gi&aacute; trị được t&igrave;m thấy trong bất kỳ c&acirc;y con n&agrave;o, n&oacute; sẽ được truyền l&ecirc;n để cuối c&ugrave;ng n&oacute; được trả về, nếu kh&ocirc;ng th&igrave; trả về gi&aacute; trị l&agrave; NULL.</li> <li style="text-align: justify;">Nếu gi&aacute; trị kh&ocirc;ng được t&igrave;m thấy, cuối c&ugrave;ng ch&uacute;ng ta sẽ đến n&uacute;t con b&ecirc;n tr&aacute;i hoặc b&ecirc;n phải của n&uacute;t l&aacute; l&agrave; NULL v&agrave; n&oacute; được truyền v&agrave; trả về.</li> </ul> <h3 id="ftoc-heading-4" class="ftwp-heading">2.2. Thao t&aacute;c ch&egrave;n</h3> <p style="text-align: justify;">Việc ch&egrave;n một gi&aacute; trị v&agrave;o đ&uacute;ng vị tr&iacute; tương tự như t&igrave;m kiếm v&igrave; ch&uacute;ng ta cố gắng duy tr&igrave; quy tắc c&acirc;y con b&ecirc;n tr&aacute;i nhỏ hơn n&uacute;t gốc v&agrave; c&acirc;y con b&ecirc;n phải c&oacute; gi&aacute; trị lớn hơn gi&aacute; trị của n&uacute;t gốc.</p> <p style="text-align: justify;">Ch&uacute;ng ta tiếp tục đi tới c&acirc;y con b&ecirc;n phải hoặc c&acirc;y con b&ecirc;n tr&aacute;i t&ugrave;y thuộc v&agrave;o gi&aacute; trị v&agrave; khi ch&uacute;ng ta đến một điểm b&ecirc;n tr&aacute;i hoặc b&ecirc;n phải l&agrave; NULL, ch&uacute;ng ta đặt n&uacute;t mới ở đ&oacute;.</p> <p style="text-align: justify;">Thuật to&aacute;n như sau:</p> <pre class="language-markup"><code>Nếu n&uacute;t gốc c&oacute; gi&aacute; trị l&agrave; NULL Trả về h&agrave;m tạo n&uacute;t với gi&aacute; trị cần ch&egrave;n Nếu gi&aacute; trị cần ch&egrave;n nhỏ hơn gi&aacute; trị của n&uacute;t Đi sang c&acirc;y con b&ecirc;n tr&aacute;i Nếu gi&aacute; trị cần ch&egrave;n lớn hơn gi&aacute; trị của n&uacute;t Đi sang c&acirc;y con b&ecirc;n phải Trả về n&uacute;t</code></pre> <ul> <li>Giả sử ta sẽ th&ecirc;m một n&uacute;t mới c&oacute; gi&aacute; trị l&agrave; 5 cho c&acirc;y nhị ph&acirc;n như sau.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/021dcb6d-8fea-4d1a-b4f0-a39e0d3666b9" alt="cay-nhi-phan-tim-kiem-8" /></p> <ul> <li>V&igrave; 5 nhỏ hơn 10, do đ&oacute; ta sẽ di chuyển sang c&acirc;y con b&ecirc;n tr&aacute;i của n&uacute;t gốc c&oacute; gi&aacute; trị l&agrave; 10.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/1e0bc807-29a8-49e5-89a9-399610c6d833" alt="cay-nhi-phan-tim-kiem-9" /></p> <ul> <li>V&igrave; 5 lớn hơn 4, n&ecirc;n ta sẽ di chuyển sang c&acirc;y con b&ecirc;n tr&aacute;i của n&uacute;t gốc c&oacute; gi&aacute; trị l&agrave; 4.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/e2fb20b3-5a13-48d7-a540-f9eef736445f" alt="cay-nhi-phan-tim-kiem-10" /></p> <ul> <li style="text-align: justify;">V&igrave; 5 nhỏ hơn 6, n&ecirc;n ta sẽ di chuyển sang c&acirc;y con b&ecirc;n tr&aacute;i của n&uacute;t gốc c&oacute; gi&aacute; trị l&agrave; 6.</li> <li style="text-align: justify;">V&igrave; kh&ocirc;ng c&oacute; c&acirc;y b&ecirc;n tr&aacute;i của n&uacute;t gốc n&agrave;y, do đ&oacute;, ta sẽ th&ecirc;m n&uacute;t mới c&oacute; gi&aacute; trị l&agrave; 5 tại đ&acirc;y.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/b3916526-013f-432f-9051-f044a57d7d70" alt="cay-nhi-phan-tim-kiem-11" /></p> <ul> <li style="text-align: justify;">Ch&uacute;ng ta đ&atilde; ch&egrave;n th&ecirc;m n&uacute;t nhưng sẽ vẫn phải tho&aacute;t khỏi h&agrave;m m&agrave; kh&ocirc;ng g&acirc;y bất kỳ sự cố n&agrave;o cho phần c&ograve;n lại của c&acirc;y. Đ&acirc;y l&agrave; nơi m&agrave; c&acirc;u lệnh trả về cho n&uacute;t được thực hiện. Trong trường hợp l&agrave; NULL, n&uacute;t mới tạo được trả về v&agrave; gắn v&agrave;o n&uacute;t cha, nếu kh&ocirc;ng th&igrave; n&uacute;t tương tự được trả về m&agrave; kh&ocirc;ng c&oacute; bất kỳ thay đổi n&agrave;o khi ch&uacute;ng ta đi l&ecirc;n cho đến khi ch&uacute;ng ta quay trở lại n&uacute;t gốc.</li> <li style="text-align: justify;">Điều n&agrave;y đảm bảo rằng khi ch&uacute;ng ta duyệt lại c&acirc;y, c&aacute;c kết nối giữa c&aacute;c n&uacute;t kh&aacute;c kh&ocirc;ng bị thay đổi.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/8ae77d9c-395e-4398-a326-90104314232e" alt="cay-nhi-phan-tim-kiem-12" /></p> <h3 id="ftoc-heading-5" class="ftwp-heading">2.3. Thao t&aacute;c x&oacute;a n&uacute;t</h3> <p>C&oacute; ba trường hợp để x&oacute;a một n&uacute;t khỏi c&acirc;y t&igrave;m kiếm nhị ph&acirc;n.</p> <p><strong><em>Trường hợp 1:</em></strong></p> <ul> <li>Trong trường hợp đầu ti&ecirc;n, n&uacute;t bị x&oacute;a l&agrave; n&uacute;t l&aacute;. Trong trường hợp n&agrave;y, chỉ cần x&oacute;a n&uacute;t n&agrave;y khỏi c&acirc;y.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/842611cb-a8ea-4db3-9a11-952e721e1104" alt="cay-nhi-phan-tim-kiem-13" /></p> <ul> <li>11 l&agrave; n&uacute;t cần x&oacute;a, do đ&oacute; ta chỉ cần loại bỏ n&uacute;t n&agrave;y đi.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/855ea700-c510-4fc9-abaa-c00000c30e62" alt="cay-nhi-phan-tim-kiem-14" /></p> <p><strong><em>Trường hợp 2:</em></strong></p> <p>Trong trường hợp thứ hai, n&uacute;t bị x&oacute;a chỉ c&oacute; một n&uacute;t con duy nhất. Trong trường hợp n&agrave;y, ta sẽ l&agrave;m theo c&aacute;c bước như sau:</p> <ul> <li>Thay thế n&uacute;t đ&oacute; bằng n&uacute;t con của n&oacute;.</li> <li>Loại bỏ n&uacute;t con khỏi vị tr&iacute; ban đầu của n&oacute;.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/e662c525-c8e4-4329-a33d-c4f6823e8429" alt="cay-nhi-phan-tim-kiem-15" /></p> <ul> <li>Trong trường hợp n&agrave;y, 6 l&agrave; n&uacute;t cần x&oacute;a.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/471835e1-4c59-4b78-8870-ef6165d91cbb" alt="cay-nhi-phan-tim-kiem-16" /></p> <ul> <li>Sao ch&eacute;p gi&aacute; trị của n&uacute;t con của n&oacute; v&agrave;o ch&iacute;nh n&uacute;t đ&oacute; v&agrave; x&oacute;a n&uacute;t con.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/82953327-9ccf-4eff-abc7-d7ccc8ad36b0" alt="cay-nhi-phan-tim-kiem-17" /></p> <p><strong><em>Trường hợp 3:</em></strong></p> <p>Trong trường hợp thứ ba, n&uacute;t bị x&oacute;a c&oacute; hai n&uacute;t con. Trong trường hợp n&agrave;y, ta sẽ l&agrave;m theo c&aacute;c bước như sau:</p> <ul> <li>Lấy n&uacute;t kế nhiệm nhỏ hơn của n&uacute;t đ&oacute;.</li> <li>Thay thế n&uacute;t bằng n&uacute;t kế nhiệm.</li> <li>Loại bỏ n&uacute;t kế nhiệm khỏi vị tr&iacute; ban đầu của n&oacute;.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/bcf9bc85-17dc-4edc-8ebc-03ac71f77b9e" alt="cay-nhi-phan-tim-kiem-18" /></p> <ul> <li>Trong trường hợp n&agrave;y, 4 l&agrave; n&uacute;t cần x&oacute;a.</li> <li>Sao ch&eacute;p gi&aacute; trị của n&uacute;t kế nhiệm (5) v&agrave;o n&uacute;t n&agrave;y.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/5f3fb31f-828d-4710-aac4-4f1b485a6476" alt="cay-nhi-phan-tim-kiem-19" /></p> <ul> <li>X&oacute;a n&uacute;t kế nhiệm v&agrave; ta c&oacute; được c&acirc;y nhị ph&acirc;n cần t&igrave;m.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/38687fe5-45a0-4d8d-814e-fa8c01714e95" alt="cay-nhi-phan-tim-kiem-20" /></p> <p>V&iacute; dụ: Triển khai c&acirc;y nhị ph&acirc;n bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <pre class="language-c"><code>#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; struct node { int data; struct node *left, *right; }; //Tạo n&uacute;t mới struct node *new_node(int data) { struct node *temp = (struct node *)malloc(sizeof(struct node)); temp-&gt;data = data; temp-&gt;left = temp-&gt;right = NULL; return temp; } //Duyệt c&acirc;y theo thứ tự inorder void inorder(struct node *root) { if (root != NULL) { inorder(root-&gt;left); printf("%d ", root-&gt;data); inorder(root-&gt;right); } } //Th&ecirc;m n&uacute;t mới struct node *add_node(struct node *node, int data) { if (node == NULL) return new_node(data); if (data &lt; node-&gt;data) node-&gt;left = add_node(node-&gt;left, data); else node-&gt;right = add_node(node-&gt;right, data); return node; } //T&igrave;m kiếm n&uacute;t kế nhiệm struct node *minValueNode(struct node *node) { struct node *current = node; while (current &amp;&amp; current-&gt;left != NULL) current = current-&gt;left; return current; } // X&oacute;a n&uacute;t struct node *remove_node(struct node *root, int data) { // Trả về nếu n&uacute;t l&agrave; rỗng if (root == NULL) return root; // T&igrave;m n&uacute;t cần x&oacute;a if (data &lt; root-&gt;data) root-&gt;left = remove_node(root-&gt;left, data); else if (data &gt; root-&gt;data) root-&gt;right = remove_node(root-&gt;right, data); else { // Nếu n&uacute;t chỉ c&oacute; 1 hoặc kh&ocirc;ng c&oacute; n&uacute;t con n&agrave;o if (root-&gt;left == NULL) { struct node *temp = root-&gt;right; free(root); return temp; } else if (root-&gt;right == NULL) { struct node *temp = root-&gt;left; free(root); return temp; } // Nếu n&uacute;t c&oacute; 2 n&uacute;t con struct node *temp = minValueNode(root-&gt;right); // Đặt n&uacute;t kế nhiệm v&agrave;o n&uacute;t cần x&oacute;a root-&gt;data = temp-&gt;data; // X&oacute;a n&uacute;t kế nhiệm root-&gt;right = remove_node(root-&gt;right, temp-&gt;data); } return root; } int main() { struct node *root = NULL; root = add_node(root, 42); root = add_node(root, 12); root = add_node(root, 21); root = add_node(root, 20); root = add_node(root, 100); root = add_node(root, 9); printf("\nDuyệt c&acirc;y theo thứ tự Inorder\n"); inorder(root); printf("\nDuyệt c&acirc;y theo thứ tự Inorder sau khi x&oacute;a n&uacute;t c&oacute; gi&aacute; trị l&agrave; 20\n"); root = remove_node(root, 20); inorder(root); }</code></pre> <p>Kết quả:</p> <div id="urvanov-syntax-highlighter-61068547a6622551382714" class="urvanov-syntax-highlighter-syntax crayon-theme-classic urvanov-syntax-highlighter-font-monaco urvanov-syntax-highlighter-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover"> <div class="crayon-toolbar" data-settings=" mouseover overlay hide delay"> <div class="crayon-tools"> <div class="crayon-button urvanov-syntax-highlighter-popup-button" title="Open Code In New Window"> <div class="urvanov-syntax-highlighter-button-icon"> <pre class="language-python"><code>Duyệt c&acirc;y theo thứ tự Inorder 9 12 20 21 42 100 Duyệt c&acirc;y theo thứ tự Inorder sau khi x&oacute;a n&uacute;t c&oacute; gi&aacute; trị l&agrave; 20 9 12 21 42 100</code></pre> <ul> <li>C&acirc;y nhị ph&acirc;n t&igrave;m kiếm của đoạn m&atilde; b&ecirc;n tr&ecirc;n c&oacute; dạng như sau:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/a30664e0-200a-4f67-9c21-5c356397a262" alt="cay-nhi-phan-tim-kiem-21" /></p> <ul> <li>Sau khi x&oacute;a n&uacute;t 20, ta sẽ c&oacute; c&acirc;y nhị ph&acirc;n t&igrave;m kiếm như sau:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/7c967a54-a018-4900-9e52-b7de5bdefc53" alt="cay-nhi-phan-tim-kiem-22" /></p> <h2 id="ftoc-heading-6" class="ftwp-heading">3. Độ phức tạp của c&acirc;y nhị ph&acirc;n t&igrave;m kiếm</h2> <h3><strong> 3.1. Độ phức tạp về mặt thời gian</strong></h3> <table style="border-collapse: collapse; width: 99.9212%; height: 80px;" border="1"> <tbody> <tr style="height: 14px;"> <td style="width: 11.0497%; height: 14px; text-align: center;">Thao t&aacute;c</td> <td style="width: 28.8871%; height: 14px; text-align: center;">Độ phức tạp của trường hợp tốt nhất</td> <td style="width: 30.7024%; height: 14px; text-align: center;">Độ phức tạp của trường hợp trung b&igrave;nh</td> <td style="width: 29.2818%; height: 14px; text-align: center;">Độ phức tạp của trường hợp xấu nhất</td> </tr> <tr style="height: 22px;"> <td style="width: 11.0497%; height: 22px; text-align: center;">T&igrave;m kiếm n&uacute;t</td> <td style="width: 28.8871%; text-align: center; height: 22px;">O(log n)</td> <td style="width: 30.7024%; text-align: center; height: 22px;">O(log n)</td> <td style="width: 29.2818%; text-align: center; height: 22px;">O(n)</td> </tr> <tr style="height: 22px;"> <td style="width: 11.0497%; height: 22px; text-align: center;">Ch&egrave;n n&uacute;t</td> <td style="width: 28.8871%; text-align: center; height: 22px;">O(log n)</td> <td style="width: 30.7024%; text-align: center; height: 22px;">O(log n)</td> <td style="width: 29.2818%; text-align: center; height: 22px;">O(n)</td> </tr> <tr style="height: 22px;"> <td style="width: 11.0497%; height: 22px; text-align: center;">X&oacute;a n&uacute;t</td> <td style="width: 28.8871%; text-align: center; height: 22px;">O(log n)</td> <td style="width: 30.7024%; text-align: center; height: 22px;">O(log n)</td> <td style="width: 29.2818%; text-align: center; height: 22px;">O(n)</td> </tr> </tbody> </table> <p>Trong đ&oacute;, n l&agrave; số lượng c&aacute;c n&uacute;t c&oacute; trong c&acirc;y.</p> <p><strong>3.2. Độ phức tạp về kh&ocirc;ng gian</strong></p> <p>Độ phức tạp về kh&ocirc;ng gian cho tất cả c&aacute;c thao t&aacute;c tr&ecirc;n c&acirc;y t&igrave;m kiếm nhị ph&acirc;n l&agrave; O(n).</p> <h2 id="ftoc-heading-7" class="ftwp-heading">4. Ứng dụng của c&acirc;y nhị ph&acirc;n t&igrave;m kiếm</h2> <ul> <li>Sử dụng trong việc lập chỉ số đa mức trong cơ sở dữ liệu.</li> <li>Để sắp xếp động.</li> <li>Để quản l&yacute; c&aacute;c v&ugrave;ng bộ nhớ ảo trong nh&acirc;n Unix.</li> </ul> <p>Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về c&acirc;y nhị ph&acirc;n t&igrave;m kiếm. 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> </div> </div> </div> </div> </div>