09_이진탐색트리(Binary_Search_Tree).ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "자료구조_9_이진탐색트리(Binary Search Tree).ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "mount_file_id": "15qFS0pTrNlFEzRr1JzDDJSsx4Dx2e280",
      "authorship_tag": "ABX9TyMU7VhrbL09hJtdNqnjETNi",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/sejin-sim/Data_structure/blob/master/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0_9_%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89%ED%8A%B8%EB%A6%AC(Binary_Search_Tree).ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-0_o_scPOHCg",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "63e957c4-7556-475d-98bd-f32034ec325f"
      },
      "source": [
        "# 이진탐색트리_순환 in 트리\n",
        "\n",
        "class Node():\n",
        "  def __init__(self, data):\n",
        "        self.data = data\n",
        "        self.left = self.right = None\n",
        "\n",
        "  def isLeaf(self):      # 단말노드 인지 확인 T or F\n",
        "      if self.left == None and self.right == None:\n",
        "        return True\n",
        "      else: return False\n",
        "\n",
        "class BinaryTree:\n",
        "  def __init__(self):   # root 초기 값 Noe\n",
        "    self.root = None     \n",
        " \n",
        "  def setRoot(self,r):   # Root 설정\n",
        "    self.root = r          \n",
        "\n",
        "  def getCount(self, root): # 전체 노드 갯수 count\n",
        "    if root == None:        \n",
        "      return 0\n",
        "    else:\n",
        "      return self.getCount(root.left) + self.getCount(root.right) + 1  \n",
        "      # 왼쪽 + 오른쪽 + 루트까지 카운트  \n",
        "\n",
        "  def getLeafCount(self, root): # 단말 노드 갯수 count\n",
        "    if root == None:\n",
        "      return 0\n",
        "    if root.isLeaf(): # 단말 노드면 1 return\n",
        "      return 1\n",
        "    else:\n",
        "      return self.getLeafCount(root.left) + self.getLeafCount(root.right)\n",
        "\n",
        "  def getHeight(self, root):\n",
        "    if root == None:\n",
        "      return 0\n",
        "    else:\n",
        "      return max(self.getHeight(root.left), self.getHeight(root.right))+1 \n",
        "      # 왼쪽, 오른쪽 비교해서 루트까지 높이\n",
        "\n",
        "  def inorder(self, root):   # 중위 순회             \n",
        "    if root != None:\n",
        "      self.inorder(root.left)                   # 왼쪽을 다 돌고\n",
        "      print(\"[{}]\".format(root.data), end =\" \") # 루트 거치고\n",
        "      self.inorder(root.right)                  # 오른쪽 돈다.\n",
        "\n",
        "  def preorder(self, root): # 전위 순회\n",
        "    if root != None:\n",
        "      print(\"[{}]\".format(root.data), end =\" \") # 루트부터 시작\n",
        "      self.preorder(root.left)                  # 왼쪽 다 돌고\n",
        "      self.preorder(root.right)                 # 오른쪽 돈다\n",
        "\n",
        "  def postorder(self, root): # 후위 순회\n",
        "    if root != None:\n",
        "      self.postorder(root.left) # 왼쪽 다 돌고\n",
        "      self.postorder(root.right) # 오른쪽 다 돌고\n",
        "      print(\"[{}]\".format(root.data), end =\" \") # 루트 돈다.\n",
        "\n",
        "  def levelorder(self, root): # 레벨 순회\n",
        "    q = []\n",
        "    q.append(root)            # 루트부터 시작. 선입 선출\n",
        "    while q:                  # q가 있을 때 까지\n",
        "      t = q.pop(0)            # t = root를 빼서\n",
        "      if t != None:           # 만약 root가 None이 아니면, \n",
        "        print(\"[{}]\".format(t.data), end=\" \") # 루트의 데이터를 프린트\n",
        "        q.append(t.left)                      # 왼쪽을 append \n",
        "        q.append(t.right)                     # 오른쪽 append\n",
        "\n",
        "\n",
        "class BinarySearchTree(BinaryTree):\n",
        "  def __init__(self):\n",
        "    self.root = None\n",
        "    \n",
        "  def insert(self, data): # 삽입 연산\n",
        "    self.root = self._insert_value(self.root, data) \n",
        "    return self.root is not None # self.root 가 None이 아니면 return\n",
        "\n",
        "  def _insert_value(self, node, data): # 삽입 순환 연산\n",
        "   if node is None:   # 루트노드가 없으면, 노드는 신규 삽입된 노드\n",
        "     node = Node(data)\n",
        "   else:                   \n",
        "     if data < node.data: # 삽입데이터가 루트노드보다 작으면,\n",
        "      node.left = self._insert_value(node.left, data) # 루트노드의 왼쪽으로 순환\n",
        "     else:                 # 삽입데이터가 루트노드보다 크면\n",
        "      node.right = self._insert_value(node.right, data) # 로트노드의 오른쪽으로 순환\n",
        "   return node\n",
        "\n",
        "  def search(self, key):   # 탐색 연산\n",
        "    return self._search_value(self.root, key)\n",
        "\n",
        "  def _search_value(self, root, key): # 탐색 순환 연산\n",
        "   if root is None or root.data == key: # 루트가 없거나, 루트데이터= 검색데이터 라면\n",
        "     if root is not None:               # 루트가 없지 않은 경우\n",
        "      return print(\"[탐색 연산] : 성공 [{}] = {}\".format(key, root)) # 탐색 성공 & 루트 객체 반환\n",
        "     elif root is None:                 # 루트가 없는 경우\n",
        "      return print(\"[탐색 연산] : 실패: No {}!\".format(key)) # 탐색 실패\n",
        "\n",
        "   elif key < root.data: # 검색데이터 < 루트데이터\n",
        "     return self._search_value(root.left, key) # 왼쪽으로 순환검색\n",
        "   else:                 # 검색데이터 > 루트데이터\n",
        "     return self._search_value(root.right, key) # 오른쪽으로 순환검색\n",
        "\n",
        "  def remove(self, key): # 삭제 연산\n",
        "    self.root, deleted = self._delete_value(self.root, key)\n",
        "    return deleted\n",
        "\n",
        "  def _delete_value(self, node, key): # 삭제 순환 연산\n",
        "    if node is None:     # 루트가 없다면\n",
        "      return node, False # False return\n",
        "\n",
        "    deleted = False      # deleted = False 선언\n",
        "\n",
        "    if key == node.data: # 삭제할 데이터 = 루트데이터라면\n",
        "      deleted = True     # deleted = True 선언\n",
        "\n",
        "      # case 3 : 루트의 자식이 두개라면 (오른쪽 서브트리에서 제일 작은 값)\n",
        "      if node.left and node.right: \n",
        "          parent, child = node, node.right # 해당 노드와 right 자식 노드를 받음\n",
        "\n",
        "          # left 자식노드를 탐색해서 가장 작은 값을 찾음\n",
        "          # left 자식 노드의 부모 노드 값을 받아둠 (재 연결을 위한)\n",
        "          while child.left is not None:    \n",
        "            parent, child = child, child.left\n",
        "\n",
        "          # 찾을 값이 left 자식노드 값을 child의 left 자식 노드에 붙임 (=가장 작은값 왼쪽에 붙임)  \n",
        "          child.left = node.left\n",
        "\n",
        "          # key 노드의 right 노드가 바로 가장 작은 값일 때인 상황을 고려하여 넣음\n",
        "          if parent != node:\n",
        "            # 가장 작은 값 부모노드에 가장 작은 값의 right 자식노드를 left 자식노드로 붙임\n",
        "            parent.left = child.right\n",
        "            # 가장 작은 값 right 자식 노드에 key값에 right 자식노드로 붙임\n",
        "            child.right = node.right\n",
        "          node = child\n",
        "\n",
        "      # case 3 : 루트의 자식이 두개라면 (왼쪽 서브트리에서 제일 큰 값)\n",
        "      # if node.left and node.right: \n",
        "      #     parent, child = node, node.left # 해당 노드와 left 자식 노드를 받음\n",
        "\n",
        "      #     # right 자식노드를 탐색해서 가장 큰 값을 찾음\n",
        "      #     # right 자식 노드의 부모 노드 값을 받아둠 (재 연결을 위한)\n",
        "      #     while child.right is not None:    \n",
        "      #       parent, child = child, child.right\n",
        "\n",
        "      #     # 찾을 값이 right 자식노드 값을 child의 right 자식 노드에 붙임 (=가장 작은값 왼쪽에 붙임)  \n",
        "      #     child.right = node.right\n",
        "\n",
        "      #     # key 노드의 left 노드가 바로 가장 큰 값일 때인 상황을 고려하여 넣음\n",
        "      #     if parent != node:\n",
        "      #       # 가장 큰 값 부모노드에 가장 큰 값의 left 자식노드를 right 자식노드로 붙임\n",
        "      #       parent.right = child.left\n",
        "      #       # 가장 큰 값 left 자식 노드에 key값에 left 자식노드로 붙임\n",
        "      #       child.left = node.left\n",
        "      #     node = child\n",
        "\n",
        "      # case 2 : 루트 자식이 한개라면\n",
        "      elif node.left or node.right:\n",
        "        # 자식 노드를 그대로 끌어다 놓음\n",
        "        node = node.left or node.right\n",
        "      \n",
        "      # case 1: 자식 노드가 없는 경우\n",
        "      else:                         \n",
        "        # 해당 값 삭제\n",
        "        node = None\n",
        "\n",
        "    # key 값이 작으면 왼쪽 순환\n",
        "    elif key < node.data: # 삭제할 데이터 < 루트데이터라면\n",
        "      node.left, deleted = self._delete_value(node.left, key) # 왼쪽으로 순환\n",
        "\n",
        "    # key 값이 크면 오른쪽 순환\n",
        "    else:       \n",
        "      node.right, deleted = self._delete_value(node.right, key) # 오른쪽으로 순환\n",
        "\n",
        "    return node, deleted\n",
        "\n",
        "\n",
        "tree = BinarySearchTree()\n",
        "\n",
        "print(\"[삽입 연산] : 35 18 7 26 12 3 68 22 30 99\")\n",
        "tree.insert(35)\n",
        "tree.insert(18)\n",
        "tree.insert(7)\n",
        "tree.insert(26)\n",
        "tree.insert(12)\n",
        "tree.insert(3)\n",
        "tree.insert(68)\n",
        "tree.insert(22)\n",
        "tree.insert(30)\n",
        "tree.insert(99)\n",
        "\n",
        "print(\"In-Order :    \", end=\" \")\n",
        "tree.inorder(tree.root)\n",
        "print(\"\\nPre-Order :   \", end=\" \")\n",
        "tree.preorder(tree.root)\n",
        "print(\"\\nPost-Order :  \", end=\" \")\n",
        "tree.postorder(tree.root)\n",
        "print(\"\\nLevel-Order : \", end=\" \")\n",
        "tree.levelorder(tree.root)\n",
        "\n",
        "print(\"\\n노드의 갯수 =\", tree.getCount(tree.root))\n",
        "print(\"단말의 갯수 =\", tree.getLeafCount(tree.root))\n",
        "print(\"트리의 높이 =\", tree.getHeight(tree.root))\n",
        "\n",
        "tree.search(26)\n",
        "tree.search(25)\n",
        "\n",
        "print(\"\\noriginal bintree: LevelOrder: \", end=\" \")\n",
        "tree.levelorder(tree.root)\n",
        "tree.remove(3)\n",
        "print(\"\\ncase1: < 3> 삭제: LevelOrder: \", end=\" \")\n",
        "tree.levelorder(tree.root)\n",
        "tree.remove(68)\n",
        "print(\"\\ncase2: <68> 삭제: LevelOrder: \", end=\" \")\n",
        "tree.levelorder(tree.root)\n",
        "tree.remove(18)\n",
        "print(\"\\ncase3: <18> 삭제: LevelOrder: \", end=\" \")\n",
        "tree.levelorder(tree.root)\n",
        "tree.remove(35)\n",
        "print(\"\\ncase3: <35> 삭제: LevelOrder: \", end=\" \")\n",
        "tree.levelorder(tree.root)\n",
        "\n",
        "print(\"\\n노드의 갯수 =\", tree.getCount(tree.root))\n",
        "print(\"단말의 갯수 =\", tree.getLeafCount(tree.root))\n",
        "print(\"트리의 높이 =\", tree.getHeight(tree.root))\n"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[삽입 연산] : 35 18 7 26 12 3 68 22 30 99\n",
            "In-Order :     [3] [7] [12] [18] [22] [26] [30] [35] [68] [99] \n",
            "Pre-Order :    [35] [18] [7] [3] [12] [26] [22] [30] [68] [99] \n",
            "Post-Order :   [3] [12] [7] [22] [30] [26] [18] [99] [68] [35] \n",
            "Level-Order :  [35] [18] [68] [7] [26] [99] [3] [12] [22] [30] \n",
            "노드의 갯수 = 10\n",
            "단말의 갯수 = 5\n",
            "트리의 높이 = 4\n",
            "[탐색 연산] : 성공 [26] = <__main__.Node object at 0x7fd394f45278>\n",
            "[탐색 연산] : 실패: No 25!\n",
            "\n",
            "original bintree: LevelOrder:  [35] [18] [68] [7] [26] [99] [3] [12] [22] [30] \n",
            "case1: < 3> 삭제: LevelOrder:  [35] [18] [68] [7] [26] [99] [12] [22] [30] \n",
            "case2: <68> 삭제: LevelOrder:  [35] [18] [99] [7] [26] [12] [22] [30] \n",
            "case3: <18> 삭제: LevelOrder:  [35] [22] [99] [7] [26] [12] [30] \n",
            "case3: <35> 삭제: LevelOrder:  [99] [22] [7] [26] [12] [30] \n",
            "노드의 갯수 = 6\n",
            "단말의 갯수 = 2\n",
            "트리의 높이 = 4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "or1G-6ck_AUN",
        "outputId": "2ede07e7-f12e-43bd-f65b-5d68fe01fd58"
      },
      "source": [
        "# Q3.\n",
        "\n",
        "tree = BinarySearchTree()\n",
        "\n",
        "tree.insert(5)\n",
        "tree.insert(7)\n",
        "tree.insert(2)\n",
        "tree.insert(8)\n",
        "tree.insert(3)\n",
        "tree.remove(3)\n",
        "\n",
        "tree.insert(4)\n",
        "tree.insert(3)\n",
        "\n",
        "tree.remove(7)\n",
        "tree.remove(5)\n",
        "print(\"original binTree : LevelOrder : \", end=\" \")\n",
        "tree.levelorder(tree.root)\n",
        "print(\"\\n트리의 높이 =\", tree.getHeight(tree.root))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "original binTree : LevelOrder :  [8] [2] [4] [3] \n",
            "트리의 높이 = 4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WLaLXf1N8Mgf",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9478ccc5-29f4-4212-d37c-61b88a3c402d"
      },
      "source": [
        "# C9.\n",
        "\n",
        "class Node():\n",
        "  def __init__(self, data):\n",
        "        self.data = data\n",
        "        self.left = self.right = None\n",
        "\n",
        "  def isLeaf(self):      # 단말노드 인지 확인 T or F\n",
        "      if self.left == None and self.right == None:\n",
        "        return True\n",
        "      else: return False\n",
        "\n",
        "class BinaryTree:\n",
        "  def __init__(self):   # root 초기 값 Noe\n",
        "    self.root = None     \n",
        " \n",
        "  def setRoot(self,r):   # Root 설정\n",
        "    self.root = r          \n",
        "\n",
        "  def getCount(self, root): # 전체 노드 갯수 count\n",
        "    if root == None:        \n",
        "      return 0\n",
        "    else:\n",
        "      return self.getCount(root.left) + self.getCount(root.right) + 1  \n",
        "      # 왼쪽 + 오른쪽 + 루트까지 카운트  \n",
        "\n",
        "  def getLeafCount(self, root): # 단말 노드 갯수 count\n",
        "    if root == None:\n",
        "      return 0\n",
        "    if root.isLeaf(): # 단말 노드면 1 return\n",
        "      return 1\n",
        "    else:\n",
        "      return self.getLeafCount(root.left) + self.getLeafCount(root.right)\n",
        "\n",
        "  def getHeight(self, root):\n",
        "    if root == None:\n",
        "      return 0\n",
        "    else:\n",
        "      return max(self.getHeight(root.left), self.getHeight(root.right))+1 \n",
        "      # 왼쪽, 오른쪽 비교해서 루트까지 높이\n",
        "\n",
        "  def inorder(self, root):   # 중위 순회             \n",
        "    if root != None:\n",
        "      self.inorder(root.left)                   # 왼쪽을 다 돌고\n",
        "      print(\"[{}]\".format(root.data), end =\" \") # 루트 거치고\n",
        "      self.inorder(root.right)                  # 오른쪽 돈다.\n",
        "\n",
        "  def preorder(self, root): # 전위 순회\n",
        "    if root != None:\n",
        "      print(\"[{}]\".format(root.data), end =\" \") # 루트부터 시작\n",
        "      self.preorder(root.left)                  # 왼쪽 다 돌고\n",
        "      self.preorder(root.right)                 # 오른쪽 돈다\n",
        "\n",
        "  def postorder(self, root): # 후위 순회\n",
        "    if root != None:\n",
        "      self.postorder(root.left) # 왼쪽 다 돌고\n",
        "      self.postorder(root.right) # 오른쪽 다 돌고\n",
        "      print(\"[{}]\".format(root.data), end =\" \") # 루트 돈다.\n",
        "\n",
        "  def levelorder(self, root): # 레벨 순회\n",
        "    q = []\n",
        "    q.append(root)            # 루트부터 시작. 선입 선출\n",
        "    while q:                  # q가 있을 때 까지\n",
        "      t = q.pop(0)            # t = root를 빼서\n",
        "      if t != None:           # 만약 root가 None이 아니면, \n",
        "        print(\"[{}]\".format(t.data), end=\" \") # 루트의 데이터를 프린트\n",
        "        q.append(t.left)                      # 왼쪽을 append \n",
        "        q.append(t.right)                     # 오른쪽 append\n",
        "\n",
        "\n",
        "class BinarySearchTree(BinaryTree):\n",
        "  def __init__(self):\n",
        "    self.root = None\n",
        "    \n",
        "  def insert(self, data):\n",
        "    self.root = self._insert_value(self.root, data) \n",
        "    return self.root is not None # self.root 가 None이 아니면 return\n",
        "\n",
        "  def _insert_value(self, node, data):\n",
        "   if node is None:\n",
        "     node = Node(data)\n",
        "   else:\n",
        "     if data <= node.data:\n",
        "      node.left = self._insert_value(node.left, data)\n",
        "     else:\n",
        "      node.right = self._insert_value(node.right, data)\n",
        "   return node\n",
        "\n",
        "  def search(self, key):\n",
        "    return self._search_value(self.root, key)\n",
        "\n",
        "  def _search_value(self, root, key): # 순환적 탐색으로 반복적 일반 함수 구현 필요\n",
        "   if root is None or root.data == key: \n",
        "     if root is not None:\n",
        "      return print(\"[탐색 연산] : 성공 [{}] = {}\".format(key, root))\n",
        "     elif root is None:\n",
        "      return print(\"[탐색 연산] : 실패: No {}!\".format(key))\n",
        "\n",
        "   elif key < root.data:\n",
        "     return self._search_value(root.left, key)\n",
        "   else:\n",
        "     return self._search_value(root.right, key)\n",
        "\n",
        "  def remove(self, key):\n",
        "    self.root, deleted = self._delete_value(self.root, key)\n",
        "    return deleted\n",
        "\n",
        "  def _delete_value(self, node, key):\n",
        "    if node is None:\n",
        "      return node, False\n",
        "\n",
        "    deleted = False\n",
        "\n",
        "    if key == node.data:\n",
        "      deleted = True\n",
        "\n",
        "      if node.left and node.right:\n",
        "          parent, child = node, node.right\n",
        "          while child.left is not None:\n",
        "            parent, child = child, child.left\n",
        "          child.left = node.left\n",
        "          if parent != node:\n",
        "            parent.left = child.right\n",
        "            child.right = node.right\n",
        "          node = child\n",
        "      elif node.left or node.right:\n",
        "        node = node.left or node.right\n",
        "      else:\n",
        "        node = None\n",
        "    elif key < node.data:\n",
        "      node.left, deleted = self._delete_value(node.left, key)\n",
        "    else:\n",
        "      node.right, deleted = self._delete_value(node.right, key)\n",
        "    return node, deleted\n",
        "\n",
        "\n",
        "tree = BinarySearchTree()\n",
        "\n",
        "tree.insert(5)\n",
        "tree.insert(3)\n",
        "tree.insert(9)\n",
        "tree.insert(1)\n",
        "tree.insert(4)\n",
        "tree.insert(7)\n",
        "tree.insert(2)\n",
        "tree.insert(6)\n",
        "tree.insert(8)\n",
        "\n",
        "print(\"original binTree : LevelOrder : \", end=\" \")\n",
        "tree.levelorder(tree.root)\n",
        "tree.remove(9)\n",
        "print(\"\\n<9> 삭제 : LevelOrder : \", end=\" \")\n",
        "tree.levelorder(tree.root)\n",
        "\n",
        "print(\"\\n노드의 갯수 =\", tree.getCount(tree.root))\n",
        "print(\"단말의 갯수 =\", tree.getLeafCount(tree.root))\n",
        "print(\"트리의 높이 =\", tree.getHeight(tree.root))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "original binTree : LevelOrder :  [5] [3] [9] [1] [4] [7] [2] [6] [8] \n",
            "<9> 삭제 : LevelOrder :  [5] [3] [7] [1] [4] [6] [8] [2] \n",
            "노드의 갯수 = 8\n",
            "단말의 갯수 = 4\n",
            "트리의 높이 = 4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "o4VxyecKKk8k",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 175
        },
        "outputId": "7722113e-4468-4e57-c5db-fa5f3ac71278"
      },
      "source": [
        "# BST another ver.\n",
        "\n",
        "\"\"\"\n",
        "다음 그림의 이진 탐색 트리를 구현한다.\n",
        "                              6           ---> 레벨 1\n",
        "                        4           8     ---> 레벨 2\n",
        "                     2     5     7     9  ---> 레벨 3\n",
        "                  1     3                 ---> 레벨 4\n",
        "    속성은 다음과 같다.\n",
        "        - 노드의 개수(크기): n = 9\n",
        "        - 분기(또는 내부 노드) 수: b = n-1 = 8\n",
        "        - 루트 노드: 6\n",
        "        - 최대 깊이 또는 높이: h = 3\n",
        "        - 균형 트리입니까? YES\n",
        "        - 이진 탐색 트리입니까? YES\n",
        "\"\"\"\n",
        "class Height(object):\n",
        "    def __init__(self):\n",
        "        self.height = 0\n",
        "\n",
        "\n",
        "class NodeBT(object):\n",
        "    def __init__(self, value=None, level=1):\n",
        "        self.value = value\n",
        "        self.level = level\n",
        "        self.left = None\n",
        "        self.right = None\n",
        "\n",
        "    def __repr__(self):\n",
        "        return \"{}\".format(self.value)\n",
        "\n",
        "    def _add_next_node(self, value, level_here=2):\n",
        "        new_node = NodeBT(value, level_here)\n",
        "        if not self.value:\n",
        "            self.value = new_node\n",
        "        elif not self.left:\n",
        "            self.left = new_node\n",
        "        elif not self.right:\n",
        "            self.right = new_node\n",
        "        else:\n",
        "            # 노드에 왼쪽 오른쪽 자식이 모두 있다면,\n",
        "            # 왼쪽 자식 노드에 새 노드를 추가한다.\n",
        "            # 그래서 예제의 트리가 왼쪽으로 치우쳐 있다.\n",
        "            self.left = self.left._add_next_node(value, level_here+1)\n",
        "        return self\n",
        "\n",
        "    def _search_for_node(self, value):\n",
        "        # 전위 순회(pre-order)로 값을 찾는다.\n",
        "        if self.value == value:\n",
        "            return self\n",
        "        else:\n",
        "            found = None\n",
        "            if self.left:\n",
        "                found = self.left._search_for_node(value)\n",
        "            if self.right:\n",
        "                found = found or self.right._search_for_node(value)\n",
        "            return found\n",
        "\n",
        "    def _is_leaf(self):\n",
        "        # 왼쪽, 오른쪽 자식이 모두 없는 노드\n",
        "        return not self.right and not self.left\n",
        "\n",
        "    def _get_max_height(self):\n",
        "        # 노드에서 최대 높이를 얻는다 - O(n)\n",
        "        heightr, heightl = 0, 0\n",
        "        if self.right:\n",
        "            heightr = self.right._get_max_height() + 1\n",
        "        if self.left:\n",
        "            heightl = self.left._get_max_height() + 1\n",
        "        return max(heightr, heightl)\n",
        "\n",
        "    def _is_balanced(self, height=Height()):\n",
        "        # 균형 트리인지 확인한다 - O(n)\n",
        "        lh = Height()\n",
        "        rh = Height()\n",
        "\n",
        "        if self.value is None:\n",
        "            return True\n",
        "\n",
        "        l, r = True, True\n",
        "        if self.left:\n",
        "            l = self.left._is_balanced(lh)\n",
        "        if self.right:\n",
        "            r = self.right._is_balanced(rh)\n",
        "\n",
        "        height.height = max(lh.height, rh.height) + 1\n",
        "\n",
        "        if abs(lh.height - rh.height) <= 1:\n",
        "            return l and r\n",
        "\n",
        "        return False\n",
        "\n",
        "    def _is_bst(self, left=None, right=None):\n",
        "        # 이진 탐색 트리인지 확인한다 - O(n)\n",
        "        if self.value:\n",
        "            if left and self.value < left:\n",
        "                return False\n",
        "            if right and self.value > right:\n",
        "                return False\n",
        "\n",
        "            l, r = True, True\n",
        "            if self.left:\n",
        "                l = self.left._is_bst(left, self.value)\n",
        "            if self.right:\n",
        "                r = self.right._is_bst(self.value, right)\n",
        "            return l and r\n",
        "        else:\n",
        "            return True\n",
        "\n",
        "\n",
        "class BinaryTree(object):\n",
        "    def __init__(self):\n",
        "        self.root = None\n",
        "\n",
        "    def add_node(self, value):\n",
        "        if not self.root:\n",
        "            self.root = NodeBT(value)\n",
        "        else:\n",
        "            self.root._add_next_node(value)\n",
        "\n",
        "    def is_leaf(self, value):\n",
        "        node = self.root._search_for_node(value)\n",
        "        if node:\n",
        "            return node._is_leaf()\n",
        "        else:\n",
        "            return False\n",
        "\n",
        "    def get_node_level(self, value):\n",
        "        node = self.root._search_for_node(value)\n",
        "        if node:\n",
        "            return node.level\n",
        "        else:\n",
        "            return False\n",
        "\n",
        "    def is_root(self, value):\n",
        "        return self.root.value == value\n",
        "\n",
        "    def get_height(self):\n",
        "        return self.root._get_max_height()\n",
        "\n",
        "    def is_balanced(self):\n",
        "        return self.root._is_balanced()\n",
        "\n",
        "    def is_bst(self):\n",
        "        return self.root._is_bst()\n",
        "\n",
        "class NodeBST(NodeBT):\n",
        "\n",
        "    def __init__(self, value=None, level=1):\n",
        "        self.value = value\n",
        "        self.level = level\n",
        "        self.left = None\n",
        "        self.right = None\n",
        "\n",
        "    def _add_next_node(self, value, level_here=2):\n",
        "        new_node = NodeBST(value, level_here)\n",
        "        if value > self.value:\n",
        "            self.right = self.right and self.right._add_next_node(\n",
        "                value, level_here + 1) or new_node\n",
        "        elif value < self.value:\n",
        "            self.left = self.left and self.left._add_next_node(\n",
        "                value, level_here + 1) or new_node\n",
        "        else:\n",
        "            print(\"중복 노드를 허용하지 않습니다.\")\n",
        "        return self\n",
        "\n",
        "    def _search_for_node(self, value):\n",
        "        if self.value == value:\n",
        "            return self\n",
        "        elif self.left and value < self.value:\n",
        "            return self.left._search_for_node(value)\n",
        "        elif self.right and value > self.value:\n",
        "            return self.right._search_for_node(value)\n",
        "        else:\n",
        "            return False\n",
        "\n",
        "\n",
        "class BinarySearchTree(BinaryTree):\n",
        "    def __init__(self):\n",
        "        self.root = None\n",
        "\n",
        "    def add_node(self, value):\n",
        "        if not self.root:\n",
        "            self.root = NodeBST(value)\n",
        "        else:\n",
        "            self.root._add_next_node(value)\n",
        "\n",
        "\n",
        "if __name__ == \"__main__\":\n",
        "    bst = BinarySearchTree()\n",
        "    # for i in range(1, 10):\n",
        "    for i in [6, 4, 8, 2, 5, 7, 9, 1, 3]:\n",
        "        bst.add_node(i)\n",
        "    print(\"노드 8은 말단 노드입니까? \", bst.is_leaf(8))\n",
        "    print(\"노드 1의 레벨은? \", bst.get_node_level(1))\n",
        "    print(\"노드 10은 루트 노드입니까? \", bst.is_root(10))\n",
        "    print(\"노드 1은 루트 노드입니까? \", bst.is_root(1))\n",
        "    print(\"트리의 높이는? \", bst.get_height())\n",
        "    print(\"이진 탐색 트리입니까? \", bst.is_bst())\n",
        "    print(\"균형 트리입니까? \", bst.is_balanced())\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "노드 8은 말단 노드입니까?  False\n",
            "노드 1의 레벨은?  4\n",
            "노드 10은 루트 노드입니까?  False\n",
            "노드 1은 루트 노드입니까?  False\n",
            "트리의 높이는?  3\n",
            "이진 탐색 트리입니까?  True\n",
            "균형 트리입니까?  True\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'\\n다음 그림의 이진 탐색 트리를 구현한다.\\n                              6           ---> 레벨 1\\n                        4           8     ---> 레벨 2\\n                     2     5     7     9  ---> 레벨 3\\n                  1     3                 ---> 레벨 4\\n    속성은 다음과 같다.\\n        - 노드의 개수(크기): n = 9\\n        - 분기(또는 내부 노드) 수: b = n-1 = 8\\n        - 루트 노드: 6\\n        - 최대 깊이 또는 높이: h = 3\\n        - 균형 트리입니까? YES\\n        - 이진 탐색 트리입니까? YES\\n'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 20
        }
      ]
    }
  ]
}