# Binary search tree

## 1.特 性

* L < V < R (Inoder traversal)
* 執行查找, 刪除, 插入等操作的時間複雜度為O(log n)
  * 一個由N個節點組成, 隨機構造的BST其高度為logN
  * 但是一棵具有N個節點的線性鏈, 則此操作最壞情況運行時間為O(N)

## 2.操作

* Search

```
TreeNode* BST::Search(int KEY){
           TreeNode *current = root;               // 將curent指向root作為traversal起點
           while (current != NULL && KEY != current->key) {
           // 兩種情況跳出迴圈：
           // 1.沒找到 2.有找到
           if (KEY < current->key{
               current = current->leftchild;   // 向左走
           } else {
               current = current->rightchild;  // 向右走
           }
       }
       return current;
   }
```

* Insert

```
void BST::InsertBST(int key, string element){
              TreeNode *y = 0;        // 準新手爸媽
              TreeNode *x = 0;        // 哨兵
              TreeNode *insert_node = new TreeNode(key, element);   // insert_node為將要新增的node
              x = root;
              while (x != NULL) {                 // 在while中, 以如同Search()的方式尋找適當的位置
                  y = x;                          // y先更新到原來x的位置
                  if (insert_node->key < x->key){ // 判斷x是要往left- 還是right- 前進
                      x = x->leftchild;
                  }else{
                      x = x->rightchild;
                  }
              }                                   // 跳出迴圈後, x即為NULL
              // y即為insert_node的parent
              insert_node->parent = y;            // 將insert_node的parent pointer指向y
              if (y == NULL){                     // 下面一組if-else, 把insert_node接上BST
                  this->root = insert_node;
              } else if (insert_node->key < y->key){
                  y->leftchild = insert_node;
              } else{
                 y->rightchild = insert_node;
             }
         }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/notes-of-algorithms/binary-search-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.