Data Structure & Algorithm(EP.11) — Binary Search Tree (BST)

• โหนดลูกที่อยู่ด้านซ้ายของโหนดแม่จะเรียกว่า ทรีย่อยซ้าย (TL) เป็นกลุ่มข้อมูลที่มีค่าน้อยกว่าโหนดแม่

• โหนดลูกที่อยู่ด้านขวาของโหนดแม่จะเรียกว่า ทรีย่อยขวา (TR) เป็นกลุ่มข้อมูลที่มีค่ามากกว่าโหนดแม่

สร้าง Binary Search Tree (BST)

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
}
let myBST = new BinarySearchTree();
console.log(myBST);

เพิ่มโหนดใน Binary Search Tree (Insert)

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    let temp = this.root;
    while (true) {
      if (newNode.value === temp.value) return undefined;
      if (newNode.value < temp.value) {
        if (temp.left === null) {
          temp.left = newNode;
          return this;
        }
        temp = temp.left;
      } else {
        if (temp.right === null) {
          temp.right = newNode;
          return this;
        }
        temp = temp.right;
      }
    }
  }
}
let myBST = new BinarySearchTree();
myBST.insert(47);
myBST.insert(21);
myBST.insert(76);
console.log(myBST);

/*
    แผนภาพไบนารีทรี
        47
       / \
      21  76
*/

ตรวจสอบข้อมูลใน Binary Search Tree (Contains)

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    let temp = this.root;
    while (true) {
      if (newNode.value === temp.value) return undefined;
      if (newNode.value < temp.value) {
        if (temp.left === null) {
          temp.left = newNode;
          return this;
        }
        temp = temp.left;
      } else {
        if (temp.right === null) {
          temp.right = newNode;
          return this;
        }
        temp = temp.right;
      }
    }
  }
  contains(value) {
    if (this.root === null) return false;
    let temp = this.root;
    while (temp) {
      if (value < temp.value) {
        temp = temp.left;
      } else if (value > temp.value) {
        temp = temp.right;
      } else {
        return true;
      }
    }
    return false;
  }
}
let myBST = new BinarySearchTree();
myBST.insert(47);
myBST.insert(21);
myBST.insert(76);
myBST.insert(18);
myBST.insert(27);
myBST.insert(52);
myBST.insert(82);

console.log(myBST.contains(15));
console.log(myBST.contains(76));

หาค่าต่ำสุดใน Binary Search Tree (Minimum Value)

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    let temp = this.root;
    while (true) {
      if (newNode.value === temp.value) return undefined;
      if (newNode.value < temp.value) {
        if (temp.left === null) {
          temp.left = newNode;
          return this;
        }
        temp = temp.left;
      } else {
        if (temp.right === null) {
          temp.right = newNode;
          return this;
        }
        temp = temp.right;
      }
    }
  }
  contains(value) {
    if (this.root === null) return false;
    let temp = this.root;
    while (temp) {
      if (value < temp.value) {
        temp = temp.left;
      } else if (value > temp.value) {
        temp = temp.right;
      } else {
        return true;
      }
    }
    return false;
  }
  minimumNode(currentNode) {
    while (currentNode.left !== null) {
      currentNode = currentNode.left;
    }
    return currentNode;
  }
}
let myBST = new BinarySearchTree();
myBST.insert(47);
myBST.insert(21);
myBST.insert(76);
myBST.insert(18);
myBST.insert(27);
myBST.insert(52);
myBST.insert(82);
console.log(myBST.minimumNode(myBST.root))
console.log(myBST.minimumNode(myBST.root).value)

บทความที่เกี่ยวข้อง

• EP.1 — รู้จักกับโครงสร้างข้อมูลและอัลกอริทึม
• EP.2 — การวัดประสิทธิภาพอัลกอริทึม
• EP.3 — อัตราการเติบโตของฟังก์ชั่น
• EP.4 — การวิเคราะห์อัลกอริทึม
• EP.5 — Big-O Notation
• EP.6 — การคำนวณ Big-O
• EP.7 — ลิงค์ลิสต์ (Linked-List)
• EP.8 — สแต็ก (Stack)
• EP.9 — คิว(Queue)
• EP.10 — ทรี (Tree)
• EP.11 — Binary Search Tree (BST)
• EP.12 — กราฟ(Graphs)

เนื้อหาที่เกี่ยวข้อง

ช่องทางการสนับสนุน
🎓 คอร์สพัฒนาเว็บด้วย JavaScript 40 Workshop

🌎 ติดตามข่าวสารเพิ่มเติมได้ที่
Facebook | YouTube | TikTok