Cây tìm kiếm nhị phân thông qua JavaScript
Vấn đề với các cấu trúc cây thông thường là chúng không được sắp xếp và rất khó sử dụng để làm việc. Nếu bạn chạy tìm kiếm một file trên máy tính của bạn , thông thường sẽ mất khá nhiều thời gian, điều này là do các file của bạn không được sắp xếp và nó phải tìm kiếm qua MỌI THỨ để có kết quả. Ta có thể cải thiện nhiều điều này bằng cách nâng cấp cách ta tổ chức các giá trị trong cây của bạn .
Yêu cầu
Bạn cần biết các khái niệm cơ bản về cây, bạn có thể tìm hiểu ở đây , ta cũng cần thực hiện một số thao tác tìm kiếm cơ bản về cây với tìm kiếm theo chiều rộng mà bạn có thể tìm hiểu tại đây .
Ý tưởng
Cây binary chỉ là một cây bình thường với giới hạn là mỗi nút chỉ có thể có tối đa hai nút con. Cây tìm kiếm binary chỉ có luật bổ sung rằng nếu có hai giá trị thì chúng cần được sắp xếp theo thứ tự, trong trường hợp của ta là từ số thấp hơn ở bên trái đến cao hơn ở bên phải.
Tìm kiếm trên cây tìm kiếm binary là một cải tiến lớn về tốc độ tìm kiếm O(n) ban đầu của ta kể từ bây giờ để tìm thứ gì đó, ta chỉ cần so sánh những gì ta muốn với mỗi nút cha trước khi di chuyển sang trái hoặc phải cho đến khi ta đạt được những gì ta muốn, cho ta O(logn) cho tất cả các hoạt động.
Tạo nên
Rất giống với danh sách liên kết, ta có thể sử dụng các lớp để tạo các node và cây của ta . Mỗi nút chỉ thực sự cần một con trỏ tới các cạnh bên trái / nhỏ hơn và bên phải / lớn hơn, và cá nhân tôi muốn thêm một bộ đếm vì các giá trị lặp lại chỉ có thể tồn tại một lần trong cây.
Sau khi kiểm tra xem đã có gì chưa, ta có thể sử dụng một chức năng tiện ích nhỏ xinh để nâng cao giá trị của ta . Rất đơn giản, ta chỉ cần lặp qua cây, nếu giá trị của ta nhỏ hơn nút hiện tại thì di chuyển sang trái, di chuyển sang phải, nếu không có gì trở thành nút mới ở vị trí đó, nếu giá trị khớp đã ở đó thì ta có thể tăng quầy tính tiền.
class Node { constructor(val) { this.val = val; this.right = null; this.left = null; this.count = 0; }; }; 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) { current.count++; return this; }; if (val < current.val) addSide('left'); else addSide('right'); }; }; }; let tree = new BST(); tree.add(10); tree.add(4); tree.add(4); tree.add(12); tree.add(2); console.log(tree); Tìm thấy
Việc tìm kiếm thứ gì đó cực kỳ đơn giản, chỉ cần di chuyển sang trái hoặc phải so với giá trị hiện tại và trả về true nếu ta gặp thứ gì đó phù hợp.
find(val) { if (!this.root) return undefined; let current = this.root, found = false; while (current && !found) { if (val < current.val) current = current.left; else if (val > current.val) current = current.right; else found = true; }; if (!found) return 'Nothing Found!'; return current; }; Xóa bỏ
Xóa là thao tác phức tạp nhất vì ta không làm việc chỉ với các lá mà phải cơ cấu lại, hoặc “cân bằng lại”, tất cả các node con của một nút. Có 2 điều kiện mà ta phải kiểm tra, đó là nút có phải là một lá hay không và nó có con hay không.
Đầu tiên, ta cần một chức năng tiện ích để thu thập tất cả các node con đã bị xóa. Tôi sẽ sử dụng tìm kiếm theo chiều rộng cơ bản trước tiên để đẩy mọi thứ vào một mảng mà sau đó ta có thể lặp lại để thêm lại từng mục vào cây.
Sự khác biệt duy nhất so với tìm kiếm thông thường là nó cần phải chấp nhận một điểm bắt đầu khác, vì vậy ta có thể giới hạn tìm kiếm của bạn chỉ trong cây con của các node con đã xóa của ta .
BFS(start) { let data = [], queue = [], current = start ? this.find(start) : this.root; queue.push(current); while (queue.length) { current = queue.shift(); data.push(current.val); if (current.left) queue.push(current.left); if (current.right) queue.push(current.right); }; return data; } Vì ta không thể backup trở lại nút cha, ta sẽ sử dụng một biến để lưu trữ nút cha thành current và sử dụng biến đó để đặt current thành null sau khi ta đã lưu các node con.
Trong deleteNode ta sẽ thu thập các node con của ta , đặt nó trên nút cha của nó thành null , sau đó sử dụng create trên từng nút con, cấu trúc lại chúng đúng cách trong cây. Mảng con của ta cũng sẽ bao gồm nút đã xóa, mà ta có thể tách ra.
delete(val) { if (!this.root) return undefined; let current = this.root, parent; const pickSide = side => { if (!current[side]) return 'No node found!'; parent = current; current = current[side]; }; const deleteNode = side => { if (current.val === val && current.count > 1) current.count--; else if (current.val === val) { const children = this.BFS(current.val); parent[side] = null; children.splice(0, 1); children.forEach(child => this.create(child)); }; }; while (current.val !== val) { if (val < current.val) { pickSide('left'); deleteNode('left'); }; else { pickSide('right'); deleteNode('right'); }; }; return current; } Kết luận
Đây sẽ là các hoạt động CRUD đầy đủ, vì bất kỳ bản cập nhật nào về cơ bản chỉ là xóa một nút và tạo một nút hoàn toàn mới ở một nơi khác, điều này không thực sự cần phương pháp riêng của nó.
Ta sẽ có thể thực hiện một số điều thú vị hơn với cây tìm kiếm binary khi ta di chuyển vào đống binary và hàng đợi ưu tiên.
Các tin liên quan
Tree Traversal qua JavaScript2020-03-02
Hiểu về Trình tạo trong JavaScript
2020-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
