---
tags: algorithm
---

# 二元搜尋樹

## 原理

讓每一個節的的右邊的值都是大於他的，左邊則是小於

digraph main {
    k
    k -> "<k"
    k -> ">=k"
}

通常用指標實作，因為不知道層數，如果用陣列開的話會很慘

## 節點

如上文所述，可知一個節點必須要有兩個指標，一個指向大於他的節點，另一個指向小於他的節點

struct node {
    node *l, *r;
    int val;
    node(int k) :　val(k){l = r = nullptr;}
}

## 操作

### 插入
`void insert(int val, node *& cur)`
加參照的原因是因為會有新的節點加入。

void insert(node *& cur, int k) {
    if(!cur) {cur = new ndoe(k); return;}
    if(k < cur -> val) {
        insert(cur -> l, k);
    }
    else {
        insert(cur -> r, k);
    }
}

:::spoiler 實作注意
要記得return
:::

---

### 查詢
查詢一個值是否存在於這個二元樹裡面
`bool qry(node *cur, int k)`

bool qry(node *cur, int k) {
    if(!cur) return false;
    
    if(k < cur -> val) {
        qry(cur -> l, k);
    }
    else if(k > cur -> val) {
        qry(cur -> r, k);
    }
    else return true;
}

:::spoiler 實作注意
一樣要記得return
:::

---

### 時間複雜度
***插入*** : 平均複雜度$O(\log N)$, 最壞複雜度$O(N)$
***查詢*** : 平均複雜度$O(\log N)$, 最壞複雜度$O(N)$

:::spoiler complete code

struct BST {
	struct node {
		node *l, *r;
		int val;
		node (int k) : val(k) {l = r = nullptr;}
	}*root = nullptr;
	
	//插入
	void insert(node *& cur, int k) {
		if(!cur) {cur = new node(k); return;}
		if(k >= cur -> val) {
			insert(cur -> r, k); 
		}
		else insert(cur -> l, k);
	}
	void insert(int k) {insert(root, k);}

	//查詢
	bool qry(node *cur, int k) {
		if(!cur) return false;

		if(k < cur -> val) {
			qry(cur -> l, k);
		}
		else if(k > cur -> val) {
			qry(cur -> r, k);
		}	
		else return true;
	}
	bool qry(int k) {return qry(root, k);}


	
	//印出　（升序）
	void out(node *cur) {
		if(!cur) return;
		out(cur -> l);
		cout << cur -> val << ' ';
		out(cur -> r);

	}
	void out() {out(root); cout << endl;}


};