JavaScriptを持つ基本データ構造-バイナリツリー-パート2🚀

14575 ワード
javascript webdev programming algorithms テキストリンク
目次
* 🤓 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:

JavaScriptを持つ基本データ構造-バイナリツリー-パート1🚀

コデスプレッシャー・ 2月13日・ 3分読む

#javascript #programming #codequality #webdev

今日、バイナリ検索ツリーの実装方法を示します.最初に、理論的説明の少しで実装に集中します.🚀
お気軽にご連絡ください

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.)

⭕ ノードを作る


イメージで見ることができるように、メンバークラス変数変数に値の引数を代入するコンストラクターを持つクラスBSTNode(バイナリ検索ツリーノード)がありますまた、左と右の2つのポインタを持っています.カウンタは、ノード値の複製を制御するために使用されます.たとえば、ツリー内の任意のノードと同じ値を持つノードを追加しようとすると、カウンタを増加させますが、ツリーにそのノードを追加しないでください.

🔎 バイナリ検索ツリー


🔍 要素を見つける


👨🏻‍💻 コード

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!
楽しい時間をハッキング!😊
[プログラマー]通学路
[白俊](Java)1987-アルファベット