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;
             }
         }