Chuyển tới nội dung
Home » Binary Search Tree Là Gì | Liên Kết Ngoài[Sửa | Sửa Mã Nguồn]

Binary Search Tree Là Gì | Liên Kết Ngoài[Sửa | Sửa Mã Nguồn]

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

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).

6.2 Glossary(Bảng chú giải thuật ngữ)

  • Root của cây là node không có bố mẹ. Có thể có nhiều nhất một node gốc trong một cây (node A trong ví dụ trên).
  • Một edge(cạnh) đề cập đến liên kết từ cha đến con (tất cả các liên kết trong hình).
  • Một node không có node con được gọi là leaf node (E, J, K, H và I).
  • Những node con có cùng node cha được gọi là siblings(anh chị em ruột – B, C, D là siblings của A và E, F là anh chị em của B).
  • Một node p là ancestor(tổ tiên) của node q nếu tồn tại một đường đi từ gốc đến q và p xuất hiện trên đường đi. Node q được gọi là descendant(con cháu) của p. Ví dụ, A, C và G là tổ tiên của K.
  • Tập hợp tất cả các node ở một độ sâu nhất định được gọi là level của cây (B, C và D là cùng một mức). Nút Root ở mức không.
  • Độ sâu của node là độ dài của đường đi từ gốc đến node (độ sâu của G là 2, A – C – G).
  • Chiều cao của một node là độ dài của đường đi từ nút đó đến nút sâu nhất. Chiều cao của cây là chiều dài của đường đi từ root đến node sâu nhất trong cây. Một cây chỉ có một node (gốc) có chiều cao bằng không. Trong ví dụ trước, chiều cao của B là 2 (B – F – J).
  • Chiều cao của cây là chiều cao lớn nhất trong số tất cả các nút trong cây và chiều sâu của cây là chiều sâu lớn nhất trong số tất cả các nút trong cây. Đối với một cây nhất định, chiều sâu và chiều cao trả về cùng một giá trị. Nhưng đối với các node riêng lẻ, chúng ta có thể nhận được các kết quả khác nhau.
  • Kích thước của một node là số lượng nút con mà nó có bao gồm cả chính nó (kích thước của cây con C là 3).
  • Nếu mọi node trong cây chỉ có một node con (trừ các nút lá) thì ta gọi các cây như vậy là cây xiên(skew trees). Nếu mọi node chỉ có con trái thì chúng ta gọi chúng là cây xiên trái(left skew trees). Tương tự, nếu mọi node chỉ có con bên phải thì chúng ta gọi chúng là cây xiên bên phải(right skew trees).
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

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

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ấu trúc dữ liệu và thuật toán #18: Binary Search Tree | BST | DS&A
Cấu trúc dữ liệu và thuật toán #18: Binary Search Tree | BST | DS&A

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; }

6.1 What is a Tree?

Tree là một cấu trúc dữ liệu tương tự như một linked list nhưng thay vì mỗi node chỉ đơn giản chỉ đến node tiếp theo theo kiểu tuyến tính, ở tree mỗi node trỏ đến một số node khác. Tree là một ví dụ về cấu trúc dữ liệu phi tuyến. Cấu trúc cây là một cách thể hiện bản chất thứ bậc của cấu trúc dưới dạng đồ họa.

Trong tree ADT (Abstract Data Type), thứ tự của các phần tử không quan trọng. Nếu chúng ta cần thông tin đặt hàng, cấu trúc dữ liệu tuyến tính như danh sách liên kết, ngăn xếp, hàng đợi, v.v. có thể được sử dụng.

410 - Java - Binary Search Tree - Cây nhị phân - Chuẩn bị các classes + sườn bài
410 – Java – Binary Search Tree – Cây nhị phân – Chuẩn bị các classes + sườn bài

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?

Ứ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 đề.

