Skip to content
Home » Cây Nhị Phân Tìm Kiếm | Thao Tác Thêm

Cây Nhị Phân Tìm Kiếm | Thao Tác Thêm

Cấu trúc dữ liệu & Giải thuật [15]: #Tree #BinaryTree #BinarySearchTree

Tham khảo[sửa | sửa mã nguồn]

  • Donald Knuth. The Art of Compter Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.2.2: Binary Tree Searching, pp. 426–458.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 12: Binary search trees, pp. 253–272. Section 15.5: Optimal binary search trees, pp. 356–363.

Các phép toán trên BST[sửa | sửa mã nguồn]

Tìm kiếm (Searching)[sửa | sửa mã nguồn]

Việc tìm một khóa trên BST có thể thực hiện nhờ đệ quy. Chúng ta bắt đầu từ gốc. Nếu khóa cần tìm bằng khóa của gốc thì khóa đó trên cây, nếu khóa cần tìm nhỏ hơn khóa ở gốc, ta phải tìm nó trên cây con trái, nếu khóa cần tìm lớn hơn khóa ở gốc, ta phải tìm nó trên cây con phải. Nếu cây con (trái hoặc phải) là rỗng thì khóa cần tìm không có trên cây.

Giả mã

Search_binary_tree(node, key);



if node is Null then return None; /* key not found */ if key < node.key: return search binary_tree(node.left, key); else if key > node.key return search_binary_tree(node.right, key) else /* key is equal to node key */ return node.value; # found key

Mã Python:


def search_binary_tree(node, key): if node is None: return None # key not found if key < node.key: return search_binary_tree(node.leftChild, key) elif key > node.key: return search_binary_tree(node.rightChild, key) else: # key is equal to node key return node.value # found key

Thời gian tìm kiếm trung bình là O(log 2n), và là O(n) khi cây là không cân bằng chỉ là một danh sách liên kết.

Chèn (Insertion)[sửa | sửa mã nguồn]

Phép chèn bắt đầu giống như phép tìm kiếm; Nếu khóa của gốc khác khóa cần chèn ta tìm nó trong cây con trái hoặc phải. Nếu cây con trái hoặc phải tương ứng là rỗng (không tìm thấy) thì thêm một nút và gán cho nút ấy khóa cần chèn.

Sau đây là mã trong C++:


void InsertNode(struct node *&treeNode, struct node *newNode) { //Inserts node pointered by "newNode" to the subtree started by "treeNode" if (treeNode == NULL) treeNode = newNode; //Only changes "node" when it is NULL else if (newNode->value < treeNode->value) InsertNode(treeNode->left, newNode); else InsertNode(treeNode->right, newNode); }

Mã Python:


def binary_tree_insert(node, key, value): if node is None: return TreeNode(None, key, value, None) if key == node.key: return TreeNode(node.left, key, value, node.right) if key < node.key: return TreeNode(binary_tree_insert(node.left, key, value), node.key, node.value, node.right) else: return TreeNode(node.left, node.key, node.value, binary_tree_insert(node.right, key, value))

Xóa (Deletion)[sửa | sửa mã nguồn]

Xét các trường hợp sau

  • Xóa một lá: Vì lá không có con nên chỉ cần giải phóng nó khỏi cây.
  • Xóa nút có một con: Xóa và thay thế nó bằng con duy nhất của nó.
  • Xóa một nút có hai con: Xóa nút đó và thay thế nó bằng nút có khóa lớn nhất trong các khóa nhỏ hơn khóa của nó (được gọi là “nút tiền nhiệm” -nút cực phải của cây con trái) hoặc nút có khóa nhỏ nhất trong các khóa lớn hơn nó (được gọi là “nút kế vị” – nút cực trái của cây con phải)

Cũng có thể tìm nút tiền nhiệm hoặc nút kế vị đổi chỗ nó với nút cần xóa và sau đó xóa nó. Vì các nút kiểu này có ít hơn hai con nên việc xóa nó được quy về hai trường hợp trước.

Sau đây là mã C++


void DeleteNode(struct node*& node) { if (node->left == NULL) { struct node* temp = node; node = node->right; delete temp; } else if (node->right == NULL) { struct node* temp = node; node = node->left; delete temp; } else { // In-Order predecessor(right most child of left subtree) // Node has two children - get max of left subtree struct node** temp = &(node->left); // get left node of the original node // find the right most child of the subtree of the left node while ((*temp)->right != NULL) { temp = &((*temp)->right); } // copy the value from the right most child of left subtree to the original node node->value = (*temp)->value; // then delete the right most child of left subtree since it's value is // now in the original node DeleteNode(*temp); } }

Mã python:


def findMin(self): ''' Finds the smallest element that is a child of *self* ''' current_node = self while current_node.left_child: current_node = current_node.left_child return current_node def replace_node_in_parent(self, new_value=None): ''' Removes the reference to *self* from *self.parent* and replaces it with *new_value*. ''' if self == self.parent.left_child: self.parent.left_child = new_value else: self.parent.right_child = new_value if new_value: new_value.parent = self.parent def binary_tree_delete(self, key): if key < self.key: self.left_child.binary_tree_delete(key) elif key > self.key: self.right_child.binary_tree_delete(key) else: # delete the key here if self.left_child and self.right_child: # if both children are present # get the smallest node that's bigger than *self* successor = self.right_child.findMin() self.key = successor.key # if *successor* has a child, replace it with that # at this point, it can only have a *right_child* # if it has no children, *right_child* will be "None" successor.replace_node_in_parent(successor.right_child) elif self.left_child or self.right_child: # if the node has only one child if self.left_child: self.replace_node_in_parent(self.left_child) else: self.replace_node_in_parent(self.right_child) else: # this node has no children self.replace_node_in_parent(None)

Phép duyệt[sửa | sửa mã nguồn]

Khi một cây tìm kiếm nhị phân được tạo ra, tất cả các nút có thể được duyệt theo thứ tự giữa nhờ duyệt đệ quy cây con bên trái, in nút đang duyệt, rồi duyệt đệ quy cây con bên phải, tiếp tục làm như vây với mỗi nút của cây trong quá trình đệ quy. Với mọi cây nhị phân, cây có thể được duyệt theo thứ tự trước() hoặc theo thứ tự sau(), cả hai cách đều hữu dụng với cây tìm kiếm nhị phân.

Đoạn mã cho duyệt theo thứ giữa được viết dưới đây với C++:


void traverse_binary_tree(struct node* n) { if(n==null) //Cay rong return NULL; else { traverse_binary_tree(n->left); //Duyet cay con trai theo thu tu giua printf("%d",n.key); //Tham nut traverse_binary_tree(n->right); //Duyet cay con phai theo thu tu giua } }

Phép duyệt có độ phức tạp tính toán là Ω(n), vì nó phải duyệt qua tất cả các nút. Độ phức tạp trên cũng là O(“n”).

Sắp xếp[sửa | sửa mã nguồn]

Một cây tìm kiếm nhị phân có thể được sử dụng như một giải thuật sắp xếp đơn giản nhưng hiểu quả. Giống như heapsort, chúng ta chèn tất cả các giá trị chúng ta muốn sắp xếp vào một cây tìm kiếm nhị phân và in ra kết quả theo thứ tự:


def build_binary_tree(values): tree = None for v in values: tree = binary_tree_insert(tree, v) return tree def get_inorder_traversal(root): ''' Returns a list containing all the values in the tree, starting at *root*. Traverses the tree in-order(leftChild, root, rightChild). ''' result = [] traverse_binary_tree(root, lambda element: result.append(element)) return result

Trường hợp xấu nhất của

build_binary_tree

có độ phức tạp là —nếu nhập vào một dãy giá trị đã sắp xếp, cây nhị phân tạo thành sẽ không có các nút trái. Ví dụ,

traverse_binary_tree([1, 2, 3, 4, 5])

tạo thành cây

(1 (2 (3 (4 (5)))))

.

Có một vài cách để vượt qua trường hợp này với các cây nhị phân đơn giản; cách đơn giản nhất là cây tìm kiếm nhị phân tự cân bằng. Với thủ tục này được sử dụng với cây nhị phân tự cân bằng, trường hợp xấu nhất sẽ có độ phức tạp là O(nlog n).

Cấu trúc dữ liệu & Giải thuật [15]: #Tree #BinaryTree #BinarySearchTree
Cấu trúc dữ liệu & Giải thuật [15]: #Tree #BinaryTree #BinarySearchTree

Ví dụ chương trình C++ thao tác với cây nhị phân tìm kiếm

Cho cây nhị phân tìm kiếm như hình bên dưới.

Chương trình C++ thao tác với cây nhị phân tìm kiếm như hình trên


#include

using namespace std; struct tNode{ int data; tNode *pLeft, *pRight; }; tNode *root; //create empty tree void createEmptyTree(){ root = NULL; } //create new node tNode *newNode(int data){ tNode *node = new tNode; if(node==NULL){//cannot allocate memory exit(1); }else{ node->data = data; node->pLeft = NULL; node->pRight = NULL; } return node; } //insert new Node into tree tNode *insertNode(tNode *node, int value){ if(node!=NULL){ if(node->data == value){ return node; }else if(node->data > value){ node->pLeft = insertNode(node->pLeft, value); }else{ node->pRight = insertNode(node->pRight, value); } }else{ node = newNode(value); } return node; } void NLR(tNode *root){ if(root!=NULL){ if(root!=NULL){ cout<

data<<" "; } NLR(root->pLeft); NLR(root->pRight); } } tNode *searchNodeByRecursion(tNode *root, int x){ if(root != NULL ){ if(root->data == x){ return root; } if(root->data > x){ return searchNodeByRecursion(root->pLeft,x); }else{ return searchNodeByRecursion(root->pRight,x); } } return NULL; } tNode *searchNodeWithoutRecursion(tNode *root, int x){ tNode *p=root; while(p != NULL){ if(p->data == x){ return p; }else if(p->data > x){ p = p->pLeft; }else{ p = p->pRight; } } return NULL; } tNode *minValueNode(tNode *node){ tNode *current = node; while(current && current->pLeft != NULL){ current = current->pLeft; } return current; } tNode *deleteNode(tNode *root, int x){ if(root == NULL){ return root; } if(root->data > x){ root->pLeft = deleteNode(root->pLeft, x); }else if(root->data < x){ root->pRight = deleteNode(root->pRight, x); }else{ tNode *p = root; if(root->pLeft == NULL){ root=root->pRight; delete p; }else if(root->pRight== NULL){ root=root->pLeft; delete p; }else{ tNode *temp = minValueNode(root->pRight); root->data = temp->data; root->pRight = deleteNode(root->pRight, temp->data); } } return root; } int main() { //create binary search tree createEmptyTree(); root = insertNode(root, 8); root = insertNode(root, 3); root = insertNode(root, 1); root = insertNode(root, 6); root = insertNode(root, 7); root = insertNode(root, 10); root = insertNode(root, 14); root = insertNode(root, 4); cout<<"traverse tree with NLR:"; NLR(root); tNode *temp = searchNodeWithoutRecursion(root, 10); if(temp!=NULL){ cout<

Kết quả


traverse tree with NLR:8 3 1 6 4 7 10 14 Found x=10 traverse tree with NLR after delete node:8 4 1 6 7 10 14

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

Contents

Cây nhị phân tìm kiếm là một cấu trúc thường được sử dụng trong tin học. Điển hình là các kiểu dữ liệu set và map của C++ được cài đặt bằng cây nhị phân tìm kiếm. Bài viết này sẽ cung cấp những kiến thức cơ bản về cây nhị phân tìm kiếm và cách cài đặt một cây nhị phân tìm kiếm đơn giản (không hiệu quả).

Cách cài đặt trong bài này không được sử dụng trong thực tế tuy nhiên sẽ là nền tảng để nghiên cứu các cấu trúc cây nhị phân cao cấp hơn.

Sơ lược về cây nhị phân

Cây nhị phân gồm nhiều nút, mỗi nút có nhiều nhất là 2 nút con, gọi là nút con trái và nút con phải. Các nút không có nút con nào gọi là nút lá.

Ngoài ra, mỗi nút đều có duy nhất một nút cha, trừ nút gốc của cây không có cha.

Mỗi nút có thể chứa thêm thông tin, gọi là khóa. Khóa của nút thường là một số nguyên, tuy nhiên có thể là bất cứ kiểu dữ liệu nào.

Sau đây là ví dụ một cây nhị phân với khóa là các số nguyên:

Ngoài ra, nếu cắt một nhánh của cây ta sẽ được một cây con:

Định nghĩa cây nhị phân tìm kiếm

Với cây nhị phân tìm kiếm, khóa của các đỉnh thỏa tính chất sau:

  • Khóa của các đỉnh không trùng lặp, mỗi đỉnh có một khóa khác với tất cả các đỉnh còn lại.
  • Với mỗi đỉnh, khóa của tất cả các đỉnh trong cây con bên trái nhỏ hơn khóa của đỉnh đó.
  • Với mỗi đỉnh, khóa của tất cả các đỉnh trong cây con bên phải lớn hơn khóa của đỉnh đó.

Khóa của đỉnh phải là một kiểu dữ liệu có thể so sánh được.

Ví dụ một cây nhị phân tìm kiếm với khóa là số nguyên:

Khi cài đặt, ta cần một kiểu dữ liệu để lưu nút của cây:


struct Node { int key; Node *left = nullptr, *right = nullptr; Node(int key) : key(key) {} };

Trong đó:


  • left

    là con trỏ đến nút con bên trái

  • right

    là con trỏ đến nút con bên phải

  • key

    là khóa của nút

Để cho thuận tiện, ta thêm một constructor cho kiểu dữ liệu vừa tạo.

Thao tác thêm

Phần này sẽ trình bày thao tác thêm một nút có khóa vào cây nhị phân tìm kiếm.
Vì các khóa trong cây phải khác nhau nên nếu đã tồn tại trên cây thì sẽ không có nút
nào được thêm vào.

Việc thêm một khóa được thực hiện một cách đệ quy:

  • Nếu vị trí đang xét chưa tồn tại nút nào thì ta tạo tại đó một nút mới với khóa là khóa cần thêm.
  • Ngược lại, khi nút đang xét đã tồn tại thì có 3 trường hợp:

    • Khóa của nút đang xét bằng , trong trường hợp này ta dừng, không thêm nữa.
    • Khóa của nút đang xét lớn hơn , ta thấy nút cần thêm phải nằm trong cây con bên phải của nút đang xét, vì vậy ta gọi đệ quy xuống cây con bên phải.
    • Khóa của nút đang xét nhỏ hơn , ta gọi đệ quy xuống cây con bên trái.
  • Khóa của nút đang xét bằng

Với quy trình như trên, nút mới luôn là nút lá. Cài đặt trong C++ như sau:


Node* insert(Node *node, int key) { if (node == NULL) return new Node(key); if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); return node; }

Ví dụ sử dụng hàm trên:


int main() { Node* root = NULL; root = insert(root, 2); root = insert(root, 1); root = insert(root, 5); cout << root->key << root->left->key << root->right->key; }

Chú ý khi gọi hàm, cần gán lại nút gốc như trên.

Thao tác tìm kiếm

Phần này trình bày thao tác tìm một nút có khóa bằng trên cây. Trong trường hợp
không tìm thấy, trả về

NULL

.

Thao tác tìm kiếm cũng được thực hiện đệ quy tương tự như trên. Cụ thể:

  • Nếu vị trí đang xét chưa có nút nào, trả về

    NULL

    với ý nghĩa là không tìm thấy.
  • Ngược lại, ta so sánh với khóa của nút đang xét, sau đó đệ quy sang trái/phải hoặc trả về nút hiện tại tùy thuộc vào kết quả so sánh lớn hơn/bé hơn hoặc bằng.

Cài đặt của thao tác này đơn giản hơn:


Node* find(Node *node, int key) { if (node == NULL) return NULL; if (key > node->key) return find(node->right, key); if (key < node->key) return find(node->left, key); return node; }

Việc khử đệ quy hàm trên khá dễ, bạn đọc có thể tự tìm hiểu.

Thao tác xóa

Xóa một nút phức tạp hơn so với việc thêm và tìm kiếm. Ta có 3 trường hợp:

Các thao tác cơ bản trên cây nhị phân tìm kiếm

Các thao tác trên cây nhị phân tìm kiếm như duyệt cây, thêm một nút vào cây, hủy một nút trong cây, tìm kiếm một nút trong cây,…

Duyệt cây

Cách duyệt giống như cây nhị phân bình thường với 3 kiểu duyệt chính là NLR, LNR, LRN.

Tìm một nút trong cây

Nhờ vào đặc điểm của cây nhị phân tìm kiếm mà việc tìm kiếm nút dễ dàng hơn. Có thể dùng đệ quy hoặc không dùng đệ quy để tìm một nút trong cây nhị phân tìm kiếm.

Sử dụng đệ quy


tNode *searchNodeByRecursion(tNode *root, int x){ if(root != NULL ){ if(root->data == x){ return root; } if(root->data > x){ return searchNodeByRecursion(root->pLeft,x); }else{ return searchNodeByRecursion(root->pRight,x); } } return NULL; }

Không sử dụng đệ quy


tNode *searchNodeWithoutRecursion(tNode *root, int x){ tNode *p=root; while(p != NULL){ if(p->data == x){ return p; }else if(p->data > x){ p = p->pLeft; }else{ p = p->pRight; } } return NULL; }

Thêm một nút vào cây

Sau khi thêm nút vào cây thì đảm bảo vẫn là cây nhị phân tìm kiếm. Lưu ý, không thêm nút lưu giá trị đã có trong cây.


tNode *insertNode(tNode *node, int value){ if(node!=NULL){ if(node->data == value){ return node; }else if(node->data > value){ node->pLeft = insertNode(node->pLeft, value); }else{ node->pRight = insertNode(node->pRight, value); } }else{ node = newNode(value); } return node; }

Hủy một nút lưu giá trị x trong cây

Khi hủy 1 nút phải đảm bảo điều kiện ràng buộc của cây nhị phân tìm kiếm.

Có 3 trường hợp khi hủy 1 nút trên cây:

Trường hợp 1: x là nút lá. Hủy nút lá mà không ảnh hưởng đến các nút khác trên cây.

Trường hợp 2: x chỉ có 1 cây con (cây con trái hoặc cây con phải). Trước khi hủy x, ta liên kết nút cha của x với con duy nhất của x.

Trường hợp 3: x có đầy đủ 2 cây con. Thực hiện các bước sau để hủy x:

Bước 1: Tìm nút y thế mạng cho nút x, có 2 cách tìm:

    • Cách 1: y là phần tử nhỏ nhất (trái nhất) trên cây con phải.

    • Cách 2: y là phần tử lớn nhất (phải nhất) trên cây con trái.

Bước 2: Lưu thông tin của y vào x.

Bước 3: Hủy y (giống như hủy nút lá).


tNode *minValueNode(tNode *node){ tNode *current = node; while(current && current->pLeft != NULL){ current = current->pLeft; } return current; } tNode *deleteNode(tNode *root, int x){ if(root == NULL){ return root; } if(root->data > x){ root->pLeft = deleteNode(root->pLeft, x); }else if(root->data < x){ root->pRight = deleteNode(root->pRight, x); }else{ tNode *p = root; if(root->pLeft == NULL){ root=root->pRight; delete p; }else if(root->pRight== NULL){ root=root->pLeft; delete p; }else{ tNode *temp = minValueNode(root->pRight); root->data = temp->data; root->pRight = deleteNode(root->pRight, temp->data); } } return root; }

[Cây Nhị Phân Tìm Kiếm] Bài 2. Khai báo-khởi tạo-Duyệt NLR cây nhị phân(cây nhị phân tìm kiếm)
[Cây Nhị Phân Tìm Kiếm] Bài 2. Khai báo-khởi tạo-Duyệt NLR cây nhị phân(cây nhị phân tìm kiếm)

Nút cần xóa có 2 nút con

Ở trường hợp này, ta tìm nút thay thế cho nút cần xóa, sau đó chuyển khóa của nút thay thế lên nút cần xóa, rồi cuối cùng mới xóa nút thay thế.

Ví dụ:

Ta thấy, nút thay thế phải là 1 trong 2 nút có khóa gần nhất với nút cần xóa, để việc chuyển khóa lên trên không vi phạm tính chất của cây.

Khi xóa nút thay thế, cũng phải xét xem nó có bao nhiêu nút con như khi xóa một nút bình thường.

Biểu diễn cây nhị phân tìm kiếm

Chúng ta có thể sử dụng danh sách liên kết để biểu diễn cây nhị phân tìm kiếm. Đầu tiên, cần định nghĩa một nút trong cấu trúc dữ liệu dạng cây.


struct tNode{ int data; tNode *pLeft, *pRight; };

Dữ liệu (data) lưu trữ trong nút của cây nhị phân tìm kiếm phải là dữ liệu có thể so sánh giá trị nhỏ hơn hoặc lớn hơn giữa các nút trong cây.

Để lưu trữ cây, chúng ta chỉ cần xác định nút gốc của cây.


tNode *root;

Tạo một cây rỗng


void CreateEmptyTree(){ root = NULL; }

Tạo một nút lưu giá trị x


tNode *newNode(int data){ tNode *node = new tNode; if(node==NULL){//cannot allocate memory exit(1); }else{ node->data = data; node->pLeft = NULL; node->pRight = NULL; } return node; }

[Cây Nhị Phân Tìm Kiếm] Bài 1. Tổng quan về cây nhị phân - cây nhị phân tìm kiếm
[Cây Nhị Phân Tìm Kiếm] Bài 1. Tổng quan về cây nhị phân – cây nhị phân tìm kiếm

Duyệt cây tìm kiếm nhị phân

Ở mục này mình sẽ trình bày về 3 cách duyệt cây tìm kiếm nhị phân. Chúng ta sẽ đi vào chi tiết từng cách nhé. Thứ tự duyệt được đặt tên phụ thuộc vào vị trí của Node root trong quá trình duyệt:

  • PreOrder: Node -> Left -> Right
  • InOrder: Left -> Node -> Right
  • PostOrder: Left -> Right -> Node
  • Thực ra 3 phần tử Left, Right, Node có tất cả 6 hoán vị cơ. Còn 3 cái nữa các bạn tự cài nhé.

3.Duyệt PreOrder

Quy trình duyệt PreOrder sẽ thực hiện theo thứ tự Node -> Left -> Right, cụ thể như sau:

  1. Ghé thăm Node root
  2. Gọi đệ quy duyệt qua cây con bên trái
  3. Gọi đệ quy duyệt qua cây con bên phải

void PreOrder(node_t* root){ if(root != NULL) { printf(“%d “, root->data); PreOrder(root->left); PreOrder(root->right); } }

3.Duyệt InOrder

Quy trình duyệt PreOrder sẽ thực hiện theo thứ tự Left-> Node -> Right, cụ thể như sau:

  1. Gọi đệ quy duyệt qua cây con bên trái
  2. Ghé thăm Node root
  3. Gọi đệ quy duyệt qua cây con bên phải

void InOrder(node_t* root){ if(root != NULL) { InOrder(root->left); printf(“%d “, root->data); InOrder(root->right); } }

3.Duyệt PostOrder

Quy trình duyệt PreOrder sẽ thực hiện theo thứ tự Left -> Right -> Node, cụ thể như sau:

  1. Gọi đệ quy duyệt qua cây con bên trái
  2. Gọi đệ quy duyệt qua cây con bên phải
  3. Ghé thăm Node root

void PostOrder(node_t* root){ if(root != NULL) { PostOrder(root->left); PostOrder(root->right); printf(“%d “, root->data); } }

Bài tập thực hành

  • https://vn.spoj.com/problems/NKTREE/
  • http://ntucoder.net/Problem/List?ThemeID=17
  • https://www.hackerearth.com/practice/data-structures/trees/binary-search-tree/practice-problems/

Cây nhị phân là một cấu trúc dữ liệu quan trọng mà trong môn Cấu trúc dữ liệu và giải thuật các bạn sẽ được học, nó được sử dụng rất rộng rãi trong lập trình vì các ứng dụng của nó. Trong bài viết này, mình sẽ giới thiệu đến các bạn về cây nhị phân và một phiên bản đặc biệt của nó là cây nhị phân tìm kiếm. Trước tiên, ta cần biết được cây là gì?

CTDLGT_Lý thuyết về cây nhị phân tìm kiếm
CTDLGT_Lý thuyết về cây nhị phân tìm kiếm

Cài đặt cây BST

Sau đây, tôi sẽ cùng các bạn đi cài đặt cây tìm kiếm nhị phân sử dụng danh sách liên kết. Do đó, cái bạn cần lưu giữ là Node root của cây mà thôi. Có được root chúng ta có thể duyệt qua mọi phần tử của cây.

Đầu tiên, chúng ta sẽ định nghĩa kiểu dữ liệu cho các Node của cây:

typedef struct Node { int data; Node* left; Node* right; } node_t;

Tiếp theo, chúng ta sẽ triển khai code cho tức chức năng của cây BST. Chúng ta sẽ sử dụng đệ quy rất nhiều trong các chức năng này. Bạn có thể tự tìm hiểu cách viết khử đệ quy nhé.

2.Hàm giải phóng dữ liệu

Chúng ta sẽ sử dụng hàm này khi muốn xóa một cây con hoặc toàn bộ cây bằng cách cung cấp Node root của cây muốn xóa. Việc giải phóng được thực hiện theo trình tự:

  1. Gọi đệ quy xóa cây con bên trái
  2. Gọi đệ quy xóa cây con bên phải
  3. Giải phóng vùng nhớ cho con trỏ hiện tại

void Free( node_t* root ) { if ( root == NULL ) return; Free( root->left ); Free( root->right ); free( root ); }

2.Hàm điều hướng của cây

2 hàm dưới đây sẽ phục vụ chúng ta trong quá trình Insert(thêm phần tử vào cây) và Tìm kiếm trên cây tìm kiếm nhị phân.

Nếu bạn cho phép cây BST có giá trị trùng lặp, hãy lưu ý hàm LeftOf nhé. Ở đây tôi sẽ không cho phép thêm phần tử đã có trên cây(bỏ qua trùng lặp giá trị).

int LeftOf( const int value, const node_t* root ) { // Nếu bạn muốn cây BST cho phép giá trị trùng lặp, hãy sử dụng dòng code thứ 2 return value < root->data; // return value <= root->data; } int RightOf( const int value, const node_t* root ) { return value > root->data; }

2.Thêm phần tử vào BST

Việc thêm 1 phần tử vào cây nhị phân tìm kiếm vẫn phải đảm bảo được các ràng buộc của một BST đã trình bày ở trên. Như vậy, bạn cần phải tìm kiếm vị trí thích hợp trong BST để lưu giữ nó.

Nếu bạn để ý, bạn sẽ nhận ra vị trí của các Node được thêm vào sẽ luôn Node lá(không có Child nào hết). Như vậy, tại vị trí đó trước khi các Node mới tới ở thì nó là NULL. Ta có quy trình như sau:

  1. Nếu Node hiện tại = NULL, đó là vị trí cần thêm. Thêm vào BST và kết thúc
  2. Nếu giá trị cần thêm < giá trị root hiện tại, gọi đệ quy Insert vào cây con bên trái
  3. Nếu giá trị cần thêm > giá trị root hiện tại, gọi đệ quy Insert vào cây con bên phải.

node_t* Insert( node_t* root, const int value ) { if ( root == NULL ) { node_t* node = (node_t*)malloc( sizeof( node_t ) ); node->left = NULL; node->right = NULL; node->data = value; return node; } if ( LeftOf( value, root ) ) root->left = Insert( root->left, value ); else if ( RightOf( value, root ) ) root->right = Insert( root->right, value ); return root; }

Hãy xem hình ảnh mô phỏng việc thêm giá trị 4 vào BST dưới đây:

2.Tìm kiếm trên BST

Việc tìm kiếm cũng tương tự như việc thêm phần tử vào BST. Ta có quy trình như sau:

  1. Nếu Node hiện tại có giá trị = giá trị cần tìm, trả về true và kết thúc.
  2. Nếu Node hiện tại có giá trị > giá trị cần tìm, gọi đệ quy tìm ở cây con bên trái.
  3. Nếu Node hiện tại có giá trị < giá trị cần tìm, gọi đệ quy tìm ở cây con bên phải
  4. Nếu tìm đến hết cây(Node đó = NULL) mà không xảy ra (1), trả về false và kết thúc.

bool Search( const node_t* root, int value ) { if ( root == NULL ) return false; if(root->data == value){ return true; }else if ( LeftOf( value, root ) ){ return Search( root->left, value ); }else if( RightOf( value, root ) ){ return Search( root->right, value ); } }

Chúng ta sẽ quan sát cách BST tìm kiếm giá trị 4 trong hình ảnh dưới đây:

2.Lấy giá trị con trái nhất

Rất đơi giản, duyệt theo con trỏ trỏ đến cây con bên trái tới chừng nào không còn con bên trái nữa thì đó là con trái nhất rồi.

Hàm này sẽ được chúng ta sử dụng trong việc xóa một Node có giá trị chỉ định trên BST ở mục tiếp theo.

int LeftMostValue( const node_t* root ) { while ( root->left != NULL ) root = root->left; return root->data; }

Hình ảnh dưới đây mô phỏng hàm LestMostChild hoạt động:

Vậy chúng ta có cần hàm RightMostChild không? Câu trả lời là có. Tuy nhiên, bạn có thể tận dùng hàm LeftMostChild này, chẳng hạn: Số 25 là right most child của root(15) có thể tính bằng LeftMostChild(root->right->right).

2.Xóa Node trong BST

Việc xóa Node trong BST có lẽ là phức tạp nhất trong các chức năng của cây tìm kiếm nhị phân. Nếu Node bạn cần xóa là Node lá thì việc xóa rất đơn giản. Cái khó ở chỗ xóa một Node ở trung gian, khi đó, bạn phải tìm cách xóa và nối lại mà vẫn đảm bảo cây mới vẫn là BST. Chúng ta sẽ xem xét từng trường hợp trước khi code nhé:

Node cần xóa là Node lá(không có child nào cả)

Giả sử ta cần xóa 20 trong hình dưới đây, đơn giản là chỉ cần giải phóng ô nhớ đó.

50 50 / \ delete(20) / \ 30 70 ———> 30 70 / \ / \ \ / \ 20 40 60 80 40 60 80

Node cần xóa có 1 child

Trong trường hợp này, Node bị xóa sẽ được giải phóng và cây con duy nhất của Node bị xóa sẽ được liên kết trực tiếp với cha của Node bị xóa.

50 50 / \ delete(30) / \ 30 70 ———> 40 70 \ / \ / \ 40 60 80 60 80

Node cần xóa có đủ 2 child

Đây là trường hợp nan giải nhất, nhưng chúng ta vẫn có cách làm như sau:

  1. Tìm Node của con trái nhất(giả sử nó là leftmost) của cây con bên phải của Node cần xóa.
  2. Cập nhật giá trị của Node cần xóa = giá trị của Node leftmost.
  3. Gọi đệ quy hàm Delete xóa Node leftmost khỏi BST.

Giải thích:

  • Khi muốn xóa Node có 2 con, ta cần tìm Node nào đó trong BST thỏa mãn tính chất lớn hơn lớn hơn tất cả các con bên trái và nhỏ hơn tất cả các con bên phái -> Node đó chính là LeftMostChild của con bên phải của Node cần xóa.
  • Ta chỉ cần sửa giá trị của Node cần xóa, không cần xóa Node đó làm gì. Thay vào đó, xóa Node bị thế thân(LeftMostChild của con bên phải của Node cần xóa).

node_t* Delete( node_t* root, int value ) { if ( root == NULL ) return root; if ( LeftOf( value, root ) ) root->left = Delete( root->left, value ); else if ( RightOf( value, root ) ) root->right = Delete( root->right, value ); else { // root->data == value, delete this node if ( root->left == NULL ) { node_t* newRoot = root->right; free( root ); return newRoot; } if ( root->right == NULL ) { node_t* newRoot = root->left; free( root ); return newRoot; } root->data = LeftMostValue( root->right ); root->right = Delete( root->right, root->data ); } return root; }

Định nghĩa[sửa | sửa mã nguồn]

Cây tìm kiếm ứng với n khóa là cây nhị phân mà mỗi nút đều được gán một khóa sao cho với mỗi mỗi nút k:

  • Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút k
  • Mọi khóa trên cây con phải đều lớn hơn khóa trên nút k

Cây tìm kiếm nhị phân là một cấu trúc dữ liệu cơ bản được sử dụng để xây dựng các cấu trúc dữ liệu trừu tượng hơn như các tập hợp, đa tập hợp, các dãy kết hợp.

Nếu một BST có chứa các giá trị giống nhau thì nó biểu diễn một đa tập hợp. Cây loại này sử dụng các bất đẳng thức không nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ hơn khóa của nút cha, mọi nút trên cây con phải có nút lớn hơn hoặc bằng khóa của nút cha.

Nếu một BST không chứa các giá trị giống nhau thì nó biểu diễn một tập hợp đơn trị như trong lý thuyết tập hợp. Cây loại này sử dụng các bất đẳng thức nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ hơn khóa của nút cha, mọi nút trên cây con phải có khóa lớn hơn khóa của nút cha.

Việc chọn đưa các giá trị bằng nhau vào cây con phải (hay trái) là tùy theo mỗi người. Một số người cũng đưa các giá trị bằng nhau vào cả hai phía, nhưng khi đó việc tìm kiếm trở nên phức tạp hơn.

Giải Bài Tập Cây Nhị Phân Tìm Kiếm Cân Bằng | Cấu Trúc Dữ Liệu | Thảo Lập Trình
Giải Bài Tập Cây Nhị Phân Tìm Kiếm Cân Bằng | Cấu Trúc Dữ Liệu | Thảo Lập Trình

Đặc điểm của cây nhị phân tìm kiếm

Cây nhị phân tìm kiếm (Binary Search Tree) là một cây nhị phân có đặc điểm:

    • Tất cả các nút trong cây con bên trái lưu trữ giá trị nhỏ hơn nút đang xét
    • Tất cả các nút trong cây con bên phải lưu trữ giá trị lớn hơn nút đang xét

Nhờ trật tự bố trí các nút trên cây giúp định hướng việc tìm kiếm các nút trong cây. Chính vì thế mà nó được gọi là cây nhị phân tìm kiếm.

Biến thể

Có cấu trúc cây cân đối khác. Phổ biến nhất là cây AVL. Cây đỏ đen và các cây nhị phân cân đối khác là những lựa chọn tốt để tìm kiếm trong bộ nhớ. Khi tập dữ liệu trở nên quá lớn không thể lưu trong bộ nhớ, một loại cây khác thường được sử dụng: cây n-way, trong đó mỗi nút có nút con. Một phiên bản chung của những cây như vậy được gọi là B-tree, hoạt động rất tốt trong việc giảm thiểu số lần truy cập đĩa để tìm một mục cụ thể trong tập dữ liệu lớn. B-tree thường được sử dụng khi triển khai cơ sở dữ liệu quan hệ.

Tổng kết

Vậy là trong bài viết mình đã trình bày những kiến thức về cây tìm kiếm nhị phân cùng với các ưu nhược điểm. Nhờ tính chất của cây tìm kiếm nhị phân mà hiệu suất tìm kiếm được cải thiện khi làm việc với dữ liệu liên tục thay đổi. Do đó, hãy cân nhắc sử dụng cây tìm kiếm nhị phân nếu bạn muốn tăng tốc chương trình của mình.

Tài liệu tham khảo

  1. Giải thuật và lập trình – Thầy Lê Minh Hoàng
  2. cp-algorithms.com
  3. Handbook Competitive Programming – Antti Laaksonen
  4. Competitve programming 3 – Steven Halim, Felix Halim

©️ Tác giả: Vũ Quế Lâm từ Viblo

All rights reserved

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

Cấu trúc cây

Cấu trúc cây (Tree) là một tập hợp các phần tử gọi là nút (node), mỗi cây có một nút gốc (root) chứa nhiều nút con, mỗi nút con lại là một tập hợp các nút khác gọi là cây con (subtree).

Các khái niệm cơ bản về cây:

  • Bậc của nút: là số nút con của nút đó. Ví dụ bậc của nút A là 3, bậc của nút C là 1, bậc của nút G là 0…
  • Bậc của cây: là bậc lớn nhất của nút trong cây đó, cây bậc n sẽ được gọi là cây n – phân. Ví dụ cây trong hình trên có bậc 3, gọi là cây tam phân, cây có bậc 2 gọi là cây nhị phân…
  • Nút lá: nút lá là nút có bậc bằng 0. Ví dụ các nút lá: B, G, H, K, L, F
  • Nút nhánh: là nút có bậc khác 0 mà không phải nút gốc (hay còn gọi là nút trung gian). Ví dụ các nút C, D, E
  • Mức của nút: là số nguyên đếm từ 0, các nút ngang hàng nhau thì có cùng mức. Nút gốc A có mức là 0, mức 1 gồm các nút B, C, D, nút 3 gồm H, K, L.
  • Chiều cao (chiều sâu): là mức lớn nhất của các nút lá. Ví dụ cây trên có nút lá bậc lớn nhất là H, K, L mức 3, vậy chiều cao của cây là 3.
  • Độ dài đường đi đến nút x: là số nhánh (cạnh nối hai nút) cần đi qua tính từ nút gốc đến nút x. Hay độ dài đường đi đến nút mức i chính là i. Ví dụ nút E có độ dài đường đi là 2.

Khi bạn đã nắm được các khái niệm cơ bản này, chúng ta hãy đến luôn với cây nhị phân.

Làm thế nào để duyệt (traverse) một Binary Search Tree

Traversal là quá trình mà qua đó chúng ta điều hướng Binary Search Tree. Nó được thực hiện để xác định vị trí một mục cụ thể hoặc để in outline (khung) của cây. Chúng ta luôn bắt đầu từ nút gốc và phải đi theo các cạnh để đến các nút khác. Mỗi nút nên được coi là một cây con và quá trình này được lặp lại cho đến khi tất cả các nút được truy cập.

  • In-order traversal: sẽ tạo ra một bản đồ theo thứ tự tăng dần. Với phương pháp này, chúng ta bắt đầu từ cây con bên trái và tiếp tục đến cây con gốc và cây con bên phải.
  • Post-order traversal: Trong phương pháp này, nút gốc được truy cập đầu tiên, tiếp theo là cây con bên trái và cây con bên phải.
  • Post-Order Traversal: truy cập vào nút gốc cuối cùng. Chúng ta bắt đầu từ cây con bên trái, sau đó đến cây con bên phải, và sau đó là nút gốc.

>>> Xem thêm: Làm thế nào để trở thành một kiến trúc sư dữ liệu?

Cây nhị phân tìm kiếm - Giới thiệu, thao tác thêm nút, tìm kiếm nút trên cây
Cây nhị phân tìm kiếm – Giới thiệu, thao tác thêm nút, tìm kiếm nút trên cây

Ứng dụng trong thế giới thực

Làm thế nào để chúng ta sử dụng các thuật toán cây tìm kiếm nhị phân? Như bạn có thể đoán được, chúng cực kỳ hiệu quả trong việc tìm kiếm và phân loại. Sức mạnh lớn nhất của cây nhị phân là cấu trúc có tổ chức của nó. Nó cho phép thực hiện tìm kiếm với tốc độ đáng kể bằng cách cắt giảm một nửa lượng dữ liệu chúng ta cần phân tích.

Binary Search Tree cho phép chúng ta duy trì một cách hiệu quả tập dữ liệu thay đổi động ở dạng có tổ chức. Đối với các ứng dụng có dữ liệu được chèn và gỡ bỏ thường xuyên, chúng rất hữu ích. Công cụ trò chơi điện tử sử dụng một thuật toán dựa trên cây được gọi là phân vùng không gian nhị phân để giúp hiển thị các đối tượng một cách có trật tự. Microsoft Excel và hầu hết các phần mềm bảng tính sử dụng cây nhị phân làm cấu trúc dữ liệu cơ bản của chúng.

Bạn có thể ngạc nhiên khi biết rằng mã Morse sử dụng cây tìm kiếm nhị phân để mã hóa dữ liệu. Một lý do khác khiến Binary Search Tree rất hữu ích là do chúng có nhiều biến thể. Tính linh hoạt của chúng đã dẫn đến nhiều biến thể được tạo ra để giải quyết tất cả các loại vấn đề.

Mã giả bằng ngôn ngữ C[sửa | sửa mã nguồn]

#include

#include

#include

//Khai bao cay nhi phan typedef char TData; typedef struct TNode{ TData Data; TNode* left; TNode* right; }; typedef TNode* TTree; /*=== Tao cay rong ===*/ void MakeNull_Tree(TTree *T) { (*T)=NULL; } /*=== Kiem tra cay rong ===*/ int EmptyTree(TTree T) { return T==NULL; } /*=== Xac dinh con trai ===*/ TTree LeftChild(TTree T) { if(T != NULL) return T->left; else return NULL; } /*=== Xac dinh con phai ===*/ TTree RightChild(TTree T) { if(T != NULL) return T->right; else return NULL; } /*=== Xac dinh nut la ===*/ int isLeaf(TTree T) { if((T != NULL) && (T->left == NULL) && (T->right == NULL)) return 1; else return NULL; } /*=== Xac dinh so nut cua cay ===*/ int nb_nodes(TTree T) { if(EmptyTree(T)) return 0; else return nb_nodes(T->left)+nb_nodes(T->right)+1; } // Ham xac dinh gia tri lon nhat trong hai so nguyen int max(int value1,int value2) { return ((value1 > value2) ? value1: value2); //xac dinh gia tri lon nhat trong 2 gia tri so nguyen } // Ham xac dinh chieu cao cua cay int TreeHeight(TTree T) { int height=0; if (!EmptyTree(T)) { if (isLeaf(T)) return 0; else height = max(TreeHeight(LeftChild(T)),TreeHeight(RightChild(T)))+1; } return height; } // Ham xac dinh so nut la tren cay int nb_leaf(TTree T) { int leaf=0; if(!EmptyTree(T)) { if (isLeaf(T)) leaf++; else leaf = nb_leaf(LeftChild(T))+nb_leaf(RightChild(T)); }; return leaf; } /*=== Tao cay moi tu hai cay co san ===*/ TTree Create2(TData v,TTree left,TTree right) { TTree N; // Khai bao 1 cay moi N = (TNode*)malloc(sizeof(TNode)); //Cap phat vung nho cho nut N N->Data = v; // Nhan cua nut N la v N->left = left; //Con trai cua N la cay left N->right = right; //Con phai cua N la cay right return N; } /*=== Duyet cay nhi phan ===*/ //Duyet tien tu void NLR(TTree T) { if(!EmptyTree(T)) { printf(” %c”,T->Data); //Xu ly nut NLR(LeftChild(T)); //Duyet tien tu con trai NLR(RightChild(T)); //Duyet tien tu con phai } } //Duyet trung tu void LNR(TTree T) { if(!EmptyTree(T)) { LNR(LeftChild(T)); //Duyet trung tu con trai printf(” %c”,T->Data);//Xu ly nut LNR(RightChild(T));//Duyet trung tu con phai } } //Duyet hau tu void LRN(TTree T) { if(!EmptyTree(T)) { LRN(LeftChild(T)); //Duyet hau tu con trai LRN(RightChild(T));//Duyet hau tu con phai printf(” %c”,T->Data);//Xu ly nut } }

Chú 7 Thiện Chia Sẻ Mới Nhất 2024!!!
Chú 7 Thiện Chia Sẻ Mới Nhất 2024!!!

Tổng kết

Vậy là qua bài viết này, mình đã giới thiệu đến các bạn về cấu trúc cây, cây nhị phân và cây nhị phân tìm kiếm. Đương nhiên, mình không phải “master” và mình cũng không thể nào mà nắm được hết tất cả các lý thuyết đồ thị hay thuật toán, do đó sai sót là không thể tránh khỏi, hy vọng các bạn góp ý thêm.

Cảm ơn các bạn đã theo dõi bài viết, nếu thấy bài viết này hay, đừng quên chia sẻ cho mọi người cùng biết nhé! Cảm ơn các bạn!

Liên kết ngoài[sửa | sửa mã nguồn]

  • [1] Lưu trữ 2009-03-20 tại Wayback Machine
  • Full source code to an efficient implementation in C++ Lưu trữ 2010-03-28 tại Wayback Machine
  • Implementation of Binary Search Trees in C
  • Implementation of a Persistent Binary Search Tree in C
  • Implementation of Binary Search Trees in Java Lưu trữ 2010-03-09 tại Wayback Machine
  • Iterative Implementation of Binary Search Trees in C# Lưu trữ 2008-06-13 tại Wayback Machine
  • An introduction to binary trees from Stanford
  • Dictionary of Algorithms and Data Structures – Binary Search Tree
  • Binary Search Tree Example in Python
  • Java Model illustrating the behaviour of binary search trees(In JAVA Applet) Lưu trữ 2005-08-01 tại Wayback Machine
  • Interactive Data Structure Visualizations – Binary Tree Traversals Lưu trữ 2014-02-27 tại Wayback Machine
  • Literate implementations of binary search trees in various languages Lưu trữ 2017-04-21 tại Wayback Machine on LiteratePrograms
  • BST Tree Applet by Kubo Kovac
  • Well-illustrated explanation of binary search tree. Implementations in Java and C++

Chương 6: TREES – 7.Cây tìm kiếm nhị phân(Binary Search Trees – BSTs)

Tại sao cần Binary Search Trees?

Trong các phần trước, chúng ta đã thảo luận về các cách biểu diễn cây khác nhau và trong tất cả chúng, chúng ta không áp đặt bất kỳ hạn chế nào đối với dữ liệu trong node. Do đó, để tìm kiếm một phần tử, chúng ta cần kiểm tra cả cây con bên trái và cây con bên phải. Do đó, độ phức tạp trong trường hợp xấu nhất của thao tác tìm kiếm là O(n).

Trong phần này, chúng ta sẽ thảo luận về một biến thể khác của cây nhị phân: Cây tìm kiếm nhị phân (BST). Như tên gợi ý, công dụng chính của biểu diễn này là để tìm kiếm. Trong biểu diễn này, chúng ta áp đặt hạn chế đối với loại dữ liệu mà một node có thể chứa. Trong biểu diễn này, chúng ta áp đặt hạn chế đối với loại dữ liệu mà một node có thể chứa. Kết quả là, nó giảm thao tác tìm kiếm trung bình trong trường hợp xấu nhất xuống O(logn).

Các tính chất của Binary Search Trees

Trong cây tìm kiếm nhị phân, tất cả các phần tử của cây con bên trái phải nhỏ hơn dữ liệu gốc và tất cả các phần tử của cây con bên phải phải lớn hơn dữ liệu gốc. Đây được gọi là thuộc tính cây tìm kiếm nhị phân. Lưu ý rằng, thuộc tính này phải được thỏa mãn tại mọi node trong cây.

  • Cây con bên trái của một node chỉ chứa các node có data nhỏ hơn node.
  • Cây con bên phải của một node chỉ chứa các node có data lớn hơn node.
  • Cả cây con bên trái và bên phải cũng phải là cây tìm kiếm nhị phân.

Ví dụ: Cây bên trái là cây tìm kiếm nhị phân và cây bên phải không phải là cây tìm kiếm nhị phân (tại node 6, nó không thỏa mãn thuộc tính của cây tìm kiếm nhị phân).

Khai báo cây tìm kiếm nhị phân

Không có sự khác biệt giữa khai báo cây nhị phân thông thường và khai báo cây nhị phân tìm kiếm. Sự khác biệt chỉ ở dữ liệu chứ không phải ở cấu trúc. Nhưng để thuận tiện, chúng ta đổi tên cấu trúc thành:


public class BinarySearchTreeNode { private int data; private BinarySearchTreeNode left; private BinarySearchTreeNode right; public int getData() { return data; } public void setData(int data) { this.data = data; } public BinarySearchTreeNode getLeft() { return left; } public void setLeft(BinarySearchTreeNode left) { this.left = left; } public BinarySearchTreeNode getRight() { return right; } public void setRight(BinarySearchTreeNode right) { this.right = right; } }

Thao tác trên cây tìm kiếm nhị phân

Các thao tác chính Các hoạt động chính được hỗ trợ bởi cây tìm kiếm nhị phân:

  • Tìm/Tìm tối thiểu/Tìm tối đa trong cây tìm kiếm nhị phân
  • Chèn một phần tử vào cây tìm kiếm nhị phân
  • Xóa một phần tử khỏi cây tìm kiếm nhị phân

Hoạt động phụ trợ

  • Kiểm tra xem cây đã cho có phải là cây tìm kiếm nhị phân hay không
  • Tìm phần tử nhỏ thứ k trong cây
  • Sắp xếp các phần tử của cây tìm kiếm nhị phân và nhiều hơn nữa

Notes về cây tìm kiếm nhị phân

  • Vì dữ liệu gốc luôn nằm giữa dữ liệu cây con bên trái và dữ liệu cây con bên phải, nên việc thực hiện duyệt theo inorder traversal cây tìm kiếm nhị phân sẽ tạo ra một danh sách được sắp xếp.
  • Trong khi giải các bài toán trên cây tìm kiếm nhị phân, đầu tiên chúng ta xử lý cây con bên trái, sau đó dữ liệu gốc và cuối cùng chúng ta xử lý cây con bên phải. Điều này có nghĩa là, tùy thuộc vào vấn đề, chỉ có bước trung gian (xử lý dữ liệu gốc) thay đổi và chúng ta không chạm vào bước đầu tiên và bước thứ ba.
  • Nếu chúng ta đang tìm kiếm một phần tử và nếu dữ liệu gốc của cây con bên trái nhỏ hơn phần tử mà chúng ta muốn tìm kiếm thì hãy bỏ qua nó. Điều tương tự cũng xảy ra với cây con bên phải. Do đó, cây nhị phân tìm kiếm mất ít thời gian hơn để tìm kiếm một phần tử so với cây nhị phân thông thường. Nói cách khác, cây tìm kiếm nhị phân xem xét các cây con bên trái hoặc bên phải để tìm kiếm một phần tử chứ không phải cả hai.
  • Các thao tác cơ bản có thể được thực hiện trên cây tìm kiếm nhị phân (BST) là chèn phần tử, xóa phần tử và tìm kiếm phần tử. Trong khi thực hiện các thao tác này trên BST, chiều cao của cây sẽ thay đổi mỗi lần. Do đó tồn tại các biến thể về độ phức tạp thời gian của trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất.
  • Các hoạt động cơ bản trên cây tìm kiếm nhị phân mất thời gian tỷ lệ thuận với chiều cao của cây. Đối với một cây nhị phân hoàn chỉnh với n node, các hoạt động như vậy chạy trong trường hợp xấu nhất là O(lgn). Tuy nhiên, nếu cây là một chuỗi tuyến tính gồm n node (cây xiên), thì các thao tác tương tự sẽ mất O(n) thời gian trong trường hợp xấu nhất.

Tìm phần tử trong cây tìm kiếm nhị phân

Thao tác tìm rất đơn giản trong BST. Bắt đầu với thư mục gốc và tiếp tục di chuyển sang trái hoặc phải bằng thuộc tính của BST. Nếu dữ liệu chúng ta đang tìm kiếm giống với dữ liệu node thì chúng ta trả về node hiện tại. Nếu dữ liệu chúng ta đang tìm kiếm nhỏ hơn dữ liệu node thì tìm kiếm cây con bên trái của node hiện tại; mặt khác tìm kiếm cây con bên phải của node hiện tại. Nếu không có dữ liệu, chúng ta sẽ return null link.


public BinarySearchTreeNode find(BinarySearchTreeNode root, int data){ if(root == null){ return null; } if(data < root.getData()){ return find(root.getLeft(), data); } else if (data > root.getData()) { return find(root.getRight(), data); } return root; }

Time Complexity: O(n), trong trường hợp xấu nhất (khi cây tìm kiếm nhị phân đã cho là cây nghiêng). Space Complexity: O(n), dành cho ngăn xếp đệ quy.

Phiên bản non recursive của thuật toán trên có thể là:


public BinarySearchTreeNode find(BinarySearchTreeNode root, int data) { if(root == null){ return null; } while(root != null){ if(data == root.getData()){ return root; } else if (data > root.getData()) { root = root.getRight(); } else { root = root.getLeft(); } } return null; }

Time Complexity: O(n). Space Complexity: O(1).

Tìm phần tử nhỏ nhất trong cây tìm kiếm nhị phân

Trong các BST, phần tử nhỏ nhất là node ngoài cùng bên trái mà không có node con bên trái. Trong BST bên dưới, phần tử tối thiểu là 4.


public BinarySearchTreeNode findMin(BinarySearchTreeNode root){ if(root == null){ return null; } else{ if(root.getLeft() == null){ return root; } else{ return findMin(root.getLeft()); } } }

Time Complexity: O(n), trong trường hợp xấu nhất (khi BST là cây lệch trái). Space Complexity: O(n), đối với ngăn xếp đệ quy.

Phiên bản non recursive của thuật toán trên có thể là:


public BinarySearchTreeNode findMin(BinarySearchTreeNode root) { if (root == null) { return null; } while(root.getLeft() != null){ root = root.getLeft(); } return root; }

Time Complexity: O(n). Space Complexity: O(1).

Tìm phần tử lớn nhất trong cây tìm kiếm nhị phân

Trong các BST, phần tử lớn nhất là node ngoài cùng bên phải, không có node con bên phải. Trong BST bên dưới, phần tử tối đa là 16.


public BinarySearchTreeNode findMax(BinarySearchTreeNode root){ if(root == null){ return null; } else{ if(root.getRight() == null){ return root; } else{ return findMax(root.getRight()); } } }

Time Complexity: O(n), trong trường hợp xấu nhất (khi BST là cây lệch trái). Space Complexity: O(n), đối với ngăn xếp đệ quy.

Phiên bản non recursive của thuật toán trên có thể là:


public BinarySearchTreeNode findMax(BinarySearchTreeNode root) { if (root == null) { return null; } while(root.getRight() != null){ root = root.getRight(); } return root; }

Time Complexity: O(n). Space Complexity: O(1).

Inorder Predecessor và Successor ở đâu?

Đâu là Inorder Predecessor(tiền nhiệm) và Successor(kế nhiệm) của node X trong cây tìm kiếm nhị phân giả sử tất cả các node là khác nhau?\

Nếu X có hai node con thì inorder predecessor của nó là giá trị lớn nhất trong cây con bên trái của nó và giá trị kế tiếp thứ tự của nó là giá trị nhỏ nhất trong cây con bên phải của nó.

Nếu nó không có con bên trái, thì node inorder predecessor là tổ tiên bên trái đầu tiên của nó.

Chèn một phần tử từ cây tìm kiếm nhị phân

Để chèn dữ liệu vào cây tìm kiếm nhị phân, trước tiên chúng ta cần tìm vị trí cho phần tử đó. Chúng ta có thể tìm vị trí chèn bằng cách làm theo cơ chế tương tự như cơ chế của thao tác tìm. Trong khi tìm vị trí, nếu dữ liệu đã có ở đó thì chúng ta chỉ cần bỏ qua và đi ra. Nếu không, hãy chèn dữ liệu vào vị trí cuối cùng trên đường dẫn đi qua.

Như một ví dụ, chúng ta hãy xem xét cây sau đây. node chấm chấm cho biết phần tử (5) sẽ được chèn vào. node có các gạch đứt cho biết phần tử (5) sẽ được chèn vào. Để chèn 5, duyệt qua cây bằng chức năng tìm. Tại node có giá trị 4, chúng ta cần đi sang phải, nhưng không có cây con, vì vậy 5 không có trong cây và đây là vị trí chính xác để chèn.


public BinarySearchTreeNode insert(BinarySearchTreeNode root, int data){ if(root == null){ root = new BinarySearchTreeNode(); if(root == null){ System.out.println("Memory error"); return null; } else{ root.setData(data); root.setLeft(null); root.setRight(null); } } else { if(data < root.getData()){ root.setLeft(insert(root.getLeft(), data)); } else if (data > root.getData()) { root.setRight(insert(root.getRight(), data)); } } return root; }

Lưu ý: Trong đoạn mã trên, sau khi chèn một phần tử vào cây con, cây được trả về node cha của nó. Time Complexity: O(n). Space Complexity: O(n), cho ngăn xếp đệ quy. Nếu sử dụng vòng lặp, space complexity là O(1).

Xóa một phần tử khỏi cây tìm kiếm nhị phân

Thao tác xóa phức tạp hơn các thao tác khác. Điều này là do phần tử bị xóa có thể không phải là node lá. Trong thao tác này cũng vậy, trước tiên chúng ta cần tìm vị trí của phần tử mà chúng ta muốn xóa. Khi chúng ta đã tìm thấy node bị xóa, hãy xem xét các trường hợp sau:

  • Nếu phần tử cần xóa là node lá: trả lại NULL cho cha mẹ của nó. Điều đó có nghĩa là tạo con trỏ con tương ứng NULL. Trong cây bên dưới để xóa 5, đặt NULL thành node cha của nó là 2.
  • Nếu phần tử bị xóa có một node con: Trong trường hợp này, chúng ta chỉ cần link node con của node hiện tại cho node cha của nó. Trong cây bên dưới, để xóa 4, cây con bên trái 4 được đặt thành node cha của nó là 2.
  • Nếu phần tử bị xóa có cả hai phần tử con: Chiến lược chung là thay thế giá trị của node này bằng phần tử lớn nhất của cây con bên trái và xóa node đó đi. node lớn nhất trong cây con bên trái không thể có node con bên phải, vì vậy thao tác xóa thứ hai là dễ dàng. Ví dụ, chúng ta hãy xem xét cây sau đây. Trong cây dưới đây, để xóa 8, nó là con bên phải của gốc. Giá trị chính là 8. Nó được thay thế bằng giá trị lớn nhất trong cây con bên trái của nó (7), và sau đó node đó bị xóa như trước (trường hợp thứ hai).

Lưu ý: Chúng ta cũng có thể thay thế bằng phần tử tối thiểu trong cây con bên phải.


public BinarySearchTreeNode delete(BinarySearchTreeNode root, int data){ BinarySearchTreeNode temp; if(root == null){ System.out.println("Element not there in tree"); } else if (data < root.getData()) { root.setLeft(delete(root.getLeft(), data)); } else if (data > root.getData()) { root.setRight(delete(root.getRight(), data)); } else{ // Found element if(root.getLeft() != null && root.getRight() != null){ // Replace with largest in left subtree temp = findMax(root.getLeft()); root.setData(temp.getData()); root.setLeft(delete(root.getLeft(), root.getData())); } else{ //One child if(root.getLeft() == null){ root = root.getRight(); } if(root.getRight() == null){ root = root.getLeft(); } } } return root; }

Time Complexity: O(n). Space Complexity: O(n), cho ngăn xếp đệ quy. Nếu sử dụng vòng lặp, space complexity là O(1).

All rights reserved

Cây tìm kiếm nhị phân – Binary search tree

Trong bài viết này, chúng ta sẽ tiếp tục tìm hiểu về cấu trúc dữ liệu Cây, và cụ thể là cây tìm kiếm nhị phân. Đây là một cấu trúc dữ liệu được dùng khá phổ biến và có tính ứng dụng cao. Hãy cùng Nguyễn Văn Hiếu tìm hiểu và cài đặt cây tìm kiếm nhị phân sử dụng ngôn ngữ C/C++ nhé.

NỘI DUNG BÀI VIẾT

M6 Tết 500ae đổ xô cắt bo giá rẻ 5k xem mặt hoa mai đất SBBL & cây Hùng Mỡ 500tr vườn mai Thành Công
M6 Tết 500ae đổ xô cắt bo giá rẻ 5k xem mặt hoa mai đất SBBL & cây Hùng Mỡ 500tr vườn mai Thành Công

Binary Search Tree: Điểm khởi đầu hoàn hảo

Một trong những cách chính để đánh giá chuyên môn của một kỹ sư là thông qua kiến thức và ứng dụng của họ về cấu trúc dữ liệu. Cấu trúc dữ liệu rất hữu ích và có thể giúp tạo ra một hệ thống hiệu quả hơn. Binary Search Tree là một khởi điểm tuyệt vời cho bất kỳ nhà phát triển nào để làm quen với cấu trúc dữ liệu.

Dịch từ: https://www.makeuseof.com/what-is-a-binary-search-tree/

>>> Nếu bạn đang có nhu cầu tìm hiểu về khóa học lập trình đi làm ngay. Hãy liên hệ với FUNiX ngay tại đây:

>>> Xem thêm chuỗi bài viết liên quan:

Ứng dụng học máy trong phân tích dữ liệu

5 công cụ phần mềm phân tích dữ liệu

Phân tích dữ liệu kinh doanh là làm gì năm 2022

Data analyst là gì? Tất cả những gì cần biết về nghề phân tích dữ liệu Data analyst

Vân Nguyễn

Code đầy đủ cây tìm kiếm nhị phân

#include

#include

typedef struct Node { int data; Node* left; Node* right; } node_t; void Free( node_t* root ) { if ( root == NULL ) return; Free( root->left ); Free( root->right ); free( root ); } int LeftOf( const int value, const node_t* root ) { // Nếu bạn muốn cây BST cho phép giá trị trùng lặp, hãy sử dụng dòng code thứ 2 return value < root->data; // return value <= root->data; } int RightOf( const int value, const node_t* root ) { return value > root->data; } node_t* Insert( node_t* root, const int value ) { if ( root == NULL ) { node_t* node = (node_t*)malloc( sizeof( node_t ) ); node->left = NULL; node->right = NULL; node->data = value; return node; } if ( LeftOf( value, root ) ) root->left = Insert( root->left, value ); else if ( RightOf( value, root ) ) root->right = Insert( root->right, value ); return root; } bool Search( const node_t* root, int value ) { if ( root == NULL ) return false; if(root->data == value){ return true; }else if ( LeftOf( value, root ) ){ return Search( root->left, value ); }else if( RightOf( value, root ) ){ return Search( root->right, value ); } } int LeftMostValue( const node_t* root ) { while ( root->left != NULL ) root = root->left; return root->data; } node_t* Delete( node_t* root, int value ) { if ( root == NULL ) return root; if ( LeftOf( value, root ) ) root->left = Delete( root->left, value ); else if ( RightOf( value, root ) ) root->right = Delete( root->right, value ); else { // root->data == value, delete this node if ( root->left == NULL ) { node_t* newRoot = root->right; free( root ); return newRoot; } if ( root->right == NULL ) { node_t* newRoot = root->left; free( root ); return newRoot; } root->data = LeftMostValue( root->right ); root->right = Delete( root->right, root->data ); } return root; } void PreOrder(node_t* root){ if(root != NULL) { printf(“%d “, root->data); PreOrder(root->left); PreOrder(root->right); } } void InOrder(node_t* root){ if(root != NULL) { InOrder(root->left); printf(“%d “, root->data); InOrder(root->right); } } void PostOrder(node_t* root){ if(root != NULL) { PostOrder(root->left); PostOrder(root->right); printf(“%d “, root->data); } } int main() { node_t* root = NULL; root = Insert( root, 25 ); root = Insert( root, 15 ); root = Insert( root, 50 ); root = Insert( root, 10 ); root = Insert( root, 22 ); root = Insert( root, 35 ); root = Insert( root, 70 ); root = Insert( root, 4 ); root = Insert( root, 12 ); root = Insert( root, 18 ); root = Insert( root, 24 ); root = Insert( root, 31 ); root = Insert( root, 44 ); root = Insert( root, 66 ); root = Insert( root, 90 ); printf(“\nDuyet preorder : “); PreOrder(root); printf(“\nDuyet inorder : “); InOrder(root); printf(“\nDuyet postorder:”); PostOrder(root); printf(“\n==Thu them phan tu 15 vao BTS==\n”); Insert(root, 15); printf(“\nDuyet preorder : “); PreOrder(root); printf(“\nDuyet inorder : “); InOrder(root); printf(“\nDuyet postorder:”); PostOrder(root); printf(“\n==Thu xoa phan tu 50 khoi BTS==\n”); Delete(root, 50); printf(“\nDuyet preorder : “); PreOrder(root); printf(“\nDuyet inorder : “); InOrder(root); printf(“\nDuyet postorder:”); PostOrder(root); Free( root ); root = NULL; return 0; }

Trong hàm main tôi đã cài đặt BTS cho cây nhị phân sau:

Nhờ các bạn kiểm tra kết quả chạy của code:

Duyet preorder : 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90 Duyet inorder : 4 10 12 15 18 22 24 25 31 35 44 50 66 70 90 Duyet postorder:4 12 10 18 24 22 15 31 44 35 66 90 70 50 25 ==Thu them phan tu 15 vao BTS== Duyet preorder : 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90 Duyet inorder : 4 10 12 15 18 22 24 25 31 35 44 50 66 70 90 Duyet postorder:4 12 10 18 24 22 15 31 44 35 66 90 70 50 25 ==Thu xoa phan tu 50 khoi BTS== Duyet preorder : 25 15 10 4 12 22 18 24 66 35 31 44 70 90 Duyet inorder : 4 10 12 15 18 22 24 25 31 35 44 66 70 90 Duyet postorder:4 12 10 18 24 22 15 31 44 35 90 70 66 25 Process returned 0 (0x0) execution time : 0.047 s Press any key to continue.

Vào lệnh với ĐỌC NẾN mà không cần PHÂN TÍCH NHIỀU
Vào lệnh với ĐỌC NẾN mà không cần PHÂN TÍCH NHIỀU

Lý thuyết về cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân(TA: Binary Search Tree – viết tắt: BST) – là một cây nhị phân và có thêm các ràng buộc sau đây:

  1. Giá trị của tất cả các Node ở cây con bên trái phải <= giá trị của Node gốc.
  2. Giá trị của tất cả các Node ở cây con bên phải phải > giá trị của Node gốc.
  3. Tất cả các cây con(bao gồm bên trái và phải) cũng đều phải đảm bảo 2 tính chất trên.

Cây tìm kiếm nhị phân là một cấu trúc dữ liệu hiệu quả cho phép chúng ta xây dựng nên một danh sách mà dữ liệu trên đó được sắp xếp:

  • Nó được gọi là cây nhị phân vì mỗi Node của cây chỉ có tối đa hai con
  • Nó được gọi là cây tìm kiếm nhị phân vì nó có thể được sử dụng để tìm kiếm sự hiện diện của một phần tử trong thời gian O(log (n)).

Tham khảo[sửa | sửa mã nguồn]

Trích dẫn[sửa | sửa mã nguồn]

  1. ^ Rowan Garnier; John Taylor (2009). Discrete Mathematics: Proofs, Structures and Applications, Third Edition. CRC Press. tr. 620. ISBN 978-1-4398-1280-8.
  2. ^ Steven S Skiena (2009). The Algorithm Design Manual. Springer Science & Business Media. tr. 77. ISBN 978-1-84800-070-4.
  3. ^ a b Knuth (1997). The Art Of Computer Programming, Volume 1, 3/E. Pearson Education. tr. 363. ISBN 0-201-89683-4.
  4. ^ Iván Flores (1971). Computer programming system/360. Prentice-Hall. tr. 39.
  5. ^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. tr. 749. ISBN 978-0-07-338309-5.
  6. ^ David R. Mazur (2010). Combinatorics: A Guided Tour. Mathematical Association of America. tr. 246. ISBN 978-0-88385-762-5.
  7. ^ Tamassia, Michael T. Goodrich, Roberto (2011). Algorithm design : foundations, analysis, and Internet examples (ấn bản 2). New Delhi: Wiley-India. tr. 76. ISBN 978-81-265-0986-7.
  8. ^ “cây nhị phân đầy đủ”. NIST.
  9. ^ Richard Stanley, Enumerative Combinatorics, volume 2, p.36
  10. ^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications 7th edition. McGraw-Hill Science. tr. 352–353. ISBN 978-0-07-338309-5.
  11. ^ “cây nhị phân hoàn hảo”. NIST.
  12. ^ a b “cây nhị phân hoàn chỉnh”. NIST.
  13. ^ “cây nhị phân gần như hoàn chỉnh”. Bản gốc lưu trữ ngày 4 tháng 3 năm 2016. Truy cập ngày 11 tháng 12 năm 2015.
  14. ^ “cây nhị phân hầu như hoàn chỉnh” (PDF). Lưu trữ (PDF) bản gốc ngày 9 tháng 10 năm 2022.
  15. ^ Aaron M. Tenenbaum, et al. Data Structures Using C, Prentice Hall, 1990 ISBN 0-13-199746-7
  16. ^ Paul E. Black (ed.), mục cấu trúc dữ liệu trong Dictionary of Algorithms and Data Structures. Viện National Institute of Standards and Technology của Mỹ. 15 tháng 12 năm 2004. Phiên bản trực tuyến Lưu trữ tháng 12 21, 2010 tại Wayback Machine Truy cập ngày 2010-12-19.
  17. ^ Parmar, Anand K. (22 tháng 1 năm 2020). “Các loại cây nhị phân với minh họa đầy màu sắc”. Medium (bằng tiếng Anh). Truy cập ngày 24 tháng 1 năm 2020.

Thư mục[sửa | sửa mã nguồn]

  • Donald Knuth. The Art of Computer Programming vol 1. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3, especially subsections 2.3.1–2.3.2 (pp. 318–348).
Chuyện Về Cô Điếc - ĐÁNG SUY NGẪM | Đọc Truyện Đêm Khuya Đài Tiếng Nói Việt Nam VOV Ngủ Ngon Nhất
Chuyện Về Cô Điếc – ĐÁNG SUY NGẪM | Đọc Truyện Đêm Khuya Đài Tiếng Nói Việt Nam VOV Ngủ Ngon Nhất

Điều kiện sử dụng

Nếu chúng ta chỉ cần xác định vị trí của một phần tử nào đó, lựa chọn đầu tiên nên là giải pháp dựa trên hàm băm. Để sử dụng cây tìm kiếm nhị phân, ta cần cân nhắc các yếu tố:

  • Kích thước tập dữ liệu không xác định và việc cài đặt phải có khả năng xử lý bất kỳ kích thước có thể nào làm cho phù hợp với bộ nhớ.

  • Tập dữ liệu có tính động cao và sẽ có nhiều lần chèn và xóa trong suốt thời gian tồn tại của cấu trúc dữ liệu.

  • Ứng dụng yêu cầu duyệt dữ liệu theo thứ tự tăng dần hoặc giảm dần.

Khi quyết định sử dụng cây tìm kiếm, ta phải đưa ra các phương án thiết kế cây sao cho phù hợp:

  • Nếu ta cần duyệt tập dữ liệu theo thứ tự bắt đầu từ bất kỳ nút cụ thể nào, thì các con trỏ thích hợp đến các nút cha phải được đưa vào cấu trúc nút.

  • Nếu dữ liệu là động, chúng ta phải thiết kế sao cho cây cân đối.

Trong hầu hết các ứng dụng, chúng ta cần cân đối cây để tránh cây bị lệch, đó là có một vài nhánh dài hơn hoặc ngắn hơn nhiều so với các nhánh khác. Một loại cây nhị phân cân đôi được sử dụng gọi là cây đỏ đen. Các cây đỏ đen xấp xỉ cân đối. Sử dụng một cây đỏ đen đảm bảo rằng không có nhánh nào có chiều cao hơn hai lần so với bất kỳ nhánh nào khác. Cây đỏ đen thỏa mãn các điều kiện sau:

  • Mọi nút đều được dán nhãn đỏ hoặc đen.

  • Gốc có màu đen.

  • Mọi nút lá đều chứa giá trị rỗng và có màu đen.

  • Tất cả các nút màu đỏ có hai nút con màu đen.

  • Mọi đường đi đơn giản từ một nút đến một trong các nút lá con của nó đều chứa cùng một số nút đen.

Trong các sơ đồ tiếp theo, mình không hiển thị các nút lá có giá trị null. Khi nhìn vào sơ đồ, bạn hãy tưởng tượng rằng mỗi nút lá trong sơ đồ thực sự có hai nút con màu đen và chúng có giá trị null.

Các hoạt động cơ bản của cây tìm kiếm nhị phân

Bây giờ bạn đã hiểu rõ hơn về định nghĩa Binary Search Tree, hãy cùng xem xét các operation (hoạt động) cơ bản của nó.

2.1 Search (Tìm kiếm)

Tìm kiếm cho phép xác định một giá trị cụ thể có trong cây. Chúng ta có thể sử dụng hai loại tìm kiếm: tìm kiếm theo chiều rộng (breadth-first search, hay BFS) và tìm kiếm theo chiều sâu (depth-first search, hay DFS). Tìm kiếm theo chiều rộng là một thuật toán tìm kiếm bắt đầu từ nút gốc và di chuyển theo chiều ngang, từ bên này sang bên kia, cho đến khi tìm thấy mục tiêu. Mỗi nút được truy cập một lần trong quá trình tìm kiếm này.

Mặt khác, tìm kiếm theo chiều sâu đi qua cây theo chiều dọc – bắt đầu từ nút gốc và đi dọc xuống một nhánh duy nhất. Nếu mục tiêu được tìm thấy, operation kết thúc. Nhưng nếu không, nó sẽ tìm kiếm các nút khác.

2.2 Insert (Chèn)

Thao tác chèn sử dụng thao tác tìm kiếm để xác định vị trí nơi nút mới sẽ được chèn. Quá trình này bắt đầu từ nút gốc và quá trình tìm kiếm bắt đầu cho đến khi đến đích. Có ba trường hợp cần xem xét:.

  • Trường hợp 1: Khi không có nút nào tồn tại. Nút được chèn vào sẽ trở thành nút gốc.
  • Trường hợp 2: Không có con. Trong trường hợp này, nút được chèn sẽ được so sánh với nút gốc. Nếu nó lớn hơn, nó sẽ trở thành nút con bên phải; nếu không, nó sẽ trở thành nút con trái.
  • Trường hợp 3: Khi có cả nút gốc và con của nó. Nút mới sẽ được so sánh với mỗi nút trên đường dẫn của nó để xác định nút nào nó sẽ truy cập tiếp theo. Nếu nút này lớn hơn nút gốc, nó sẽ đi qua cây con bên phải, nếu không thì bên trái. Tương tự, so sánh được thực hiện ở mỗi cấp độ để xác định xem nó sẽ đi sang phải hay sang trái cho đến khi đến đích.

2.3 Delete (Xóa)

Thao tác xóa được sử dụng để xóa một nút cụ thể trong cây. Việc này khá phức tạp vì sau khi xóa một nút, cây phải được tổ chức lại cho phù hợp. Có ba trường hợp chính cần xem xét:

  • Trường hợp 1: Xóa một nút lá (leaf node). Nút lá là nút không có nút con nào. Đây là nút dễ nhất để loại bỏ vì nó không ảnh hưởng đến bất kỳ nút nào khác; chúng ta chỉ cần đi dọc cây cho đến khi đến vị trí của nó và xóa nó đi.
  • Trường hợp 2: Xóa một nút cha có một nút con. Việc này sẽ dẫn đến việc nút con chiếm vị trí của nó và tất cả các nút tiếp theo sẽ tăng lên một cấp. Sẽ không có thay đổi về cấu trúc cây con.
  • Trường hợp 3: Xóa một nút cha có hai nút con. Khi loại bỏ một nút có hai nút con, trước tiên chúng ta phải tìm một nút tiếp theo có thể thay thế vị trí của nó. Hai nút có thể thay thế nút đã bị loại bỏ: inorder successor hoặc inorder predecessor. Inorder successor là con ngoài cùng bên trái của cây con bên phải và inorder predecessor là con ngoài cùng bên phải của cây con bên trái. Chúng ta sẽ sao chép nội dung của nút successor (kế nhiệm)/predecessor (tiền nhiệm) và xóa inorder successor/predecessor.
LAN VY | #0326408040 | NĂM MỚI MAY MẮN PHÁT TÀI. BS LAN VY GIỚI THIỆU NHIỀU TÁC PHẨM LŨA ĐỘC ĐẸP !!!
LAN VY | #0326408040 | NĂM MỚI MAY MẮN PHÁT TÀI. BS LAN VY GIỚI THIỆU NHIỀU TÁC PHẨM LŨA ĐỘC ĐẸP !!!

Mô tả thuật toán

Tìm kiếm trên cây đỏ đen không khác gì so với tìm kiếm bất kỳ trên cây nhị phân nào. Bắt đầu từ gốc, ta kiểm tra từng nút để tìm giá trị khóa đã cho, chuyển sang nút con bên trái nếu giá trị khóa nhỏ hơn giá trị khóa cần tìm kiếm và chuyển sang nút con bên phải nếu giá trị khóa lớn hơn.

Code java của thuật toán tìm kiếm nhị phân trên cây:


public V search(K k) { BalancedBinaryNode

p = root; while (p != null) { int cmp = compare(k, p.key); if (cmp == 0) { return p.value; } else if (cmp < 0) { p = p.left; } else { p = p.right; } } // not found return null; }

Để chèn một nút vào cây đỏ đen, ta cần tìm vị trí thích hợp trong cây mà nút mới sẽ được đặt. Khi chúng ta thêm giá trị 14 vào cây trong hình 3, một nút mới chứa 14 sẽ trở thành nút con bên phải của nút lá chứa giá trị 13 (có nhãn “Step 1” trong hình 4). Sau khi chèn vào, các thuộc tính của cây đỏ đen bị xâm phạm nên cây phải tự điều chỉnh. Ở bước 2, màu sắc của các nút được cập nhật để đảm bảo điều kiện 4 của cây đỏ đen. Ở bước 3, cây được xoay sang phải để đảm bảo điều kiện 5 của cây đỏ đen. Cuối cùng, ở Bước 4, màu sắc của các nút được cập nhật để đảm bảo điều kiện 4 của cây.

Thao tác cơ bản khi thay đổi cấu trúc cây là xoay về một nút. Ta sửa đổi các nút con trong cây để thực hiện thao tác xoay. Hình dưới cho thấy kết quả của việc xoay trái hoặc phải về một nút. Có thể xoay cây bên trái về nút a để thành cây bên phải. Tương tự, bạn có thể thực hiện một phép xoay bên phải về nút b để từ cây bên phải thành cây bên trái.

Ta thấy rằng để thực hiện các phép xoay, cấu trúc nút trong cây đỏ đen cần có các con trỏ cha. Code java để thực hiện xoay trái được trình bày bên dưới (xoay phải tương tự):


protected void rotateLeft(BalancedBinaryNode

p) { BalancedBinaryNode

r = p.right; p.right = r.left; if (r.left != null) r.left.parent = p; r.parent = p.parent; if (p.parent == null) root = r; else if (p.parent.left == p) p.parent.left = r; else p.parent.right = r; r.left = p; p.parent = r; }

Lưu ý rằng các phép xoay đảm bảo thuộc tính cây tìm kiếm nhị phân vì thứ tự của các nút là không thay đổi. Khi giá trị mới được chèn, cây sẽ tự cập nhật để khôi phục điều kiện 4 và 5 của cây đỏ đen.

Liên kết ngoài[sửa | sửa mã nguồn]

Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Cây nhị phân.
  • binary trees Lưu trữ 2020-09-23 tại Wayback Machine entry in the FindStat database
  • Gamedev.net introduction on binary trees
  • Binary Tree Proof by Induction
  • Balanced binary search tree on array How to create bottom-up an Ahnentafel list, or a balanced binary search tree on array
  • Binary trees and Implementation of the same with working code examples

CÂY, CÂY NHỊ PHÂN, CÂY NHỊ PHÂN TÌM KIẾM

1.1. Định nghĩa Cấu trúc cây 1:Cây là một tập hợp T các phần tử (nút trên cây) trong đó có 1 nút đặc biệt T0 được gọi là gốc, các nút còn khác được chia thành những tập rời nhau T1, T2 , … , Tn theo quan hệ phân cấp trong đó Ti cũng là một cây.Nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta còn gọi là quan hệ cha-con.

1.2. Một số khái niệm cơ bản- Bậc của một nút: là số cây con của nút đó .- Bậc của một cây: là bậc lớn nhất của các nút trong cây. Cây có bậc n thì gọi là cây n-phân.- Nút gốc: nút không có nút cha.- Nút lá: nút có bậc bằng 0 .- Nút nhánh: nút có bậc khác 0 và không phải là gốc .- Mức của một nút:Mức (T0 ) = 1.Gọi T1, T2, T3, … , Tn là các cây con của T0Mức (T1) = Mức (T2) = … = Mức (Tn) = Mức (T0) + 1.- Độ dài đường đi từ gốc đến nút x: là số nhánh cần đi qua kể từ gốc đến x.- Chiều cao h của cây: mức lớn nhất của các nút lá.

1.3. Một số ví dụ về đối tượng các cấu trúc dạng cây- Sơ đồ tổ chức của một doanh nghiệp- Sơ đồ tổ chức cây thư mục

2. CÂY NHỊ PHÂN2.1 Định nghĩaCây nhị phân là cây mà mỗi nút có tối đa 2 cây con

Cây nhị phân có thể ứng dụng trong nhiều bài toán thông dụng. Ví dụ dưới đây cho ta hình ảnh của một biểu thức toán học:

2.2. Một số tính chất của cây nhị phân:

– Số nút ở mức I ≤ 2

I-1

– Số nút ở mức lá ≤ 2

h-1

, với h là chiều cao của cây.

– Chiều cao của cây h ≥ log

2

N (N – số nút trên trong cây).

2.3. Biểu diễn cây nhị phân T

Cây nhị phân là một cấu trúc bao gồm các phần tử (nút) được kết nối với nhau theo quan hệ “cha-con” với mỗi cha có tối đa 2 con. Để biểu diễn cây nhị phân ta chọn phương pháp cấp phát liên kết. Ứng với một nút, ta dùng một biến động lưu trữ các thông tin:

+ Thông tin lưu trữ tại nút.

+ Địa chỉ nút gốc của cây con trái trong bộ nhớ.

+ Địa chỉ nút gốc của cây con phải trong bộ nhớ.

Khai báo như sau:


typedef struct
tagTNODE {
Data Key; //Data là kiểu dữ liệu ứng với thông tin lưu tại nút
struct tagNODE * pLeft, * pRight;
}
TNODE;
typedef TNODE * TREE;

2.4. Các thao tác trên cây nhị phânThăm các nút trên cây theo thứ tự trước (Node-Left-Right)


void NLR(TREE Root) {
if (Root != NULL) {
//Xử lý tương ứng theo nhu cầu
//

;
NLR(Root -> pLeft);
NLR(Root -> pRight);
}
}

Thăm các nút trên cây theo thứ tự giữa (Left- Node-Right)


void LNR(TREE Root) {
if (Root != NULL) {
LNR(Root -> Left);
//

;
LNR(Root -> Right);
//Xử lý tương ứng theo nhu cầu
}
}

Thăm các nút trên cây theo thứ tự sau (Left-Right-Node)


void LRN(TREE Root) {
if (Root != NULL) {
LRN(Root -> Left);
LRN(Root -> Right);
//

;
//Xử lý tương ứng theo nhu cầu
}
}

Ứng dụng phương pháp này trong việc tính tổng kích thước của thư mục.

Ứng dụng tính toán giá trị của biểu thức.

2.5. Biểu diễn cây tổng quát bằng cây nhị phânNhược điểm của các cấu trúc cây tổng quát là bậc của các nút trên cây có thể rất khác nhau ⇒ việc biểu diễn gặp nhiều khó khăn và lãng phí. Hơn nữa, việc xây dựng các thao tác trên cây tổng quát phức tạp hơn trên cây nhị phân nhiều.Vì vậy, nếu không quá cần thiết phải sử dụng cây tổng quát, người ta sẽ biến đổi cây tổng quát thành cây nhị phân.Ta có thể biến đổi một cây bất kỳ thành một cây nhị phân theo qui tắc sau:- Giữ nút con trái nhất làm con trái.- Các nút con còn lại biển đổi thành nút con phải.VD: Giả sử có cây tổng quát như hình sau:

2.6. Một cách biểu diễn cây nhị phân khác

Đôi khi, trên cây nhị phân, người ta quan tâm đến cả quan hệ chiều cha con. Khi đó, cấu trúc cây nhị phân có thể định nghĩa lại như sau:


typedef struct tagTNode {
DataType Key;
struct tagTNode * pParent;
struct tagTNode * pLeft;
struct tagTNode * pRight;
}
TNODE;
typedef TNODE * TREE;

3. CÂY NHỊ PHÂN TÌM KIẾM3.1. Định nghĩa

: Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải.

Dưới đây là một ví dụ về cây nhị phân tìm kiếm:

Nhờ ràng buộc về khóa trên CNPTK, việc tìm kiếm trở nên có định hướng. Hơn nữa, do cấu trúc cây việc tìm kiếm trở nên nhanh đáng kể. Chi phí tìm kiếm trung bình chỉ khoảng log

2

N.

3.2. Các thao tác trên cây

3.2.1. Thăm các nút trên cây

3.2.2. Tìm một phần tử x trong cây

Thuật Toán: Dễ dàng thấy rằng số lần so sánh tối đa phải thực hiện để tìm phần tử X là bằng h, với h là chiều cao của cây.

Ví dụ: Tìm phần tử 55

3.3.3. Thêm một phần tử x vào câyViệc thêm một phần tử X vào cây phải bảo đảm điều kiện ràng buộc của CNPTK. Ta có thể thêm vào nhiều vị trí khác nhau trên cây, nhưng nếu thêm vào một nút lá thì sẽ dễ nhất do ta có thể thực hiện quá trình tương tự thao tác tìm kiếm. Khi chấm dứt quá trình tìm kiếm ta sẽ tìm được vị trí cần thêm.

Hàm insert trả về giá trị –1, 0, 1 khi không đủ bộ nhớ, gặp nút cũ hay thành công:


int insertNode(TREE & T, Data X) {
if (T) {
if (T -> Key == X) return 0; //đã có
if (T -> Key > X)
return insertNode(T -> pLeft, X);
else
return insertNode(T -> pRight, X);
}
T
= new TNode;
if (T == NULL)
return -1; //thiếu bộ nhớ
T -> Key = X;
T -> pLeft = T -> pRight = NULL;
return 1; //thêm vào thành công
}

2.4. Hủy một phần tử có khóa x

Việc hủy một phần tử X ra khỏi cây phải bảo đảm điều kiện ràng buộc của CNPTK.

Có 3 trường hợp khi hủy nút X có thể xảy ra:

  • X – nút lá.
  • X – chỉ có 1 cây con (trái hoặc phải).
  • X có đủ cả 2 cây con

Trường hợp thứ nhất: chỉ đơn giản hủy X vì nó không móc nối đến phần tử nào khác.

Trường hợp thứ hai: trước khi hủy X ta móc nối cha của X với con duy nhất của nó.

Trường hợp cuối cùng: ta không thể hủy trực tiếp do X có đủ 2 con ⇒ Ta sẽ hủy gián tiếp. Thay vì hủy X, ta sẽ tìm một phần tử thế mạng Y. Phần tử này có tối đa một con. Thông tin lưu tại Y sẽ được chuyển lên lưu tại X.Sau đó, nút bị hủy thật sự sẽ là Y giống như 2 trường hợp đầu.Vấn đề là phải chọn Y sao cho khi lưu Y vào vị trí của X, cây vẫn là CNPTK.

Có 2 phần tử thỏa mãn yêu cầu:

  • Phần tử nhỏ nhất (trái nhất) trên cây con phải.
  • Phần tử lớn nhất (phải nhất) trên cây con trái.

Việc chọn lựa phần tử nào là phần tử thế mạng hoàn toàn phụ thuộc vào ý thích của người lập trình. Ở đây, cháng tôi sẽ chọn phần tử (phải nhất trên cây con trái làm phân tử thế mạng.VD: Cần hủy phần tử 18.

2.5. ĐÁNH GIÁTất cả các thao tác Tìm kiếm, Thêm mới, Xóa trên CNPTK đều có độ phức tạp trung bình O(h), với h là chiều cao của câyTrong trong trường hợp tốt nhất, CNPTK có n nút sẽ có độ cao h = log2(n). Chi phí tìm kiếm khi đó sẽ tương đương tìm kiếm nhị phân trên mảng có thứ tự.Tuy nhiên, trong trường hợp xấu nhất, cây có thể bị suy biến thành 1 DSLK. Lúc đó các thao tác trên sẽ có độ phức tạp O(n). Vì vậy cần có cải tiến cấu trúc của CNPTK để đạt được chi phí cho các thao tác là log2(n).

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

Như mình đã trình bày trong bài viết trước, tìm kiếm nhị phân trên một mảng thể hiện sự hiệu quả. Tuy nhiên, hiệu suất của việc tìm kiếm trên mảng bị giảm đi rất nhiều khi dữ liệu trong tập dữ liệu thay đổi thường xuyên. Với tập dữ liệu động, ta phải áp dụng cấu trúc dữ liệu khác để duy trì hiệu suất tìm kiếm ở mức chấp nhận được.

Cây tìm kiếm là cấu trúc dữ liệu phổ biến nhất được sử dụng để lưu trữ các tập dữ liệu động. Loại cây tìm kiếm phổ biến nhất là cây tìm kiếm nhị phân, trong đó mỗi nút bên trong cây có nhiều nhất hai nút con. Một loại cây tìm kiếm khác, được gọi là B-Tree, là một cây n-ary được thiết kế để dễ dàng lưu trữ trên đĩa nhớ.

Phân tích thuật toán

Nhạc Xuân Mới Nhất 2024 - Mùa Xuân Của Mẹ | Nhạc Xuân Nghe Mà Nhớ Mẹ Song Ca Quang Lập Thu Hường
Nhạc Xuân Mới Nhất 2024 – Mùa Xuân Của Mẹ | Nhạc Xuân Nghe Mà Nhớ Mẹ Song Ca Quang Lập Thu Hường

Binary Search Tree là gì?

Binary Search Tree là một cấu trúc dữ liệu bao gồm các nút (node) — tương tự như Linked Lists (Danh sách được liên kết). Có hai loại nút: parent (nút cha) và child (nút con). Root node (nút gốc) là điểm đầu của cấu trúc phân nhánh thành hai nút con, được gọi là left node (nút bên trái) và right node (nút bên phải).

Mỗi nút chỉ có thể được tham chiếu bởi parent của nó và chúng ta có thể đi qua các nút của cây tùy thuộc vào hướng. Binary Search Tree có ba thuộc tính chính:

  1. Nút bên trái nhỏ hơn nút cha của nó.
  2. Nút bên phải lớn hơn nút cha của nó.
  3. Các cây con bên trái và bên phải bắt buộc phải là Binary Search Tree.

Chúng ta đạt được Binary Search Tree hoàn hảo khi tất cả các cấp được lấp đầy và mọi nút đều có nút con bên trái và bên phải.

>>> Xem thêm: Hướng dẫn sử dụng cấu trúc cây, cây tìm kiếm nhị phân

Cài đặt

Cài đặt trong C++:


Node *find_remove(Node *root, int key) { if (root == NULL) return NULL; if (root->key == key) { if (root->left == NULL && root->right == NULL) return NULL; if (root->left != NULL && root->right != NULL) { // Tìm nút thay thế Node *successor = root->right; while (successor->left != NULL) successor = successor->left; root->key = successor->key; find_remove(root->right, successor->key); return root; } if (root->left != NULL) return root->left; else return root->right; } if (key > root->key) root->right = find_remove(root->right, key); else root->left = find_remove(root->left, key); return root; }

Khi gọi hàm, tương tự như khi thêm nút, ta cũng phải gán:


root = find_remove(root, key);

Độ phức tạp

Độ phức tạp của các thao tác trên tùy thuộc vào độ cao của cây khi truy vấn. Với dữ liệu ngẫu nhiên, cách cài đặt cây nhị phân trong bài này có độ phức tạp trung bình cho mỗi thao tác là \(O(\log N)\), với \(N\) là số nút trên cây.

Tuy nhiên, độ phức tạp trong trường hợp xấu nhất là \(O(N)\), vì vậy cây này không được sử dụng trong thực tế.

Cây nhị phân

Trong khoa học máy tính, cây nhị phân (tiếng Anh: binary tree) là một cấu trúc dữ liệu cây mà mỗi nút có nhiều nhất hai nút con, được gọi là con trái (left child) và con phải (right child). Một định nghĩa đệ quy chỉ sử dụng các khái niệm lý thuyết tập hợp là cây nhị phân không trống là một tuple (L, S, R), với L và R là các cây nhị phân hay tập hợp rỗng và S là tập đơn (singleton set).[1] Một số tác giả cho phép cây nhị phân cũng có thể là tập hợp trống.[2]

Từ góc độ lý thuyết đồ thị, cây nhị phân (và K-ary) như định nghĩa ở đây thực sự là arborescence.[3] Vì vậy cây nhị phân có thể gọi là arborescence phân nhánh đôi (bifurcating arborescence)[3]—một thuật ngữ xuất hiện trong các sách lập trình rất cũ,[4] trước khi thuật ngữ khoa học máy tính hiện đại chiếm ưu thế. Cũng có thể hiểu cây nhị phân là một đồ thị vô hướng chứ không phải đồ thị có hướng, trong trường hợp đó cây nhị phân là một cây có gốc và thứ tự[5] Một số tác giả dùng thuật ngữ cây nhị phân có gốc thay vì cây nhị phân để nhấn mạnh thực tế rằng cây có gốc, nhưng như được định nghĩa ở trên thì cây nhị phân luôn có gốc.[6] Cây nhị phân là trường hợp đặc biệt của cây K-ary, với k bằng 2.

(P2) Tucker Carlson Phỏng Vấn Putin:\
(P2) Tucker Carlson Phỏng Vấn Putin:\”Hãy Hỏi Biden\” | Kiến Thức Chuyên Sâu

Nhận xét

Cây đỏ đen hay các cây nhị phân cân đối khác yêu cầu phải code dài hơn so với cây tìm kiếm nhị phân đơn giản. Sự đánh đổi này đáng giá về hiệu suất thời gian chạy . Cây đỏ đen có hai yêu cầu lưu trữ đối với cấu trúc dữ liệu được sử dụng cho các nút như sau:

  • Mỗi nút yêu cầu bộ nhớ để lưu trữ màu của nút. Đây là mức tối thiểu là một bit, nhưng trong thực tế, hầu hết các cài đặt sử dụng ít nhất một byte.

  • Mọi nút phải có một liên kết cha, đây không phải là một yêu cầu đối với cây tìm kiếm nhị phân.

Cây đỏ đen cũng yêu cầu một nút có giá trị null ở gốc. Người ta có thể thực hiện điều này bằng cách sử dụng một nút có giá trị null và làm cho tất cả các con trỏ của nút lá trỏ đến nó.

Các loại cây nhị phân[sửa | sửa mã nguồn]

Thuật ngữ về cây không được chuẩn hóa tốt và do đó thay đổi trong các tài liệu.

  • Một cây nhị phân gốc có một nút gốc và mỗi nút có tối đa hai nút con.
  • Một cây nhị phân đầy đủ (đôi khi được gọi là đúng đắn[7] hay phẳng hay cây nhị phân nghiêm ngặt)[8] [9] là một cây có mỗi nút đều có hoặc không có hoặc 2 nút con. Một cách định nghĩa khác cho cây nhị phân đầy đủ là một cách định nghĩa đệ quy. Một cây nhị phân đầy đủ gồm:[10]

    • Một đỉnh đơn lẻ (một nút đơn lẻ làm nút gốc).
    • Một cây có nút gốc có hai nhánh con, cả hai đều là cây nhị phân đầy đủ.
  • Một cây nhị phân hoàn hảo là một cây nhị phân mà tất cả các nút bên trong đều có hai nút con và tất cả các nút lá đều có cùng độ sâu hoặc cùng cấp độ (cấp độ của một nút được định nghĩa là số đường nối từ nút gốc đến nút đó).[11] Một ví dụ về cây nhị phân hoàn hảo là biểu đồ tổ tiên của một người đến một độ sâu nhất định nhỏ hơn mức mà tổ tiên sẽ xuất hiện nhiều hơn một lần trong biểu đồ (tại thời điểm này, biểu đồ không còn là một cây có các nút duy nhất; chú ý là cùng một tổ tiên có thể xuất hiện ở các độ sâu khác nhau trong biểu đồ), vì mỗi người có đúng hai cha mẹ sinh học (một mẹ và một cha). Miễn là biểu đồ tổ tiên luôn hiển thị mẹ và cha ở cùng một bên cho một nút nhất định, giới tính của họ có thể được coi là tương đương với nút con trái và phải, con ở đây được hiểu là một thuật ngữ thuật toán. Một cây nhị phân hoàn hảo là một cây nhị phân đầy đủ, nhưng đảo ngược của nó không nhất thiết đúng.
  • Một cây nhị phân hoàn chỉnh là một cây nhị phân trong đó mọi cấp độ, ngoại trừ có thể là cấp cuối cùng, đều được lấp đầy hoàn toàn và tất cả các nút ở cấp cuối cùng nằm càng bên trái càng tốt. Nó có thể có từ 1 đến 2h nút ở cấp cuối cùng h.[12] Một cây hoàn hảo vì vậy luôn luôn là hoàn chỉnh nhưng một cây hoàn chỉnh không nhất thiết hoàn hảo. Một số tác giả sử dụng thuật ngữ hoàn chỉnh để chỉ một cây nhị phân hoàn hảo như được định nghĩa ở trên, trong trường hợp đó họ gọi loại cây này (với một cấp cuối không nhất thiết phải lấp đầy) là cây nhị phân gần như hoàn chỉnh hoặc hầu như hoàn chỉnh.[13][14] Một cây nhị phân hoàn chỉnh có thể được biểu diễn hiệu quả bằng một mảng.[12]
  • Trong cây nhị phân vô hạn hoàn chỉnh, cây có cấp độ, trong đó ở mỗi cấp độ d số nút hiện có ở cấp độ d bằng 2d. Số lượng phần tử của tập hợp tất cả các cấp độ là (vô hạn đếm được). Số lượng phần tử của tập hợp tất cả các đường đi (các “lá”, cứ coi như vậy) là không đếm được, có số lượng của liên tục.
  • Một cây nhị phân cân bằng là một cấu trúc cây nhị phân trong đó nhánh con trái và nhánh con phải của mỗi nút không chênh lệch về chiều cao (số đường nối từ nút trên cùng đến nút xa nhất trong nhánh con) không quá 1.[15] Người ta cũng có thể xem xét các cây nhị phân trong đó không có lá nào xa gốc hơn các lá khác. (Các lược đồ cân bằng khác nhau cho phép các định nghĩa khác nhau về “xa hơn”. [16])
  • Một cây tàu lượn (hoặc bệnh lý) là một cây mà mỗi nút cha chỉ có một nút con liên quan.[17] Điều này có nghĩa là cây sẽ hoạt động như một cấu trúc dữ liệu danh sách liên kết. Trong trường hợp này, lợi ích của việc sử dụng cây nhị phân bị giảm đáng kể vì nó về cơ bản là một danh sách liên kết có độ phức tạp độ phức tạp thời gian là O(n) (n là số nút) và nó có nhiều không gian dữ liệu hơn danh sách liên kết do hai con trỏ cho mỗi nút, trong khi độ phức tạp O(log2n) cho tìm kiếm dữ liệu trong cây nhị phân cân bằng thường được mong đợi.
Dựng cây nhị phân tìm kiếm từ 1 dãy số cho trước
Dựng cây nhị phân tìm kiếm từ 1 dãy số cho trước

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

Cây nhị phân tìm kiếm là cây nhị phân mà trong đó, các phần tử của cây con bên trái đều nhỏ hơn phần tử hiện hành và các phần tử của cây con bên phải đều lớn hơn phần tử hiện hành. Do tính chất này, cây nhị phân tìm kiếm không được có phần tử cùng giá trị.

Nhờ vào tính chất đặc biệt này, cây nhị phân tìm kiếm được sử dụng để tìm kiếm phần tử nhanh hơn (tương tự với tìm kiếm nhị phân). Khi duyệt cây nhị phân theo cách duyệt trung tự, bạn sẽ thu được một mảng có thứ tự. Chúng ta sẽ lần lượt tìm hiểu qua chúng.

Thêm phần tử vào cây nhị phân tìm kiếm

Để thêm phần tử vào cây nhị phân tìm kiếm, ta phải thêm vào cây nhưng vẫn đảm bảo được cây đó vẫn là cây nhị phân tìm kiếm. Ví dụ thêm phần tử 12 vào cây trong hình trên, mình sẽ cần chèn vào vị trí bên trái 13. Hàm duyệt tìm vị trí thích hợp và chèn của mình như sau:


void AddNode(Tree &root, Node *node) { if (root) { if (root->data == node->data) // Nếu bị trùng giá trị thì không thêm return; if (node->data < root->data) // Thêm vào cây con bên trái (nhỏ hơn nút hiện tại) AddNode(root->left, node); else AddNode(root->right, node); // Thêm vào cây con bên phải (lớn hơn nút hiện tại) } else { root = node; // Đã tìm thấy vị trí thích hợp, thêm node vào } }

Tìm một phần tử trong cây nhị phân tìm kiếm

Như đã giới thiệu ở trên, để tìm một phần tử trong cây nhị phân tìm kiếm, chúng ta sẽ thực hiện tương tự việc tìm kiếm nhị phân. Nếu như nút cần tìm nhỏ hơn nút đang xét, chúng ta sẽ tìm cây con bên trái, ngược lại chúng ta sẽ tìm trong cây con bên phải, nếu đúng nút cần tìm thì mình sẽ trả về địa chỉ của nút đó. Mình sẽ có thuật toán sau:


Node *FindNode(Tree root, int x) { if (root) { if (root->data == x) // Tìm thấy return root; if (x < root->data) return FindNode(root->left, x); // Tìm cây con bên trái return FindNode(root->right, x); // Tìm cây con bên phải } return NULL; // Không tìm thấy }

Hủy nút trên cây nhị phân tìm kiếm

Để hủy một nút có khóa X trong cây nhị phân tìm kiếm, chúng ta cần giải quyết ba trường hợp sau:

  1. Nút X là nút lá, ta xóa đi mà không làm ảnh hưởng đến các nút khác. Ví dụ xóa nút 15 đi không ảnh hưởng gì đến các nút khác.
  2. Nút X có 1 cây con, chúng ta chỉ cần nối nút cha của X với nút con của X. Ví dụ xóa nút 13 đi, ta chỉ cần nối nút 18 và 15 lại, sau đó xóa nút 13 đi.
  3. Nút X có đầy đủ 2 cây con: vì X có đầy đủ 2 nút nên nếu ta xóa đi, ta sẽ bị mất toàn bộ cây con. Do đó chúng ta cần tìm phần tử thế mạng cho X mà vẫn đảm bảo được cây nhị phân tìm kiếm, sau đó mới xóa X đi.

Đối với hai trường hợp đầu thì dễ, tuy nhiên, với trường hợp thứ 3, chúng ta cần phải giải quyết vấn đề tìm phần tử thế mạng cho x, chúng ta sẽ có hai cách thực hiện như sau:

  1. Nút thế mạng là nút có khóa nhỏ nhất (trái nhất) của cây con bên phải x.
  2. Nút thế mạng là nút có khóa lớn nhất (phải nhất) của cây con bên trái x.

Lấy ví dụ cho các bạn dễ hiểu hơn, hình phía trên, xóa đi phần tử 18 theo cách 1, phần tử lớn nhất của cây con bên trái là 15, vậy thì thay 18 bằng 15 rồi xóa đi nút 15 cuối. Cách 2, phần tử nhỏ nhất của cây con bên phải là 23, vậy 18 sẽ thay bằng 23 và xóa nút 23 đó đi.

Đối với hai trường hợp đầu tiên khá đơn giản, nên mình sẽ lồng nó vào code luôn ở phần dưới, mình sẽ giải quyết cách tìm phần tử thế mạng ở trường hợp 3 trước và theo cả hai cách. Theo cách 1, mình sẽ làm như sau:

Trường hợp 1


// nút p là nút cần thay thế, tree là cây đang xét (cây bên phải) void FindAndReplace1(Tree &p, Tree &tree) { if (tree->left) // chưa phải nhỏ nhất (trái nhất) FindAndReplace1(p, tree->left); // tiếp tục tìm else // tree là nút trái nhất { p->data = tree->data; // copy data p = tree; // trỏ nút p vào nút tree sẽ làm thế mạng bị xóa tree = tree->right; // nút trái không còn tuy nhiên nút phải có thể còn nên ta phải nối chúng lại } }

Đối với trường hợp này, các bạn phải gọi hàm FindAndReplace1(p, root->right) trong hàm DeleteNode ở phía trên. Trường hợp thứ 2 thì ngược lại.

Trường hợp 2


// nút p là nút cần thay thế, tree là cây đang xét (cây bên trái) void FindAndReplace2(Tree &p, Tree &tree) { if (tree->right) // chưa phải lớn nhất (phải nhất) FindAndReplace2(p, tree->right); // tiếp tục tìm else // tree là nút trái nhất { p->data = tree->data; // copy data p = tree; // trỏ nút p vào nút tree sẽ làm thế mạng bị xóa tree = tree->left; // nút phải không còn tuy nhiên nút trái có thể còn nên ta phải nối chúng lại } }

Và trong hàm DeleteNode, các bạn sẽ gọi hàm FindAndReplace(p, root->left). Bây giờ, tổng hợp lại, chúng ta đã có thể dể dàng xóa một nút khỏi cây nhị phân tìm kiếm, mình sẽ code như sau:


void DeleteNode(Tree &root, int x) { if (root) { if (x > root->data) DeleteNode(root->right, x); else if (x < root->data) DeleteNode(root->left, x); else // nút hiện tại (root) là nút cần xóa { Node *p = root; // lưu lại nút cần xóa tránh bị ghi đè if (!root->left) root = root->right; // trường hợp 1 else if (!root->right) root = root->left; // trường hợp 2 else FindAndReplace1(p, root->right); // cách 1 // FindAndReplace2(p, root->left); // cách 2 delete p; // xóa nút } } else { cout << "Not found!n"; // Không tìm thấy phần tử cần xóa } }

Đặt vấn đề

Input và output cho các thuật toán sử dụng cây tìm kiếm giống như đối với Tìm kiếm nhị phân. Mỗi phần tử từ một tập hợp để được lưu trữ trong cây tìm kiếm cần có một hoặc nhiều thuộc tính có thể được sử dụng như một khóa . Các phần tử cũng phải có các thuộc tính phân biệt chính nó với các phần tử khác trong tập hợp. Cây tìm kiếm sẽ được sử dụng lưu trữ các phần tử của tập .

Rò rỉ bộ nhớ là một vấn đề nghiêm trọng đối với các lập trình viên. Khi một chương trình chạy trong một thời gian dài, chẳng hạn như nhiều ứng dụng server được sử dụng trong các hệ thống ngày nay, rò rỉ bộ nhớ sẽ khiến chương trình vượt quá lượng bộ nhớ được cấp cho quy trình của nó và sau đó bị sập, thường dẫn đến những hậu quả tai hại.

Người ta có thể viết một chương trình để giám sát việc phân phối bộ nhớ và báo cáo về cấu hình bộ nhớ của chương trình để phát hiện sự xuất hiện của rò rỉ bộ nhớ. Một trình biên dịch bộ nhớ như vậy có thể được viết khá đơn giản bằng cách viết các hàm malloc() và free() ghi lại thông tin thích hợp trước khi cấp phát và giải phóng bộ nhớ. Chúng ta muốn ghi lại mọi cấp phát bộ nhớ và khi bộ nhớ đó được giải phóng, chúng ta phải xóa nó khỏi tập hợp cấp phát đang hoạt động.

Trong tình huống được mô tả, ta không biết trước về số lượng phần tử cần lưu trữ. Tìm kiếm dựa trên hàm băm sử dụng được, nhưng ta có thể chọn kích thước bảng băm quá nhỏ để sử dụng tài nguyên hiệu quả. Một chiến lược tìm kiếm thay thế là sử dụng cây tìm kiếm nhị phân. Cây tìm kiếm nhị phân hoạt động tốt với dữ liệu động, nơi thường xuyên thực hiện thao tác chèn và xóa.

Cây tìm kiếm nhị phân , là một tập hợp hữu hạn các nút được xác định bằng thuộc tính có thứ tự hoặc khóa. Tập hợp các nút có thể rỗng hoặc nó có thể chứa một nút gốc . Mỗi nút tham chiếu đến hai cây tìm kiếm nhị phân, và , tuân theo thuộc tính rằng nếu là khóa của nút , thì tất cả các khóa trong là và tất cả các khóa trong là . Hình dưới cho thấy một ví dụ nhỏ về cây nhị phân. Mỗi nút có một khóa là số nguyên xác định nút.

Bạn có thể thấy rằng việc tìm một khóa trong cây ở hình yêu cầu kiểm tra nhiều nhất ba nút, bắt đầu với nút gốc. Ta thấy cây hoàn toàn cân đối. Có nghĩa là, mỗi nút có bất kỳ nút con nào đều có đúng hai nút con. Một cây nhị phân cân bằng hoàn hảo có nút với và chiều cao là .

Cây có thể không phải lúc nào cũng cân đối (như hình dưới). Ở đây cây đóng vai trò như một list (danh sách).

[Cây Nhị Phân] - Chèn và duyệt cây nhị phân tìm kiếm BST.
[Cây Nhị Phân] – Chèn và duyệt cây nhị phân tìm kiếm BST.

Cây nhị phân

Cây nhị phân là một trường hợp đặc biệt của cấu trúc cây và nó cũng phổ biến nhất. Đúng như tên gọi của nó, cây nhị phân có bậc là 2 và mỗi nút trong cây nhị phân đều có bậc không quá 2.

Các khái niệm

Có một số khái niệm khác về cây nhị phân các bạn cần nắm như sau:

  • Cây nhị phân đúng: là cây nhị phân mà mỗi nút của nó đều có bậc 2. Ví dụ như hình trên, hoặc hình trên bỏ đi nút H và I cũng là cây nhị phân đúng.
  • Cây nhị phân đầy đủ là cây nhị phân có mức của các nút lá đều bằng nhau. Ví dụ hình trên, tất cả các nút lá đều có mức 3.
  • Cây nhị phân tìm kiếm (sẽ tìm hiểu bên dưới)
  • Cây nhị phân cân bằng: số phần tử của cây con bên trái chênh lệch không quá 1 so với cây con bên phải.

Định nghĩa cấu trúc nút

Nhìn vào hình, ta có thể dễ dàng phân tích được rằng, mỗi nút trong cây nhị phân sẽ gồm 3 thành phần như sau:

  • Thành phần dữ liệu: có thể là bất kỳ kiểu dữ liệu nào.
  • Thành phần liên kết trái: lưu trữ địa chỉ của nút gốc của cây con bên trái. Kiểu dữ liệu là con trỏ trỏ vào node.
  • Thành phân liên kết phải: lưu trữ địa chỉ của nút gốc của cây con bên phải. Kiểu dữ liệu là con trỏ trỏ vào node.

Chúng ta sẽ có struct lưu trữ một node như sau – ở đây để đơn giản mình sử dụng kiểu dữ liệu int cho thành phần dữ liệu của node:


struct Node { int data; Node *left; Node *right; };

Khi tạo một nút node mới, chúng ta cần phải gán lại các thành phần của node để nó không nhận giá trị rác, tránh lỗi không mong muốn. Chúng ta sẽ tạo một biến động cho node và trả về địa chỉ của node đó, mình sẽ có đoạn code tạo node như sau:


Node *CreateNode(int init) { Node *p = new Node; p->data = init; p->left = NULL; p->right = NULL; return p; }

Định nghĩa cấu trúc cây

Để quản lý một cái cây, bạn chỉ cần quản lý được nút gốc, bạn có thể đi được đến các nhánh và lá của nó từ đó. Trên thực tế bạn không cần phải định nghĩa một kiểu dữ liệu nào để quản lý cả, tuy nhiên, để cho code rõ ràng hơn, bạn nên định nghĩa một kiểu dữ liệu cây nữa.


typedef Node* Tree;

Lúc này, khi tạo một cây, bản chất là nó sẽ tạo cho bạn một con trỏ có thể trỏ vào một node.


Tree myTree;

Vì nó là con trỏ nên các bạn gán nó bằng NULL để tránh lỗi, nhưng để mọi thứ rõ ràng hơn, mình sẽ dùng hàm tạo cây đơn giản gán nó bằng NULL.


void CreateTree(Tree &root) { root = NULL; } // Khi tạo cây CreateTree(myTree);

Duyệt cây nhị phân

Có 3 cách duyệt cây nhị phân:

  • Duyệt tiền tự (NLR): duyệt nút gốc, duyệt tiền tự cây con trái, duyệt tiền tự cây con phải.
  • Duyệt trung tự (LNR): duyệt trung tự cây con trái, duyệt nút gốc, duyệt trung tự cây con phải.
  • Duyệt hậu tự (LRN): duyệt hậu tự cây con trái, duyệt hậu tự cây con phải, duyệt nút gốc.

Để bạn hiểu rõ hơn ba cách duyệt này, chúng ta sẽ sử dụng lại hình ảnh cây nhị phân trên:

  • Duyệt tiền tự: A B D H I E K L C F M N G O P
  • Duyệt trung tự: H D I B K E L A M F N C O G P
  • Duyệt hậu tự: H I D K L E B M N F O P G C A

Ứng với từng cách duyệt đó, chúng ta sẽ có các hàm duyệt cây như sau:

Duyệt tiền tự


void NLR(Tree root) { if (root) { // Xử lý nút gốc (root) NLR(root->left); NLR(root->right); } }

Duyệt trung tự


void LNR(Tree root) { if (root) { LNR(root->left); // Xử lý nút gốc (root) LNR(root->right); } }

Duyệt hậu tự


void LRN(Tree root) { if (root) { LRN(root->left); LRN(root->right); // Xử lý nút gốc (root) } }

Hủy cây nhị phân

Để hủy đi cây nhị phân, các bạn cũng thực hiện duyệt và xóa đi các nút của cây, tuy nhiên, các bạn dễ thấy rằng, nếu ta duyệt tiền tự và trung tự, khi xóa nút nhánh thì sẽ bị mất luôn địa chỉ của các nút con. Do đó, việc hủy cây nhị phân bắt buộc phải duyệt hậu tự. Hay nói cách khác, bạn phải xóa các phần tử là nút lá xóa dần lên đến nút gốc.

Chúng ta sẽ có hàm hủy như sau:


void DestroyTree(Tree &root) { if (root) { DestroyTree(root->left); DestroyTree(root->right); delete root; } }

Như vậy là chúng ta đã tìm hiểu về cách tạo một nút, kết nối chúng lại thành một cây nhị phân, duyệt cây và hủy cây. Tiếp theo chúng ta sẽ tìm hiểu về cây nhị phân đặc biệt khác là cây nhị phân tìm kiếm.

Tham khảo thêm các vị trí tuyển lập trình viên C++ mới nhất.

Source code


struct Node { int data; Node *left; Node *right; }; typedef Node *Tree; Node *CreateNode(int init) { Node *p = new Node; p->data = init; p->left = NULL; p->right = NULL; return p; } void CreateTree(Tree &root) { root = NULL; } void DestroyTree(Tree &root) { if (root) { DestroyTree(root->left); DestroyTree(root->right); delete root; } } void AddNode(Tree &root, Node *node) { if (root) { if (root->data == node->data) return; if (node->data < root->data) AddNode(root->left, node); else AddNode(root->right, node); } else { root = node; } } Node *FindNode(Tree root, int x) { if (root) { if (root->data == x) return root; if (x < root->data) return FindNode(root->left, x); return FindNode(root->right, x); } return NULL; } void PrintTree(Tree root)// print tree using LNR { if (root) { PrintTree(root->left); cout << root->data << ' '; PrintTree(root->right); } } void NLR(Tree root) { if (root) { // Xử lý nút gốc (root) NLR(root->left); NLR(root->right); } } void LNR(Tree root) { if (root) { LNR(root->left); // Xử lý nút gốc (root) LNR(root->right); } } void LRN(Tree root) { if (root) { LRN(root->left); LRN(root->right); // Xử lý nút gốc (root) } } void FindAndReplace1(Tree &p, Tree &tree) { if (tree->left) FindAndReplace1(p, tree->left); else { p->data = tree->data; p = tree; tree = tree->right; } } void FindAndReplace2(Tree &p, Tree &tree) { if (tree->right) FindAndReplace2(p, tree->right); else { p->data = tree->data; p = tree; tree = tree->left; } } void DeleteNode(Tree &root, int x) { if (root) { if (x > root->data) DeleteNode(root->right, x); else if (x < root->data) DeleteNode(root->left, x); else { Node *p = root; if (!root->left) root = root->right; else if (!root->right) root = root->left; else FindAndReplace1(p, root->right); // FindAndReplace2(p, root->left); delete p; } } else { cout << "Not found!n"; } }

Binary Search Tree (Cây tìm kiếm nhị phân) là gì?

  • Vai trò của kiến trúc bảo mật thích ứng trong quản lý ninh mạng
  • Ưu điểm khi kết hợp trí tuệ nhân tạo AI và RPA – Robotic Process Automation
  • Cấu trúc dữ liệu là gì? Những điều cần biết về cấu trúc dữ liệu
  • Làm thế nào để học lập trình? Mẹo hay cho người mới bắt đầu
  • Trung tâm Công nghệ chuyên sâu xSeries ra mắt phiên bản mới môn Toán rời rạc

Binary Search Tree là một trong những cấu trúc dữ liệu khác nhau giúp tổ chức và sắp xếp dữ liệu. Nó rất linh hoạt và là một cách hiệu quả để lưu trữ dữ liệu theo hệ thống phân cấp.

Trong bài viết này, chúng ta sẽ xem xét kỹ hơn cách thức hoạt động — cũng như các thuộc tính và ứng dụng của Binary Search Tree.

Hướng dẫn cài đặt cây nhị phân - Cây nhị phân tìm kiếm bằng ngôn ngữ C
Hướng dẫn cài đặt cây nhị phân – Cây nhị phân tìm kiếm bằng ngôn ngữ C

Keywords searched by users: cây nhị phân tìm kiếm

Cây Tìm Kiếm Nhị Phân – Binary Search Tree – Luyện Code
Cây Tìm Kiếm Nhị Phân – Binary Search Tree – Luyện Code
Cấu Trúc Dữ Liệu Và Giải Thuật - Cây Nhị Phân Tìm Kiếm
Cấu Trúc Dữ Liệu Và Giải Thuật – Cây Nhị Phân Tìm Kiếm
Cây Nhị Phân Và Cây Nhị Phân Tìm Kiếm
Cây Nhị Phân Và Cây Nhị Phân Tìm Kiếm
Ctdl] Binary Search Tree - Cây Nhị Phân Tìm Kiếm | Xóa Node Khỏi Bst » Cafedev.Vn
Ctdl] Binary Search Tree – Cây Nhị Phân Tìm Kiếm | Xóa Node Khỏi Bst » Cafedev.Vn
Cây Nhị Phân Và Cây Nhị Phân Tìm Kiếm
Cây Nhị Phân Và Cây Nhị Phân Tìm Kiếm
Cấu Trúc Dữ Liệu
Cấu Trúc Dữ Liệu
Cây Nhị Phân Trong C++ | Topdev
Cây Nhị Phân Trong C++ | Topdev
Giải Thuật Lập Trình · Cây Nhị Phân Cân Bằng — Balanced Binary Search Tree
Giải Thuật Lập Trình · Cây Nhị Phân Cân Bằng — Balanced Binary Search Tree
Cây Nhị Phân Và Cây Nhị Phân Tìm Kiếm
Cây Nhị Phân Và Cây Nhị Phân Tìm Kiếm
Cây Nhị Phân Tìm Kiếm] Bài 4. Duyệt Lnr Cây Nhị Phân(Cây Nhị Phân Tìm Kiếm) - Youtube
Cây Nhị Phân Tìm Kiếm] Bài 4. Duyệt Lnr Cây Nhị Phân(Cây Nhị Phân Tìm Kiếm) – Youtube
Algorithm – Cập Nhật Thuật Toán Vẽ Cây Nhị Phân | Yinyang'S Programing Blog
Algorithm – Cập Nhật Thuật Toán Vẽ Cây Nhị Phân | Yinyang’S Programing Blog
Thuật Toán Tìm Kiếm Nhị Phân - Binary Search Tree (Bts) - Vntalking
Thuật Toán Tìm Kiếm Nhị Phân – Binary Search Tree (Bts) – Vntalking
Binary Search Tree (Cây Tìm Kiếm Nhị Phân) Là Gì? | Học Trực Tuyến Cntt, Học Lập Trình Từ Cơ Bản Đến Nâng Cao
Binary Search Tree (Cây Tìm Kiếm Nhị Phân) Là Gì? | Học Trực Tuyến Cntt, Học Lập Trình Từ Cơ Bản Đến Nâng Cao
Cây Nhị Phân – Binary Tree – Luyện Code
Cây Nhị Phân – Binary Tree – Luyện Code
Tìm Kiếm Nhị Phân – Wikipedia Tiếng Việt
Tìm Kiếm Nhị Phân – Wikipedia Tiếng Việt
Cây Nhị Phân Tìm Kiếm] Bài 14. Đọc - Ghi File Các Số Nguyên Trong Cây Nhị Phân Tìm Kiếm(Phần 1) - Youtube
Cây Nhị Phân Tìm Kiếm] Bài 14. Đọc – Ghi File Các Số Nguyên Trong Cây Nhị Phân Tìm Kiếm(Phần 1) – Youtube
Cấu Trúc Dữ Liệu Và Giải Thuật - Cây Nhị Phân Tìm Kiếm
Cấu Trúc Dữ Liệu Và Giải Thuật – Cây Nhị Phân Tìm Kiếm
Cây Nhị Phân Tìm Kiếm] Bài 2. Khai Báo-Khởi Tạo-Duyệt Nlr Cây Nhị Phân(Cây Nhị Phân Tìm Kiếm) - Youtube
Cây Nhị Phân Tìm Kiếm] Bài 2. Khai Báo-Khởi Tạo-Duyệt Nlr Cây Nhị Phân(Cây Nhị Phân Tìm Kiếm) – Youtube
Binary Search Tree (Cây Tìm Kiếm Nhị Phân) Là Gì? | Học Trực Tuyến Cntt, Học Lập Trình Từ Cơ Bản Đến Nâng Cao
Binary Search Tree (Cây Tìm Kiếm Nhị Phân) Là Gì? | Học Trực Tuyến Cntt, Học Lập Trình Từ Cơ Bản Đến Nâng Cao
Tìm Kiếm Node Trên Cây Nhị Phân Tìm Kiếm
Tìm Kiếm Node Trên Cây Nhị Phân Tìm Kiếm
Giải Thuật Tìm Kiếm Trên Cây Tìm Kiếm Nhị Phân - Youtube
Giải Thuật Tìm Kiếm Trên Cây Tìm Kiếm Nhị Phân – Youtube
Cây Tìm Kiếm Nhị Phân – Binary Search Tree – Luyện Code
Cây Tìm Kiếm Nhị Phân – Binary Search Tree – Luyện Code

See more here: kientrucannam.vn

Tags:

Leave a Reply

Your email address will not be published. Required fields are marked *