- vừa được xem lúc

Chương 6: TREES - 3.Binary Trees: Problems & Solutions(01-12)

0 0 20

Người đăng: Đặng An

Theo Viblo Asia

Problem-1

Đưa ra thuật toán tìm phần tử lớn nhất trong cây nhị phân.

Solution: Một cách đơn giản để giải quyết vấn đề này là: tìm phần tử lớn nhất trong cây con bên trái, tìm phần tử lớn nhất trong cây con bên phải, so sánh chúng với dữ liệu gốc và chọn phần tử cho giá trị lớn nhất.
Cách tiếp cận này có thể dễ dàng thực hiện với đệ quy.

public int maxInBinaryTree(BinaryTreeNode root) { int maxValue = Integer.MIN_VALUE; if(root != null) { int leftMax = maxInBinaryTree(root.left); int rightMax = maxInBinaryTree(root.right); if(leftMax > rightMax) { maxValue = leftMax; } else { maxValue = rightMax; } if(root.data > maxValue) { maxValue = root.data; } } return maxValue; }

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

Problem-2

Đưa ra thuật toán tìm phần tử lớn nhất trong cây nhị phân mà không sử dụng đệ quy.

Solution: Sử dụng level order traversal: chỉ cần quan sát dữ liệu của phần tử trong khi xóa.

	public int maxInBinaryTreeLevelOrder(BinaryTreeNode root){ if(root == null) { return Integer.MIN_VALUE; } int max = Integer.MIN_VALUE; Queue<BinaryTreeNode> q = new LinkedList<>(); q.offer(root); while(!q.isEmpty()) { BinaryTreeNode tmp = q.poll(); if(tmp.data > max) { max = tmp.data; } if(tmp != null) { if(tmp.left != null) { q.offer(tmp.left); } if(tmp.right != null) { q.offer(tmp.right); } } } return max; }

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

Problem-3

Đưa ra thuật toán tìm kiếm một phần tử trong cây nhị phân.

Solution: Cho một cây nhị phân, trả về true nếu tìm thấy một nút có dữ liệu trong cây. Truy hồi xuống cây, chọn nhánh trái hoặc nhánh phải, so sánh dữ liệu với dữ liệu từng nút.

	public static boolean findInBT(BinaryTreeNode root, int data) { if(root == null) { return false; } if(root.data == data) { return true; } return findInBT(root.left, data) || findInBT(root.right, data); }

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

Problem-4

Đưa ra thuật toán tìm kiếm một phần tử trong cây nhị phân không sử dụng đệ quy.

Solution: Sử dụng level order traversal: chúng ta chỉ cần kiểm tra xem dữ liệu gốc có bằng phần tử mà chúng ta muốn tìm kiếm hay không.

	public boolean maxInBinaryTreeLevelOrder(BinaryTreeNode root, int data){ if(root == null) { return false; } Queue<BinaryTreeNode> q = new LinkedList<>(); q.offer(root); while(!q.isEmpty()) { BinaryTreeNode tmp = q.poll(); if(tmp.data == data) { return true; } if(tmp != null) { if(tmp.left != null) { q.offer(tmp.left); } if(tmp.right != null) { q.offer(tmp.right); } } } return false; }

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

Problem-5

Đưa ra thuật toán insert một phần tử vào cây nhị phân.

Solution: Vì cây đã cho là cây nhị phân nên chúng ta có thể chèn phần tử vào bất cứ đâu chúng ta muốn. Để chèn một phần tử, chúng ta có thể sử dụng level order traversal và chèn phần tử vào bất cứ nơi nào chúng ta tìm thấy nút có con trái hoặc con phải là NULL.

	public BinaryTreeNode insertInBinaryTreeLevelOrder(BinaryTreeNode root, int data){ if(root == null) { return null; } Queue<BinaryTreeNode> q = new LinkedList<>(); q.offer(root); while(!q.isEmpty()) { BinaryTreeNode tmp = q.poll(); if(tmp != null) { if(tmp.left != null) { q.offer(tmp.left); }else { tmp.left = new BinaryTreeNode(data); return root; } if(tmp.right != null) { q.offer(tmp.right); }else { tmp.right = new BinaryTreeNode(data); return root; } } } return root; }