Cấu trúc dữ liệu và giải thuật - Python - Cây nhị phân tìm kiếm - Binary Search Tree - BST - Phần 1
Cấu trúc dữ liệu và giải thuật – Python – Cây nhị phân tìm kiếm – Binary Search Tree – BST – Phần 1

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); } }

6.3 Binary Trees

Một cây được gọi là cây nhị phân(binary tree) nếu mỗi nút không có con nào, một con hoặc hai con. Cây rỗng cũng là một cây nhị phân hợp lệ. Chúng ta có thể hình dung cây nhị phân bao gồm một gốc và hai cây nhị phân rời rạc, được gọi là cây con trái và phải của gốc.

Types of Binary Trees

Strict Binary Tree: Cây nhị phân được gọi là cây nhị phân nghiêm ngặt(Strict Binary Tree) nếu mỗi nút có đúng hai nút con hoặc không có nút con nào.

Full Binary Tree: Cây nhị phân được gọi là cây nhị phân đầy đủ(Full Binary Tree) nếu mỗi nút có đúng hai nút con và tất cả các nút lá đều ở cùng một mức.

Complete Binary Tree: Trước khi xác định cây nhị phân hoàn chỉnh(Complete Binary Tree), chúng ta hãy giả sử rằng chiều cao của cây nhị phân là h. Trong cây nhị phân hoàn chỉnh, nếu chúng ta đánh số cho các nút bằng cách bắt đầu từ gốc (giả sử nút gốc có 1) thì chúng ta sẽ nhận được một chuỗi hoàn chỉnh từ 1 đến số nút trong cây.

Trong khi đi ngang, chúng ta cũng nên đánh số cho các con trỏ NULL. Cây nhị phân được gọi là cây nhị phân hoàn chỉnh nếu tất cả các nút lá ở độ cao h hoặc h – 1 và cũng không thiếu bất kỳ số nào trong dãy tuần tự.

Properties of Binary Trees

Đối với các tính chất sau, chúng ta hãy giả sử rằng chiều cao của cây là h. Ngoài ra, giả sử rằng nút gốc ở độ cao bằng không.

Từ sơ đồ dưới đây, chúng ta có thể suy ra các thuộc tính sau:

  • Số nút n trong cây nhị phân đầy đủ là . Vì có h mức, chúng ta cần cộng tất cả các nút ở mỗi cấp .
  • Số nút n trong một cây nhị phân hoàn chỉnh nằm trong khoảng từ (tối thiểu) đến (tối đa). Mình sẽ nói thêm chi tiết về cái này trong chương về Priority Queue.
  • Số lượng nút lá trong một cây nhị phân đầy đủ là .
  • Số liên kết NULL (con trỏ lãng phí) trong một cây nhị phân hoàn chỉnh có node là .

Structure of Binary Trees

Bây giờ chúng ta hãy xác định cấu trúc của cây nhị phân. Để đơn giản, giả sử rằng dữ liệu của các nút là số nguyên. Một cách để biểu diễn một node (chứa dữ liệu) là có hai liên kết trỏ đến nút con bên trái và bên phải cùng với các trường dữ liệu như được hiển thị bên dưới:


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

Lưu ý: Trong cây, luồng mặc định là từ cha đến con và không bắt buộc phải hiển thị các nhánh có hướng. Đối với phần này, chúng ta giả định rằng cả hai đại diện được hiển thị bên dưới đều giống nhau.

Operations on Binary Trees

Basic Operations

  • Thêm một phần tử vào cây
  • Xóa một phần tử khỏi cây
  • Tìm kiếm trong cây
  • Duyệt cây

Auxiliary(phụ trợ) Operations

  • Tìm kích thước của cây
  • Tìm chiều cao của cây
  • Tìm cấp có tổng tối đa
  • Tìm tổ tiên chung gần nhất (the least common ancestor – LCA) cho một cặp nút nhất định và nhiều nút khác.

Một số ứng dụng của Binary Trees

