목차
* 🤓 INTRODUCTION
* 0️⃣1️⃣ ABOUT BINARY SEARCH TREES
* ⭕ CREATE A NODE
* 🔎 BINARY SEARCH TREE
* 🔍 FIND AN ELEMENT
* 👨🏻‍💻 CODE
* 🙏 THANK YOU

🤓 소개

Welcome, my dear hackers!🚀 Welcome to yet another blog article about elementary data structures.

If you missed the previous article where we describe the Binary trees, you can check it out right here:

더 이상 사용할 수 없는 기사

Today, we will show how to implement the binary search tree. We will concentrate on the implementation with a bit of theoretical explanation in the beginning. 🚀

Please feel free to connect with me via , or

0️⃣1️⃣ 이진 검색 트리에 대해

Basic operations on a binary search tree take time proportional to the height of the tree. For a complete binary tree with n nodes, such operations run in the O(logn) worst-case time.
If the tree is a linear chain of n nodes, however, the same operations take O(n) worst-case time.
In practice, we can’t always guarantee that binary search trees are built randomly, but we can design variations of binary search trees with good guaranteed
worst-case performance on basic operations.

A binary search tree is organized, as the name suggests, in a binary tree, that we discussed in the previous chapter. There, we concluded that we can represent such a tree by a linked data structure in which each node is an object. In addition to a key and satellite data, each node contains attributes left, right and a pointer that points to the nodes corresponding to its left child, its right child, and its parent, respectively. So, if a child or the parent is missing, the appropriate attribute contains the value of NULL. The root node is the only node in the tree whose parent is NULL. The keys in a binary search tree are always stored in such a way as to satisfy the binary search tree property.

Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y:key <= x:key. If y is a node in the right subtree of x, then y:key >= x:key.

The binary-search-tree property allows us to print out all the keys in a binary search tree in sorted order by a simple recursive algorithm, called an inorder tree walk. This algorithm is so named because it prints the key of the root of a subtree between printing the values in its left subtree and printing those in its right subtree. (Similarly, a preorder tree walk prints the root before the values in either subtree and a postorder tree walk prints the root after the values in its subtrees.)

⭕ 노드 생성

이미지에서 볼 수 있듯이 멤버 클래스 변수 값에 할당되는 값의 인수를 취하는 생성자가 있는 BSTNod(이진 검색 트리 노드) 클래스가 있습니다. 또한 왼쪽과 오른쪽에 각각 왼쪽 자식과 오른쪽 자식을 가리키는 두 개의 포인터가 있습니다. 카운터는 노드 값의 복제를 제어하는 데 사용됩니다. 예를 들어 트리의 노드와 동일한 값을 가진 다른 노드를 추가하려고 하면 카운터만 증가할 뿐 해당 노드를 트리에 추가하지는 않습니다.

🔎 이진 검색 트리

🔍 요소 찾기

👨🏻‍💻 코드

class BSTNode {
  constructor(value) {
    this.value = value;
    this.right = null;
    this.left = null;
    this.count = 0;
  }
}

class BST {
  constructor() {
    this.root = null;
  }
  create(value) {
    const newNode = new BSTNode(value);
    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 (value === current.value) {
        current.count++;
        return this;
      }
      if (value < current.value) addSide('left');
      else addSide('right');
    }
  }
  find(value) {
    if (!this.root) return undefined;
    let current = this.root;
    let found = false;

    while (current && !found) {
      if (value < current.value) current = current.left;
      else if (value > current.value) current = current.right;
      else found = true;
    }

    if (!found) return 'Oops! Nothing found!';
    return current;
  }
}

let binary_search_tree = new BST();
binary_search_tree.create(100);
binary_search_tree.create(2);
binary_search_tree.create(21);
binary_search_tree.create(221);
binary_search_tree.create(3);
binary_search_tree.create(44);
console.log(binary_search_tree)

The expected output should be something like this:

🙏 읽어주셔서 감사합니다!

Stay tuned for the next chapter of this article where we will implement deletion and traversal logic!

References:
School notes...
School books...

Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me!

☕ SUPPORT ME AND KEEP ME FOCUSED!

즐거운 해킹 시간 되세요! 😊

Reference

이 문제에 관하여(JavaScript를 사용한 기본 데이터 구조 - 이진 트리 - 2부🚀), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/devlazar/elementary-data-structures-with-javascript-binary-trees-part-2-1pl6

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)

JavaScript를 사용한 기본 데이터 구조 - 이진 트리 - 2부🚀