Nếu các bạn đọc trong sách thì có thể thấy code mình hơi khác 1 chút, khối 2 mình sẽ vẫn để nằm trong if của 1. Không biết tác giả có nhầm lẫn chỗ này không, nếu tmp = null, thì tmp.right sẽ gây ra exception.

Recursive Approach

	public void insertHelper(BinaryTreeNode root, int data) { if(root.data >= data){//Không nhất thiết phải có điều kiện này(Sử dụng tạo cây nhị phân cân bằng) if(root.left == null) { root.left = new BinaryTreeNode(data); }else { insertHelper(root.left, data); } }else { if(root.right == null) { root.right = new BinaryTreeNode(data); }else { insertHelper(root.right, data); } } }

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

Problem-6

Đưa ra một thuật toán tìm kiếm kích thước của binary tree.

Solution: Tính toán kích thước của các cây con bên trái và bên phải theo cách đệ quy, thêm 1 (nút hiện tại) và trở về nút cha của nó.

	public int size(BinaryTreeNode root) { int leftCount = root.left == null ? 0 : size(root.left); int rightCount = root.right == null ? 0 : size(root.right); return 1 + leftCount + rightCount; }

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

Problem-7

Chúng ta có thể giải Problem-6 mà không cần đệ quy không?

Solution: Yes, sử dụng level order traversal.

	public int size(BinaryTreeNode root, int data){ if(root == null) { return 0; } int count = 0; Queue<BinaryTreeNode> q = new LinkedList<>(); q.offer(root); while(!q.isEmpty()) { BinaryTreeNode tmp = q.poll(); count++; if(tmp != null) { if(tmp.left != null) { q.offer(tmp.left); } if(tmp.right != null) { q.offer(tmp.right); } } } return count; }

Problem-8

Đưa ra thuật toán xóa cây.

Solution: Để xóa một cây, chúng ta phải duyệt qua tất cả các nút của cây và xóa từng nút một. Vì vậy, chúng ta nên sử dụng giao dịch nào: Inorder, Preorder, Postorder hay Level order Traversal? Trước khi xóa nút cha, chúng ta nên xóa các nút con của nó trước. Chúng ta có thể sử dụng Postorder vì nó hoạt động mà không cần lưu trữ bất cứ thứ gì. Chúng ta có thể xóa cây với các đường ngang khác với độ phức tạp không gian bổ sung. Như ảnh dưới, các nút bị xóa theo thứ tự 4,5,2,3,1.

public void deleteBinaryTree(BinaryTreeNode root){ root = null; }

Trong các ngôn ngữ khác mà bạn phải tự mình quản lý bộ nhớ thì bạn có thể làm như soloution, còn java chỉ cần root = null, Garbage Collector sẽ lo phần còn lại.
Quản lý bộ nhớ và cơ chế của GC trong Java là những câu hỏi khá khó, mình thường thấy dành cho pv từ middle và senior trở lên(Các bạn có ai sắp phỏng vấn nên đọc thêm về phần này 😄)

Problem-9

Đưa ra thuật toán in dữ liệu thứ tự mức theo thứ tự ngược lại. Ví dụ: đầu ra cho cây bên dưới phải là: 4 5 6 7 2 3 1

Solution: Đơn giản là sử dụng thêm một stack trong Level Order Traversal

	public void levelOrderTraversalInReverse(BinaryTreeNode root, int data){ if(root == null) { return; } Stack<BinaryTreeNode> s = new Stack<>(); Queue<BinaryTreeNode> q = new LinkedList<>(); q.offer(root); while(!q.isEmpty()) { BinaryTreeNode tmp = q.poll(); if(tmp != null) { if(tmp.left != null) { q.offer(tmp.left); } if(tmp.right != null) { q.offer(tmp.right); } } s.push(tmp); } System.out.println(s); }

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

Problem-10

Đưa ra thuật toán tìm chiều cao (hoặc chiều sâu) của cây nhị phân.

Solution: Tính toán đệ quy chiều cao của các cây con bên trái và bên phải của một nút và gán chiều cao cho nút bằng chiều cao tối đa của hai phần tử con cộng với 1. Điều này tương tự với tính năng duyệt cây PreOrder (và DFS của thuật toán Đồ thị).

	public int maxDepth(BinaryTreeNode root) { if(root == null) { return 0; } int leftCount = maxDepth(root.left); int rightCount = maxDepth(root.right); return leftCount > rightCount ? 1 + leftCount : 1 + rightCount; }

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

Problem-11

Giải quyết Problem-10 không sử dụng đệ quy

Solution: Chúng ta có thể sử dụng ngăn xếp để mô phỏng đệ quy.

	public int maxDepthIterative(BinaryTreeNode root) { if(root == null) { return 0; } Stack<BinaryTreeNode> s = new Stack<>(); s.push(root); int maxDepth = 0; BinaryTreeNode prev = null; while(!s.isEmpty()) { BinaryTreeNode curr = s.peek(); if(prev == null || prev.left == curr || prev.right == curr) { if(curr.left != null) { s.push(curr.left); } else { if(curr.right != null) { s.push(curr.right); } } } else { if(curr.left == prev) { if(curr.right != null) { s.push(curr.right); } } else { s.pop(); } } prev = curr; if(s.size() > maxDepth) { maxDepth = s.size(); } } return maxDepth; }

Problem-12

Giải quyết Problem-10 không sử dụng đệ quy(Cách khác Problem-11)

Solution: Yes. Sử dụng level order traversal. Điều này tương tự như BFS của các thuật toán Đồ thị. Kết thúc cấp độ được xác định bằng NULL.

	public static int maxDepthLevelOrderTraversal(BinaryTreeNode root){ if(root == null) { return 0; } Queue<BinaryTreeNode> q = new LinkedList<>(); q.offer(root); q.offer(null); int count = 1; while(!q.isEmpty()) { BinaryTreeNode curr = q.poll(); if(curr != null) { if(curr.left != null) { q.offer(curr.left); } if(curr.right != null) { q.offer(curr.right); } } else { if(!q.isEmpty()) { count++; q.offer(null); } } } return count; }

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

Bình luận

Bài viết tương tự

- vừa được xem lúc

Đôi chút về cấu trúc dữ liệu và thuật toán

Theo anh Phạm Huy Hoàng (toidicodedao) đã viết trong blog của mình là kiến thức trong ngành IT có 2 loại, một là càng để lâu thì càng cũ, lạc hậu và trở lên vô dụng. Hai là càng để lâu thì càng có giá trị thậm chí ngày càng có giá.

0 0 32

- vừa được xem lúc

Cấu trúc dữ liệu Merkle Tree

Cây Merkle là một cây nhị phân có thứ tự được xây dựng từ một dãy các đối tượng dữ liệu (d1, d2,...,dn) sử dụng hàm băm h. Các “lá” của cây là các giá trị băm h(di) đối với 1 ≤ i ≤ n.

0 0 46

- vừa được xem lúc

Cách xây dựng cấu trúc dữ liệu Stack và Queue.

Mở đầu. Hello các bạn, hôm nay mình sẽ chia sẻ với các bạn cách để có thể tự xây dựng 2 loại cấu trúc dữ liệu stack(ngăn xếp) và queue(hàng đợi) sử dụng mảng trong C++;.

0 0 31

- vừa được xem lúc

Tối ưu ứng dụng với cấu trúc dữ liệu cơ bản

Ở Việt Nam có một nghịch lý ai cũng biết: hầu hết sinh viên ngành CNTT đều đã học cấu trúc dữ liệu và giải thuật, thuộc các môn bắt buộc. Thế nhưng lại rất hiếm khi ứng dụng vào công việc hoặc bị loại

0 0 36

- vừa được xem lúc

Chương 1: Introduction - Analysis of Algorithrms

Trong bài viết này mình sẽ nói về cách chúng ta sẽ sử dụng để phân tích và so sánh các loại thuật toán khác nhau. 1.

0 0 15

- vừa được xem lúc

Chương 1: Introduction - Các khái niệm cơ bản

Lời nói đầu. Trước khi có máy tính, đã có các thuật toán.

0 0 16