Giải thích chi tiết về tree structure (binary tree, AVL, B/B+ tree)

Tree là một data structure giống cây trong đời sống, nhưng bị đảo ngược. Mọi tree không rỗng chỉ có một root node.

Một tree có các đặc điểm sau:

1. Hai node bất kỳ trong một tree được nối với nhau bằng đúng một path.
2. Nếu một tree có n node thì chắc chắn có đúng n-1 edge.
3. Một tree không chứa cycle.

Hình dưới đây là một tree, đồng thời là một binary tree.

Như hình trên, hãy giải thích một số khái niệm thường dùng trong tree:

• Node: Mỗi phần tử trong tree đều có thể gọi chung là node.
• Root node: Node ở tầng cao nhất, hay node không có parent node. Trong hình trên, node A là root node.
• Parent node: Nếu một node có child node thì node đó được gọi là parent node của child node. Trong hình trên, node B là parent node của node D và node E.
• Child node: Root node của subtree do một node chứa được gọi là child node của node đó. Trong hình trên, node D và node E là child node của node B.
• Sibling node: Các node có cùng parent node được gọi là sibling node. Trong hình trên, parent node chung của node D và node E là node B, nên D và E là sibling node.
• Leaf node: Node không có child node. Trong hình trên, D, F, H, I đều là leaf node.
• Height của node: Số edge trong path dài nhất từ node đó đến leaf node.
• Depth của node: Số edge trong path từ root node đến node đó.
• Level của node: depth của node + 1.
• Height của tree: height của root node.

Về định nghĩa depth và height của tree, bạn có thể xem câu hỏi này trên Stack Overflow: What is the difference between tree depth and height?.

Phân loại binary tree

Binary tree là một tree structure mà mỗi node có nhiều nhất hai branch (tức không có node nào có degree lớn hơn 2).

Các branch của binary tree thường được gọi là “left subtree” hoặc “right subtree”. Ngoài ra, các branch của binary tree có thứ tự trái phải và không thể tùy ý đảo ngược.

Level thứ i của binary tree có nhiều nhất 2^(i-1) node. Theo định nghĩa “depth của root node bằng 0” trong bài viết này, binary tree có depth bằng k có nhiều nhất 2^(k+1)-1 node (trường hợp là full binary tree), và ít nhất k+1 node (trường hợp suy biến thành một chain). Về định nghĩa depth của node, các tài liệu trong nước có những quy ước khác nhau; bài viết này sử dụng định nghĩa depth của node của Wikipedia.

Full binary tree

Nếu số node ở mỗi level của một binary tree đều đạt mức tối đa thì binary tree đó là full binary tree. Nói cách khác, nếu một binary tree có K level và tổng số node là 2^k -1 thì nó là full binary tree. Hình dưới đây minh họa điều đó:

Complete binary tree

Nếu tất cả level ngoại trừ level cuối đều đầy, đồng thời level cuối đầy hoặc chỉ thiếu một số node liên tiếp ở bên phải, thì binary tree đó là complete binary tree.

Bạn có thể hình dung một tree được mở rộng bắt đầu từ root node: chỉ sau khi mở rộng xong left child node mới bắt đầu mở rộng right child node; chỉ sau khi mở rộng xong một level mới tiếp tục mở rộng level tiếp theo. Hình dưới đây minh họa điều đó:

Complete binary tree có một tính chất rất hữu ích: số thứ tự của parent node và child node có quan hệ tương ứng.

Có thể bạn đã nhận ra rằng khi giá trị của root node là 1, nếu số thứ tự của parent node là i thì số thứ tự của left child node là 2i, còn số thứ tự của right child node là 2i+1. Tính chất này giúp complete binary tree tiết kiệm đáng kể không gian khi lưu bằng array, đồng thời dùng số thứ tự để tìm parent node và child node. Phần lưu trữ binary tree sẽ giới thiệu chi tiết hơn ở phía sau.

AVL tree (height-balanced binary search tree)

AVL tree là một binary search tree cân bằng về height và có các tính chất sau:

