データ構造⑤ 木構造(Trees)

木構造とは

木構造とは、階層的な構造を表現するためのデータ構造であり、ノードと呼ばれる要素がエッジと呼ばれるリンクによって繋がれている。繋がれているノードは親子関係を持っており、繋がっているノードのうち、上の階層にあるノードを親ノード(parent node)、下の階層にあるものを子ノード(child node)と呼ぶ。また、木構造のうち、最上位にある、親ノードを持たないノードを根ノード(root node)、末端のノードを葉ノード(leaf node)と呼ぶ。

木構造には、B木や赤黒木、トライ木などが様々な木構造が存在するが、このページでは基礎的な二分探索木を扱う。

---

実装

二分探索木の実装は以下。二分探索木とは、親ノードが持つ子ノードは最大二つであり、親ノードの右側にある子ノードが持つ値は親ノードの持つ値よりも大きく、親ノードの左側にある子ノードが持つ値は親ノードの持つ値よりも小さいという性質を持つ木構造である。二分探索木は、この性質により探索が効率的に行うことができ、挿入、削除も効率的に行うことができる。

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) {
      this.root = newNode;  
    } else {
      let currentNode = this.root;
      
      while (true) {
        if (value < currentNode.value) {
          if (!currentNode.left) {
            currentNode.left = newNode;
            return this;
          }
          currentNode = currentNode.left;
        } else {
          if (!currentNode.right) {
            currentNode.right = newNode;
            return this;
          }
          currentNode = currentNode.right;
        } 
      }
    }
  }

  lookup(value) {
    if(!this.root) {
      return false;
    }
    
    let currentNode = this.root;
    
    while(currentNode) {
      if (value > currentNode.value){
        currentNode = currentNode.right;
      } else if (value < currentNode.value) {
        currentNode = currentNode.left;
      } else {
        return currentNode;
      }
    }

    return false;
  }

  remove(value) {
    if (!this.root) {
      return false;
    }
    
    let currentNode = this.root;
    let parentNode = null;
    while (currentNode) {
      if (value < currentNode.value) {
        parentNode = currentNode;
        currentNode = currentNode.left;
      } else if (value > currentNode.value) {
        parentNode = currentNode;
        currentNode = currentNode.right;
      } else if (currentNode.value === value) {
        //Option 1: No right child:
        if (currentNode.right === null) {
          if (parentNode === null) {
            this.root = currentNode.left;
          } else {
            //if parent > current value, make current left child a child of parent
            if (currentNode.value < parentNode.value) {
              parentNode.left = currentNode.left;

              //if parent < current value, make left child a right child of parent
            } else if (currentNode.value > parentNode.value) {
              parentNode.right = currentNode.left;
            }
          }

          //Option 2: Right child which doesnt have a left child
        } else if (currentNode.right.left === null) {
          currentNode.right.left = currentNode.left;
          if (parentNode === null) {
            this.root = currentNode.right;
          } else {
            //if parent > current, make right child of the left the parent
            if (currentNode.value < parentNode.value) {
              parentNode.left = currentNode.right;

              //if parent < current, make right child a right child of the parent
            } else if (currentNode.value > parentNode.value) {
              parentNode.right = currentNode.right;
            }
          }

          //Option 3: Right child that has a left child
        } else {
          //find the Right child's left most child
          let leftmost = currentNode.right.left;
          let leftmostParent = currentNode.right;
          while (leftmost.left !== null) {
            leftmostParent = leftmost;
            leftmost = leftmost.left;
          }

          //Parent's left subtree is now leftmost's right subtree
          leftmostParent.left = leftmost.right;
          leftmost.left = currentNode.left;
          leftmost.right = currentNode.right;

          if (parentNode === null) {
            this.root = leftmost;
          } else {
            if (currentNode.value < parentNode.value) {
              parentNode.left = leftmost;
            } else if (currentNode.value > parentNode.value) {
              parentNode.right = leftmost;
            }
          }
        }
        return true;
      }
    }
  }
}
         

---

それぞれの操作の計算量

二分探索木におけるそれぞれの操作の計算量は以下。
探索、挿入、削除ともO(logn)で行うことができ、効率的である。ただし、ハッシュテーブルやスタック・キューなどでは、挿入や削除はO(1)で行うことができるため、用途によって使い分けが必要である。

操作	計算量
lookup	O(logn)
insert	O(logn)
delete	O(logn)

また、以下のような木構造が構成されてしまった場合、構造的には連結リストとなんら変わらない状態になり、計算量はO(n)となってしまうため、注意が必要である。以下のような木構造になることを避け、より均等にノードが配置できるようなアルゴリズムが組み込まれているデータ構造として、AVL木や赤黒木などがある。

// Unbalanced Tree
   10
    \
     20
      \
       30
        \
         40

---

参考webサイト

このUdemyの講座を参考にしています。
https://www.udemy.com/course/master-the-coding-interview-data-structures-algorithms/