NỘI DUNG BÀI VIẾT
Giới thiệu Tree và Binary Tree
- Tree lưu trữ dữ liệu trên các node
- Các node có mối quan hệ cha-con, node trên cùng được gọi là node gốc (root node)
- Binary Tree (Cây nhị phân) là cây mà mỗi node có 0, 1 hoặc 2 cây con (subtree)
- 2 cây con được gọi lần lượt là left-subtree (cây con trái) và right-subtree (cây con phải)
Minh họa cây nhị phân
Các khái niệm
- Độ dài của đường đi (length of the path) là số lượng các cạnh
- Chiều sâu của node là độ dài của đường đi tính từ root node đến node đó
- Node anh em (sibling) là các node có cùng node cha
- Node không có node con thì gọi là node lá (leaf node)
- Chiều cao của cây là độ dài của đường đi từ node gốc đến node lá
Binary Search Tree (BST)
- Binary Tree (Cây nhị phân) là một cấu trúc phân tầng
- Bao gồm:
- Một nút gốc (root)
- Một cây con trái (left subtree)
- Một cây con phải (right subtree)
- Một nút có thể có 0, 1 hoặc 2 cây con
- Cây tìm kiếm nhị phân:
- Là cây nhị phân có trật tự
- Giá trị nút bên trái nhỏ hơn nút hiện tại
- Giá trị nút bên phải lớn hơn nút hiện tại
- BSTđược biểu diễn bằng một tập các node liên kết với nhau
- Mỗi node chứa dữ liệu và 2 liên kết: 1 liên kết sang node con bên trái và. 1 liên kết sang node con bên phải
Minh hoạ cấu trúc cây tìm kiếm nhị phân
Triển khai BST
class TreeNode<E> { protected E element; protected
TreeNode<E> left; protected TreeNode<E> right; public TreeNode(E e) { element = e; } }
TreeNode<Integer> root = new TreeNode<>(60); root.left = new TreeNode<>(55); root.right = new TreeNode<>(100);
Tìm kiếm trên BST
public boolean search(E element) { TreeNode<E> current = root; while (current != null) { if (element < current.element) { current = current.left; } else if (element > current.element) { current = current.right; } else return true; } return false; }
Thêm phần tử vào BST
Minh hoạ thao tác thêm phần tử vào BST