1. Có thể là một empty tree.
2. Nếu không rỗng, giá trị tuyệt đối của hiệu height giữa hai subtree trái và phải không vượt quá 1, đồng thời hai subtree trái và phải cũng đều là AVL tree.

Red-black tree, scapegoat tree, weight-balanced tree và các tree khác cũng được dùng để tránh binary search tree bị suy biến nghiêm trọng, nhưng điều kiện balance của chúng không giống điều kiện “chênh lệch height giữa left subtree và right subtree không vượt quá 1” của AVL tree. Splay tree đạt được bảo đảm về amortized complexity thông qua việc điều chỉnh sau khi truy cập.

Trước khi giới thiệu balanced binary tree, hãy xem một tree:

Bạn gọi thứ này là tree à???

Đúng vậy, thứ này thực sự được gọi là tree, chỉ là tree này đã suy biến thành một linked list, và nó được gọi là oblique tree.

Nếu vậy thì tại sao tôi không dùng linked list luôn?

Đúng là như vậy.

Bản thân binary tree thông thường không bảo đảm việc search nhanh hơn linked list. Chỉ khi tận dụng tính có thứ tự của binary search tree hoặc các quan hệ index khác, tree structure mới có thể giúp search và update data hiệu quả hơn; binary search tree chưa được balance trong trường hợp xấu nhất vẫn suy biến thành O(n).

Tuy nhiên, nếu binary search tree suy biến thành linked list thì lợi thế search do structure có thứ tự mang lại khó thể hiện, hiệu năng cũng giảm mạnh. AVL tree sử dụng điều kiện height balance chặt chẽ hơn để tránh tình trạng này: chênh lệch height giữa left subtree và right subtree của mỗi node nhiều nhất là 1, như hình dưới đây:

Lưu trữ binary tree

Lưu trữ binary tree chủ yếu được chia thành linked storage và sequential storage:

Linked storage

Tương tự linked list, linked storage của binary tree dùng pointer để nối các node lại với nhau và không cần vùng bộ nhớ liên tục.

Mỗi node gồm ba thuộc tính:

• data. data không nhất thiết là một giá trị đơn; tùy trường hợp, nó có thể gồm nhiều data thuộc các type khác nhau.
• Pointer của left node là left.
• Pointer của right node là right.

Nhưng JAVA không có pointer mà!

Vậy thì dùng reference đến object là được (đừng hỏi tôi tìm object ở đâu).

Sequential storage

Sequential storage là lưu trữ bằng array. Mỗi vị trí trong array chỉ lưu data của node, không lưu pointer của left child node và right child node; index của child node được xác định thông qua chỉ số của array. Số thứ tự của root node là 1. Với mỗi node Node, giả sử node được lưu tại vị trí có array index là i thì left child node được lưu tại vị trí 2i, còn right child node được lưu tại vị trí có array index là 2i+1.

Sequential storage bằng array của một complete binary tree được minh họa như hình dưới đây:

Bạn có thể thử điền array dùng để lưu binary tree dưới đây, rồi so sánh sự khác nhau với sequential storage của complete binary tree:

Có thể thấy rằng nếu binary tree cần lưu không phải complete binary tree thì trong array sẽ xuất hiện các khoảng trống, khiến hiệu suất sử dụng memory giảm.

Traversal binary tree

Preorder traversal

Preorder traversal của binary tree là output root node trước, sau đó thực hiện traversal trên left subtree và cuối cùng là right subtree. Khi traverse left subtree và right subtree cũng tuân theo quy tắc preorder traversal, vì vậy có thể implement preorder traversal bằng recursion.

Code như sau:

public void preOrder(TreeNode root){
    if(root == null){
        return;
    }
    System.out.println(root.data);
    preOrder(root.left);
    preOrder(root.right);
}

Inorder traversal

Inorder traversal của binary tree là việc đệ quy thực hiện inorder traversal của left subtree trước, sau đó output value của root node, rồi đệ quy thực hiện inorder traversal của right subtree. Bạn có thể hình dung việc dùng một bàn tay ép phẳng tree: parent node bị ép vào giữa left child node và right child node, như hình dưới đây:

Code như sau:

public void inOrder(TreeNode root){
    if(root == null){
        return;
    }
    inOrder(root.left);
    System.out.println(root.data);
    inOrder(root.right);
}

Postorder traversal

Postorder traversal của binary tree là việc đệ quy thực hiện postorder traversal của left subtree trước, sau đó đệ quy thực hiện postorder traversal của right subtree, cuối cùng output value của root node.

Code như sau:

public void postOrder(TreeNode root){
    if(root == null){
        return;
    }
    postOrder(root.left);
    postOrder(root.right);
    System.out.println(root.data);
}

Trọng tâm ôn tập phỏng vấn

Trong phỏng vấn về tree structure, câu hỏi thường bắt đầu từ binary tree traversal, sau đó lần lượt hỏi sâu về binary search tree, balanced tree, B tree và B+ tree.

Structure	Đặc điểm	Câu hỏi thường gặp
Binary tree	Mỗi node có nhiều nhất hai child node	Traversal, path, lowest common ancestor, xây dựng tree
Binary search tree	Left subtree nhỏ hơn root, right subtree lớn hơn root	Inorder traversal có thứ tự, suy biến thành linked list
AVL tree	Height-balanced	Query nhanh, insert/delete cần rotation thường xuyên hơn
Red-black tree	Gần balanced	Java TreeMap, tree hóa HashMap
B tree	Multi-way balanced search tree	Thân thiện với disk IO
B+ tree	Data thường nằm ở leaf node, các leaf node được nối bằng linked list có thứ tự	MySQL index, range query

Cần tự viết được template traversal binary tree:

void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    // Vị trí preorder
    dfs(root.left);
    // Vị trí inorder
    dfs(root.right);
    // Vị trí postorder
}

Các câu trả lời thường gặp về BST:

• Inorder traversal của binary search tree cho ra một sequence tăng dần.
• Nếu data được insert vốn đã có thứ tự, BST thông thường sẽ suy biến thành linked list.
• AVL tree balance chặt chẽ hơn red-black tree, query ổn định hơn; yêu cầu balance của red-black tree rộng hơn, chi phí điều chỉnh khi insert/delete thấp hơn.
• B+ tree phù hợp với database index: mỗi node có thể lưu nhiều key hơn, height của tree thấp hơn, linked list có thứ tự ở leaf node phù hợp với range query.

Có thể phân loại các bài toán thuật toán về binary tree dựa trên việc “current node đảm nhiệm vai trò gì trong recursion”:

• Nhóm path: current node cần được thêm vào path, sau khi recursion kết thúc thì undo; thường gặp trong path từ root đến leaf và path sum.
• Nhóm thông tin subtree: left subtree và right subtree trả kết quả trước, current node sau đó merge chúng; thường gặp khi tính height, diameter và balanced binary tree.
• Nhóm phân nhánh hội tụ: left subtree và right subtree lần lượt tìm target, current node xác định có phải điểm hội tụ hay không; thường gặp khi tìm lowest common ancestor.
• Nhóm construction: xác định root node trước, sau đó chia interval của left subtree và right subtree; thường gặp khi xây dựng binary tree từ preorder + inorder.

Java code template

Level-order traversal là template non-recursive thường gặp nhất trong phỏng vấn binary tree. Nhiều bài như “giá trị lớn nhất của mỗi level”, “zigzag traversal”, “minimum depth” đều có thể biến đổi từ template này.

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        ans.add(level);
    }
    return ans;
}

Khi verify BST, không nên chỉ so sánh current node với left child và right child. Cách đúng là truyền lower bound và upper bound cho mỗi subtree:

boolean isValidBST(TreeNode root) {
    return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

boolean check(TreeNode node, long lower, long upper) {
    if (node == null) {
        return true;
    }
    if (node.val <= lower || node.val >= upper) {
        return false;
    }
    return check(node.left, lower, node.val) && check(node.right, node.val, upper);
}

Lowest common ancestor (LCA) có thể xử lý theo tư duy postorder: left subtree và right subtree tìm target node trước, current node sau đó dựa vào return value để xác định có hội tụ hay không.

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) {
        return root;
    }
    return left != null ? left : right;
}