Sau đây là một số ứng dụng mà cây nhị phân đóng một vai trò quan trọng:

  • Cây biểu thức(Expression trees) được sử dụng trong trình biên dịch.
  • Cây mã hóa Huffman được sử dụng trong các thuật toán nén dữ liệu.
  • Cây tìm kiếm nhị phân (Binary Search Tree – BST), hỗ trợ tìm kiếm, chèn và xóa trên một tập hợp các mục trong (trung bình).
  • Priority Queue (PQ), hỗ trợ tìm kiếm và xóa tối thiểu (hoặc tối đa) trên một collection các mục theo thời gian logarit (trong trường hợp xấu nhất).

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

Bài 05. Thuật Toán Tìm Kiếm Nhị Phân (Binary Search) | Cấu Trúc Dữ Liệu Và Giải Thuật
Bài 05. Thuật Toán Tìm Kiếm Nhị Phân (Binary Search) | Cấu Trúc Dữ Liệu Và Giải Thuật

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 } }


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)).
Cấu trúc dữ liệu và thuật toán #19: Binary Search Tree code | DS&A
Cấu trúc dữ liệu và thuật toán #19: Binary Search Tree code | DS&A

Đị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.

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

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

Cây tìm kiếm nhị phân (viết tắt tiếng Anh: BST – Binary Search Tree) là một cấu trúc dữ liệu rất thuận lợi cho bài toán tìm kiếm. Mỗi cây tìm kiếm nhị phân đều có tính chất sau: Với mỗi nút , các nút ở cây con bên trái của đều có giá trị key nhỏ hơn : , còn các nút ở cây con bên phải của đều có key lớn hơn hoặc bằng : .

VN-Index khai xuân Giáp Thìn vượt 1.200 điểm | Điểm tin chứng khoán 15/2/2024
VN-Index khai xuân Giáp Thìn vượt 1.200 điểm | Điểm tin chứng khoán 15/2/2024

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/

Một cây tìm kiếm nhị phân (Binary Search Tree – viết tắt là BST) là một cây mà trong đó tất cả các nút đều có các đặc điểm sau:

Vì thế có thể nói rằng, một cây tìm kiếm nhị phân (BST) phân chia tất cả các cây con của nó thành hai phần: cây con bên trái và cây con bên phải và có thể được định nghĩa như sau:


left_subtree (keys) node (key) right_subtree (keys)

Cây tìm kiếm nhị phân (BST) là một tập hợp bao gồm các nút được sắp xếp theo cách để chúng có thể duy trì hoặc tuân theo các đặc điểm của cây tìm kiếm nhị phân. Mỗi một nút thì đều có một khóa và giá trị liên kết với nó. Trong khi tìm kiếm, khóa cần tìm được so sánh với các khóa trong cây tìm kiếm nhị phân (BST) và nếu tìm thấy, giá trị liên kết sẽ được thu nhận.

Ví dụ một cây tìm kiếm nhị phân (BST):

Từ hình ví dụ minh họa trên ta thấy rằng, khóa của nút gốc có giá trị 27 và tất cả khóa bên trái của cây con bên trái đều có giá trị nhỏ hơn 27 này và tất cả các khóa bên phải của cây con bên phải đều có giá trị lớn hơn 27.

Dưới đây là một số hoạt động cơ bản có thể được thực hiện trên cây tìm kiếm nhị phân:

Một nút có một vài dữ liệu, tham chiếu tới các nút con bên trái và nút con bên phải của nó.


struct node { int data; struct node *leftChild; struct node *rightChild; };

Mỗi khi một phần tử được tìm kiếm: bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn giá trị khóa (key), thì sẽ tìm phần tử ở cây con bên trái; nếu lớn hơn thì sẽ tìm phần tử ở cây con bên phải. Dưới đây là giải thuật cho mỗi nút:


struct node* search(int data){ struct node *current = root; printf("Truy cap cac phan tu: "); while(current->data != data){ if(current != NULL) { printf("%d ",current->data); //tới cây con bên trái if(current->data > data){ current = current->leftChild; }//else tới cây con bên phải else { current = current->rightChild; } //không tìm thấy if(current == NULL){ return NULL; } } } return current; }

Mỗi khi một phần tử được chèn: đầu tiên chúng ta cần xác định vị trí chính xác của phần tử này. Bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn giá trị khóa (key), thì tìm kiếm vị trí còn trống ở cây con bên trái và chèn dữ liệu vào đó; nếu dữ liệu là nhỏ hơn thì tìm kiếm vị trí còn sống ở cây con bên phải và chèn dữ liệu vào đó.


void insert(int data){ struct node *tempNode = (struct node*) malloc(sizeof(struct node)); struct node *current; struct node *parent; tempNode->data = data; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //Nếu cây là trống if(root == NULL){ root = tempNode; }else { current = root; parent = NULL; while(1){ parent = current; //tới cây con bên trái if(data < parent->data){ current = current->leftChild; //chèn dữ liệu vào cây con bên trái if(current == NULL){ parent->leftChild = tempNode; return; } }//tới cây con bên phải else{ current = current->rightChild; //chèn dữ liệu vào cây con bên phải if(current == NULL){ parent->rightChild = tempNode; return; } } } } }

Viết câu trả lời

Các bạn đã chán với thuật toán chưa? Học thuật toán hay mà ^^. Nối tiếp series thuật toán chuyên sâu này, chúng ta sẽ tiếp tục thảo luận về một thuật toán vô cùng phổ biến, nghe tên là bạn thấy quen liền. Đó là thuật toán tìm kiếm nhị phân hay Binary Search Tree.

Chúng ta sẽ triển khai các chức năng của thuật toán để tìm kiếm, chèn và xóa các giá trị từ một cây nhị phân. Vẫn là hai phương pháp để bạn tiếp cận và thực hiện thuật toán là: sử dụng vòng lặp và đệ quy.

Nội dung chính của bài viết

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).
5nm, 7nm, 14nm, 10nm: mấy con số này có nghĩa là gì | Giải thích tiến trình CPU
5nm, 7nm, 14nm, 10nm: mấy con số này có nghĩa là gì | Giải thích tiến trình CPU

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

Chương 6: TREES -Tree là gì? Lý thuyết về Binary Tree.

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Ổ PHIẾU LÌ XÌ CHO NĐT TRONG NĂM GIÁP THÌN
CỔ PHIẾU LÌ XÌ CHO NĐT TRONG NĂM GIÁP THÌN

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.

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.

KINH NGHIỆM NHẬN DIỆN CỔ PHIẾU VÀO SÓNG TĂNG
KINH NGHIỆM NHẬN DIỆN CỔ PHIẾU VÀO SÓNG TĂNG

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.

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.

EASY-HOW-TO Binary Search Tree (BST) Tutorial (Manual)
EASY-HOW-TO Binary Search Tree (BST) Tutorial (Manual)

Binary Search Tree (BTS)

Một Binary Search Tree có thuộc tính sau:

  • Tất cả các node phải sao cho node con bên trái luôn nhỏ hơn node cha.
  • Node con bên phải luôn lớn hơn node cha.

Hình dưới đây là một minh họa cho một cây nhị phân, khi mà dữ liệu được tổ chức giống như một cây.

Trong các phần sau, chúng ta sẽ xem cách tìm kiếm, chèn và xóa trong BTS bằng cả hai phương pháp: sử dụng vòng lặp và đệ quy.

🔥 Đọc thêm về thuật toán:

  • Thuật toán Quick Sort – Java Example
  • 5 thuật toán mà mọi lập trình viên nên biết
  • Bài toán tháp Hà Nội – Thuật toán và cách giải

Trước tiên, hãy tạo cấu trúc dữ liệu Binary Search Tree:

public class BinaryTree { public TreeNode root; public static class TreeNode { public TreeNode left; public TreeNode right; public Object data; public TreeNode(Object data) { this.data = data; left = right = null; } } }

Tìm kiếm đệ quy BST

Đoạn code dưới đây sẽ thực thi việc tìm kiếm một giá trị trong tree theo phương pháp đệ quy.

public class SearchInsertRemoveFromTree { public static void main(String[] args) { /** * Our Example Binary Search Tree * 10 * 5 20 * 4 8 15 25 */ BinaryTree tree = new BinaryTree(); tree.root = new TreeNode(10); tree.root.left = new TreeNode(5); tree.root.right = new TreeNode(20); tree.root.left.left = new TreeNode(4); tree.root.left.right = new TreeNode(8); tree.root.right.left = new TreeNode(15); tree.root.right.right = new TreeNode(25); System.out.println(“Search Value 2 is in tree? ” + searchRecursively(tree.root, 2)); System.out.println(“Search Value 10 in tree? ” + searchRecursively(tree.root, 10)); } public static boolean searchRecursively(TreeNode root, int value) { if (root == null) return false; if ((int) root.data == value) return true; if (value < (int) root.data) return searchRecursively(root.left, value); else if (value > (int) root.data) return searchRecursively(root.right, value); return false; } }

Kết quả thu được:

Tìm kiếm nhị phân BST sử dụng vòng lặp

Vẫn với yêu cầu tìm kiếm tương tự như phần trên, nhưng lần này chúng ta sử dụng phương pháp dùng vòng lặp.

Với phương pháp dùng vòng lặp, nó có ưu điểm là dễ debug hơn nhiều so với đệ quy.

public static boolean searchIteratively(TreeNode root, int value) { while (root != null) { if ((int) root.data == value) return true; if (value < (int) root.data) root = root.left; else root = root.right; } return false; }

Chèn thêm một giá trị vào cây nhị phân bằng đệ quy

public static TreeNode insertionRecursive(TreeNode root, int value) { if (root == null) return new TreeNode(value); if (value < (int) root.data) { root.left = insertionRecursive(root.left, value); } else if (value > (int) root.data) { root.right = insertionRecursive(root.right, value); } return root; } public static void printInorderTraversal(TreeNode root) { if (root != null) { printInorderTraversal(root.left); System.out.print(root.data + ” “); printInorderTraversal(root.right); } }

Giả sử chúng ta gọi hàm trên trong

main()

, bạn làm như sau:

tree.root = insertionRecursive(tree.root, 24); tree.root = insertionRecursive(tree.root, 2); printInorderTraversal(tree.root);

Cây được in dưới dạng inorder traversal

Chèn thêm một giá trị vào cây nhị phân bằng vòng lặp

Để làm được điều này trong cây BST, chúng ta sẽ cần duyệt qua cây bằng cách sử dụng hai con trỏ.

public static TreeNode insertionIterative(TreeNode root, int value) { TreeNode current, parent; TreeNode tempNode = new TreeNode(value); if (root == null) { root = tempNode; return root; } else { current = root; } while (true) { parent = current; if (value < (int) current.data) { current = current.left; if (current == null) { parent.left = tempNode; return root; } } else if (value > (int) current.data) { current = current.right; if (current == null) { parent.right = tempNode; return root; } } } }

Xóa một phần tử trong cây nhị phân bằng cách đệ quy

Việc xóa phần tử khỏi cây nhị phân phức tạp hơn so với tìm kiếm và chèn một chút. Vì chúng ta phải đảm bảo rằng hai thuộc tính của cây nhị phân vẫn được bảo toàn.

Để xóa một phần tử, trước tiên chúng ta cần tìm kiếm và xác định được nó đã. Sau đó, chúng ta cần xác định xem phần tử đó có phần tử con hay không!

