树与树的表示

0x00 什么是树

很多事物存在层次关系比如人类社会家谱关系，社会组织结构，文件目录关系。

为什么使用分层次组织，因为在管理上更高效，比如查找，线性管理的时间复杂度必然是O(n),而二分查找是O(logn)，而我们观察二分查找，实际上是一种树状的判定。

查找分为静态查找和动态查找（前者中的记录是固定的，后者还可以做插入删除操作）

TIM截图20200203130735

二分查找的代码实现：

int binary_search(int*data,int size,int x){
		int ret=-1;
		int l=0;
		int r=size-1;
		int mid;
		while(r>=l){
			mid=(l+r)/2;
			if(x>data[mid]){
				l=mid+1;
			}else if(x<data[mid]){
				r=mid-1; 
			} else{
				ret=mid;
				break;
			}
		}	
		return ret;	
	}