Ý nghĩa của đoạn code này là: nếu p và q lần lượt xuất hiện trong left subtree và right subtree thì current node là lowest common ancestor; nếu chỉ xuất hiện ở một bên thì tiếp tục return kết quả của bên đó lên trên.

Khi xây dựng binary tree từ preorder + inorder, phần tử đầu tiên của preorder array là root node; trong inorder array, phần bên trái root node là left subtree, phần bên phải là right subtree. Để tránh phải tìm root node bằng cách tìm tuyến tính trong array mỗi lần, thông thường trước tiên dùng hash table để ghi lại index trong inorder.

TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> index = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        index.put(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1, index);
}

TreeNode build(
    int[] preorder,
    int preLeft,
    int preRight,
    int inLeft,
    int inRight,
    Map<Integer, Integer> index
) {
    if (preLeft > preRight) {
        return null;
    }
    int rootVal = preorder[preLeft];
    int rootIndex = index.get(rootVal);
    int leftSize = rootIndex - inLeft;
    TreeNode root = new TreeNode(rootVal);
    root.left = build(preorder, preLeft + 1, preLeft + leftSize, inLeft, rootIndex - 1, index);
    root.right = build(preorder, preLeft + leftSize + 1, preRight, rootIndex + 1, inRight, index);
    return root;
}

Điểm dễ sai nhất trong bài toán construction là boundary của các interval. Bạn nên viết rõ ý nghĩa của preLeft/preRight và inLeft/inRight trước, sau đó dựa vào kích thước left subtree leftSize để chia preorder array.

Minh họa quy trình và các ví dụ boundary

Với bài toán binary tree, trước tiên có thể xác định “current node cần làm gì”, rồi quyết định dùng preorder, inorder, postorder hay level-order.

Preorder: xử lý current node trước, sau đó xử lý left subtree và right subtree, phù hợp để copy tree và xây dựng path.
Inorder: left -> root -> right, kết quả inorder trong BST có thứ tự.
Postorder: xử lý left subtree và right subtree trước, sau đó xử lý current node, phù hợp để tính height, diameter và xóa node.
Level-order: tiến hành theo từng level, phù hợp với minimum depth, thống kê theo level và serialization.

Trước khi tự viết, nên kiểm tra một số boundary case:

• Empty tree: nhiều bài nên return empty list, 0 hoặc true.
• Chỉ có một node: cả điểm thoát của recursion và level-order queue đều phải xử lý được.
• Tree suy biến thành linked list: depth của recursion có thể đạt n, không được viết nhầm complexity thành O(logn).
• BST có Integer.MIN_VALUE / Integer.MAX_VALUE: nên dùng long cho upper bound và lower bound.
• Trong LCA, một target node là ancestor của target node còn lại: khi gặp target node phải return current node ngay.
• Khi xây dựng tree mà array rỗng: recursive interval sẽ trở thành preLeft > preRight, cần return null.

Bài tập đề xuất

• 144. Binary Tree Preorder Traversal
• 102. Binary Tree Level Order Traversal
• 98. Validate Binary Search Tree
• 236. Lowest Common Ancestor of a Binary Tree
• 105. Construct Binary Tree from Preorder and Inorder Traversal

Lời cuối

Nếu nội dung hữu ích với bạn, hãy tiện tay tặng JavaGuide một Star miễn phí để ủng hộ: GitHub | Gitee.

JavaGuide đã được duy trì gần bảy năm, tích lũy 6100+ commit, với sự chung tay hoàn thiện của 620+ contributor. Star, phản hồi và PR của bạn đều là động lực để dự án tiếp tục cập nhật.

Nếu bạn đang chuẩn bị phỏng vấn backend / phát triển ứng dụng AI, có thể tham khảo Knowledge Planet của tôi, bao gồm các project thực tế về backend và AI, tối ưu CV, hỏi đáp 1-1 và tài liệu về các trọng điểm thường gặp, đã được duy trì liên tục sáu năm.