  • Nếu không có con – Chỉ cần xóa.
  • Nếu có một con – Sao chép con đó vào node.
  • Nếu có hai con – Xác định phần tử cao nhất tiếp theo (con kế nhiệm inorder) trong cây con bên phải. Thay thế node bị xóa bằng node kế nhiệm nhỏ hơn. Xóa bản sao kế nhiệm inorder.

Có thể thu được giá trị kế nhiệm inorder bằng cách tìm giá trị nhỏ nhất trong con bên phải của node.

Chương trình java sau đây xóa các phần tử khỏi BST:

public static TreeNode deleteRecursively(TreeNode root, int value) { if (root == null) return root; if (value < (int) root.data) { root.left = deleteRecursively(root.left, value); } else if (value > (int) root.data) { root.right = deleteRecursively(root.right, value); } else { if (root.left == null) { return root.right; } else if (root.right == null) return root.left; root.data = inOrderSuccessor(root.right); root.right = deleteRecursively(root.right, (int) root.data); } return root; } public static int inOrderSuccessor(TreeNode root) { int minimum = (int) root.data; while (root.left != null) { minimum = (int) root.left.data; root = root.left; } return minimum; }

Giả sử chúng ta gọi hàm trên trong

main()

, bạn làm như sau:

tree.root = deleteRecursively(tree.root, 4); tree.root = deleteRecursively(tree.root, 20); printInorderTraversal(tree.root);

Đầu ra là:2 5 8 10 15 24 25

Hãy làm tương tự lặp đi lặp lại.

Xóa một phần tử trong cây nhị phân bằng cách sử dụng vòng lặp

public static TreeNode deleteNodeIteratively(TreeNode root, int value) { TreeNode parent = null, current = root; boolean hasLeft = false; if (root == null) return root; while (current != null) { if ((int) current.data == value) { break; } parent = current; if (value < (int) current.data) { hasLeft = true; current = current.left; } else { hasLeft = false; current = current.right; } } if (parent == null) { return deleteNodeIteratively(current); } if (hasLeft) { parent.left = deleteNodeIteratively(current); } else { parent.right = deleteNodeIteratively(current); } return root; } private static TreeNode deleteNodeIteratively(TreeNode node) { if (node != null) { if (node.left == null && node.right == null) { return null; } if (node.left != null && node.right != null) { TreeNode inOrderSuccessor = deleteInOrderSuccessorDuplicate(node); node.data = inOrderSuccessor.data; } else if (node.left != null) { node = node.left; } else { node = node.right; } } return node; } private static TreeNode deleteInOrderSuccessorDuplicate(TreeNode node) { TreeNode parent = node; node = node.right; boolean rightChild = node.left == null; while (node.left != null) { parent = node; node = node.left; } if (rightChild) { parent.right = node.right; } else { parent.left = node.right; } node.right = null; return node; }

Độ phức tạp của thuật toán BST là 0(h). Trong đó h là độ cao của cây.

Bài viết của mình đến đây là hết rồi. Mình hi vọng vẫn cảm thấy thích thú với thuật toán ^^

Nguồn tham khảo:

