Tree Traversal qua JavaScript
Cây về cơ bản chỉ là danh sách được liên kết lạ mắt và việc tạo và xóa các node trên cây cực kỳ đơn giản. Mặt khác, tìm kiếm phức tạp hơn một chút khi chúng không được sắp xếp, vì vậy ta sẽ xem xét một số cách khác nhau để xử lý việc tìm kiếm trong toàn bộ cây.
Yêu cầu
Bạn cần hiểu biết cơ bản về cây cối là gì và chúng hoạt động như thế nào. Ví dụ cụ thể của ta về việc sử dụng Cây tìm kiếm binary , nhưng đây là những kỹ thuật và mẫu nhiều hơn là triển khai chính xác và có thể dễ dàng điều chỉnh cho bất kỳ loại cây nào.
Các khái niệm
Với cây tìm kiếm binary , ta có thể sử dụng cùng một hệ thống để tạo một nút mới để tìm một nút. Cây tiêu chuẩn, giống như hệ thống file của bạn, không tuân theo bất kỳ luật cụ thể nào và buộc ta phải xem xét mọi mục thông qua một cây hoặc cây con để tìm những gì ta muốn. Đây là lý do tại sao việc chạy tìm kiếm một file cụ thể có thể mất nhiều thời gian.
Không có nhiều cách để tối ưu hóa O(n) trong quá khứ nhưng có hai “triết lý” chính để tìm kiếm trong toàn bộ cây, hoặc bằng cách tìm kiếm theo chiều rộng (theo chiều ngang giữa các anh chị em) hoặc theo chiều sâu (theo chiều dọc giữa cha mẹ và con cái) .
Cây
Vì cây tìm kiếm binary là cây dễ cài đặt nhất, ta có thể kết hợp một cây nhanh chóng mà chỉ có thể thêm các node .
class Node { constructor(val) { this.val = val; this.right = null; this.left = null; }; }; class BST { constructor() { this.root = null; }; create(val) { const newNode = new Node(val); if (!this.root) { this.root = newNode; return this; }; let current = this.root; const addSide = side => { if (!current[side]) { current[side] = newNode; return this; }; current = current[side]; }; while (true) { if (val === current.val) return this; if (val < current.val) addSide('left'); else addSide('right'); }; }; }; const tree = new BST(); tree.create(20); tree.create(14); tree.create(57); tree.create(9); tree.create(19); tree.create(31); tree.create(62); tree.create(3); tree.create(11); tree.create(72); Breadth-First Search
Tìm kiếm theo chiều rộng có đặc điểm là nó tập trung vào mọi mục, từ trái sang phải, ở mọi cấp độ trước khi chuyển sang cấp độ tiếp theo.
Có ba phần chính của điều này, nút hiện tại, danh sách các node đã truy cập của ta và một hàng đợi cơ bản để theo dõi các node nào ta cần xem xét ( ta sẽ chỉ sử dụng một mảng vì nó sẽ không bao giờ dài) .
Ta hãy xem xét nó sẽ trông như thế nào trên cây này.
Cho dù current của ta là gì, ta sẽ đẩy con của nó (từ trái sang phải) vào hàng đợi của ta , vì vậy nó sẽ giống như [20, 14, 57] . Sau đó, ta sẽ thay đổi mục current thành mục tiếp theo trong hàng đợi và thêm các mục con bên trái và bên phải của nó vào cuối hàng đợi, [14, 57, 9, 19] .
Mục hiện tại của ta hiện có thể được xóa và thêm vào visited trong khi ta chuyển sang mục tiếp theo, tìm kiếm các mục con của nó và thêm chúng vào hàng đợi. Điều này sẽ lặp lại cho đến khi hàng đợi của ta trống và mọi giá trị đều được visited .
BFS() { let visited = [], queue = [], current = this.root; queue.push(current); while (queue.length) { current = queue.shift(); visited.push(current.val); if (current.left) queue.push(current.left); if (current.right) queue.push(current.right); }; return visited; } console.log(tree.BFS()); //[ 20, 14, 57, 9, 19, 31, 62, 3, 11, 72 ] Tìm kiếm sâu-đầu tiên
Tìm kiếm theo chiều sâu quan tâm hơn đến việc hoàn thành một đường đi xuống toàn bộ phía của cây đến lá hơn là hoàn thành mọi cấp độ.
Có ba cách chính để xử lý điều này, preOrder , postOrder và inOrder nhưng chúng chỉ là những sửa đổi rất nhỏ của nhau để thay đổi thứ tự kết quả . Tốt hơn, ta thậm chí không cần phải lo lắng về hàng đợi nữa.
Bắt đầu từ root , ta sẽ sử dụng một hàm đệ quy ngắn để ghi lại nút của ta trước khi di chuyển xuống bên trái càng xa càng tốt, ghi lại đường dẫn của nó trên đường đi. Khi phần bên trái được thực hiện, nó sẽ bắt đầu làm việc với các giá trị bên phải còn lại cho đến khi toàn bộ cây đã được ghi lại. Cuối cùng được truy cập sẽ giống như [24, 14, 9, 3, 11, 19, ...] .
preOrder() { let visited = [], current = this.root; let traverse = node => { visited.push(node.val); if (node.left) traverse(node.left); if (node.right) traverse(node.right); }; traverse(current); return visited; } console.log(tree.preOrder()); // [ 20, 14, 9, 3, 11, 19, 57, 31, 62, 72 ] Như bạn có thể đoán, postOrder ngược lại với preOrder , ta vẫn đang làm việc theo chiều dọc nhưng thay vì chuyển từ root sang lá, ta sẽ tìm kiếm từ dưới lên trên.
Ta sẽ bắt đầu từ nút dưới cùng bên trái và ghi lại nó và các anh chị em của nó trước khi chuyển đến nút cha của chúng. Nửa đầu của lượt truy cập sẽ trông như thế này, [3, 11, 9, 19, 14, ...] , vì nó hoạt động như bong bóng lên cây.
Ta có thể dễ dàng đạt được điều này bằng cách đẩy các node của ta vào lượt visited sau khi cả hai lần duyệt hoàn thành.
postOrder() { let visited = [], current = this.root; let traverse = node => { if (node.left) traverse(node.left); if (node.right) traverse(node.right); visited.push(node.val); }; traverse(current); return visited; } console.log(tree.postOrder()); // [ 3, 11, 9, 19, 14, 31, 72, 62, 57, 20 ] Tương tự như postOrder , lượt truy cập preOrder hoạt động từ dưới lên nhưng nó chỉ thăm cha mẹ trước bất kỳ anh chị em nào.
Thay vì bắt đầu hoặc kết thúc, ta có thể đẩy vào danh sách của bạn sau khi ta đi qua bên trái và trước bên phải. Kết quả của ta sẽ giống như sau, [3, 9, 11, 14, 19, 20, ...] .
inOrder() { let visited = [], current = this.root; let traverse = node => { if (node.left) traverse(node.left); visited.push(node.val); if (node.right) traverse(node.right); }; traverse(current); return visited; } console.log(tree.inOrder()); // [ 3, 9, 11, 14, 19, 20, 31, 57, 62, 72 ] Bớt tư tưởng
Tất nhiên tất cả các thuật toán này sẽ là O(n) vì mục đích là xem xét mọi nút, không có nhiều chỗ cho các góc cắt hoặc các thủ thuật thông minh.
Lưu ý đây không phải là những cách triển khai chính xác cần phải ghi nhớ mà là những mẫu chung để giải quyết vấn đề và xây dựng các thuật toán có giá trị hơn. Khi bạn hiểu các khái niệm được gạch dưới, chúng có thể dễ dàng được điều chỉnh cho phù hợp với bất kỳ ngôn ngữ hoặc khuôn khổ nào.
Các tin liên quan
Hiểu về Trình tạo trong JavaScript2020-02-28
Triển khai Thành phần Tab từ Scratch trong Vanilla JavaScript
2020-02-24
Khám phá cây qua JavaScript
2020-02-23
Giới thiệu về danh sách được liên kết qua JavaScript - Phần 2: Triển khai
2020-02-23
Khám phá các và hàng đợi qua JavaScript
2020-02-23
Câu hỏi phỏng vấn JavaScript: Gotchas phổ biến
2020-02-21
Giới thiệu về danh sách được liên kết qua JavaScript - Phần 1: Tổng quan
2020-02-21
Hiểu Radix Sắp xếp Thông qua JavaScript
2020-02-18
Cách xây dựng PWA trong Vanilla JavaScript
2020-02-17
Hiểu về Sắp xếp nhanh qua JavaScript
2020-02-14
