Triển khai cây tìm kiếm nhị phân trong JavaScript

Cấu trúc dữ liệu dạng cây

Cây là một tập hợp các nút được nối với nhau bằng một số cạnh. Thông thường, mỗi nút của một cây chứa một số dữ liệu và tham chiếu đến các nút con của nó.

Cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân là cây nhị phân trong đó các nút có giá trị nhỏ hơn được lưu trữ ở bên trái trong khi các nút có giá trị cao hơn được lưu trữ ở bên phải.

Ví dụ:mô tả trực quan của một BST hợp lệ là -

     25
   /   \
  20   36
 / \   / \
10 22 30 40

Bây giờ chúng ta hãy triển khai Cây tìm kiếm nhị phân rất riêng của chúng ta bằng ngôn ngữ JavaScript.

Bước 1:Lớp nút

Lớp này sẽ đại diện cho một nút duy nhất hiện diện tại các điểm khác nhau trong BST. BST không là gì ngoài tập hợp các nút lưu trữ dữ liệu và các tham chiếu con được đặt theo các quy tắc được mô tả ở trên.

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};

Để tạo một phiên bản Node mới, chúng ta có thể gọi lớp này như thế này với một số dữ liệu -

const newNode = new Node(23);

Thao tác này sẽ tạo một phiên bản Node mới với dữ liệu được đặt thành 23 và tham chiếu trái và phải đều là null.

Bước 2:Lớp cây tìm kiếm nhị phân:

class BinarySearchTree{
   constructor(){
      this.root = null;
   };
};

Thao tác này sẽ tạo ra lớp Cây tìm kiếm nhị phân mà chúng ta có thể gọi bằng từ khóa mới để tạo phiên bản miễn phí.

Bây giờ khi chúng ta đã hoàn thành những việc cơ bản, hãy chuyển sang chèn một nút mới vào đúng vị trí (theo các quy tắc của BST được mô tả trong định nghĩa).

Bước 3:Chèn một nút vào BST

class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};

Ví dụ

Mã cây tìm kiếm nhị phân đầy đủ:

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};
const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);