  • https://en.wikipedia.org/wiki/Binary_search_tree
  • https://www.cs.usfca.edu/~galles/visualization/BST.html
  • https://www.journaldev.com/23086/binary-search-tree-bst-search-insert-remove

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.

Keywords searched by users: binary search tree là gì

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
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 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
Ctdl] Binary Tree - Cây Nhị Phân | Các Loại Binary Trees » Cafedev.Vn
Ctdl] Binary Tree – Cây Nhị Phân | Các Loại Binary Trees » Cafedev.Vn
Chương 6: Trees - 1. Tree Là Gì? Lý Thuyết Về Binary Tree.
Chương 6: Trees – 1. Tree Là Gì? Lý Thuyết Về Binary Tree.
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
Chương 6: Trees - 7.Cây Tìm Kiếm Nhị Phân(Binary Search Trees - Bsts)
Chương 6: Trees – 7.Cây Tìm Kiếm Nhị Phân(Binary Search Trees – Bsts)
Cây Tìm Kiếm Nhị Phân – Wikipedia Tiếng Việt
Cây Tìm Kiếm Nhị Phân – Wikipedia Tiếng Việt
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
Binary Trees - W3Seo Cây Nhị Phân Là Gì? Tìm Hiểu Về Cây Nhị Phân
Binary Trees – W3Seo Cây Nhị Phân Là Gì? Tìm Hiểu Về Cây Nhị Phân
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ây Avl Trong Cấu Trúc Dữ Liệu Và Giải Thuật
Cây Avl Trong Cấu Trúc Dữ Liệu Và Giải Thuật
Binary Trees - W3Seo Cây Nhị Phân Là Gì? Tìm Hiểu Về Cây Nhị Phân
Binary Trees – W3Seo Cây Nhị Phân Là Gì? Tìm Hiểu Về Cây Nhị Phân
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
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
Chương 6: Trees - 7.Cây Tìm Kiếm Nhị Phân(Binary Search Trees - Bsts)
Chương 6: Trees – 7.Cây Tìm Kiếm Nhị Phân(Binary Search Trees – Bsts)
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
Giải Thuật Lập Trình · Binary Tree
Giải Thuật Lập Trình · Binary Tree
Algorithm – Cài Đặt Binary Search Tree Bằng C# | Yinyang'S Programing Blog
Algorithm – Cài Đặt Binary Search Tree Bằng C# | Yinyang’S Programing Blog
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
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
8 Cấu Trúc Dữ Liệu Siêu Cơ Bản Mà Dev Nào Cũng Nên Biết – Phần 3: Hashtable  Và Set, Graph Và Tree | Từ Coder Đến Developer – Tôi Đi Code Dạo
8 Cấu Trúc Dữ Liệu Siêu Cơ Bản Mà Dev Nào Cũng Nên Biết – Phần 3: Hashtable Và Set, Graph Và Tree | Từ Coder Đến Developer – Tôi Đi Code Dạo
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
Chương 6: Trees - 1. Tree Là Gì? Lý Thuyết Về Binary Tree.
Chương 6: Trees – 1. Tree Là Gì? Lý Thuyết Về Binary Tree.
Duyệt Cây Trong Cấu Trúc Dữ Liệu Và Giải Thuật
Duyệt Cây Trong Cấu Trúc Dữ Liệu Và Giải Thuật
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
Chương 6: Trees - 1. Tree Là Gì? Lý Thuyết Về Binary Tree.
Chương 6: Trees – 1. Tree Là Gì? Lý Thuyết Về Binary Tree.
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
411 - Java - Binary Search Tree - Cây Nhị Phân - Insert (Thêm) Node + In Dữ  Liệu - Youtube
411 – Java – Binary Search Tree – Cây Nhị Phân – Insert (Thêm) Node + In Dữ Liệu – Youtube
Binary Trees - W3Seo Cây Nhị Phân Là Gì? Tìm Hiểu Về Cây Nhị Phân
Binary Trees – W3Seo Cây Nhị Phân Là Gì? Tìm Hiểu Về Cây Nhị Phân
411 - Java - Binary Search Tree - Cây Nhị Phân - Insert (Thêm) Node + In Dữ  Liệu - Youtube
411 – Java – Binary Search Tree – Cây Nhị Phân – Insert (Thêm) Node + In Dữ Liệu – Youtube
Algorithm – Cài Đặt Binary Search Tree Bằng C# | Yinyang'S Programing Blog
Algorithm – Cài Đặt Binary Search Tree Bằng C# | Yinyang’S Programing Blog
Binary Search Trees - W3Seo Tìm Hiểu Về Cầy Bst, Cây Nhị Phân Tìm Kiếm
Binary Search Trees – W3Seo Tìm Hiểu Về Cầy Bst, Cây Nhị Phân Tìm Kiếm

See more here: kientrucannam.vn

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *