二叉搜索树

BST(BinarySearchTree,二叉搜索树)是非常有用的数据结构它的结构精巧访问高效.BST的特征如下:

(1) 每个元素有唯一的键值,这些键值能比较大小.通常把键值存放在BST的结点上.

(2) 任意一个结点的键值,比它左子树的所有结点的键值大,比它右子树的所有结点的键值小.也就是说,在BST上,以任意结点为根结点的一棵子树仍然是BST.BST是一棵有序的二叉树.可以推出,键值最大的结点没有右儿子,键值最小的结点没有左儿子.

下图是一棵二叉搜索树,用中序遍历可以得到它的有序排列.右图的虚线把每个结点隔开,很容易看出,结点正好按从小到大的顺序被虚线隔开了.有虚线的帮助,很容易理解后文介绍树和树时提到的旋转技术

数据的基本操作是插人、查询、删除。给定一个数据序列，如何实现BST?下面给出种朴素的实现方法。

(1) 建树和插入。以第 1个数据 为根结点，逐个插入其他所有数据。插入过程从根结点开始，如果数据 y 比根结点 小，就往的左子树上插，否则就往右子树上插;如果子树为空，就直接放到这个空位，如果非空，就与子树的值进行比较，再进入子树的下一层，直到找到一个空位置。新插入的数据肯定位于一个最底层的叶子结点，而不是插到中间某个结点上替代原来的数据。

从建树的过程可知，如果按给定序列的顺序进行插入，最后建成的 BST 是唯一的。形成的 BST可能很好，也可能很坏。在最坏的情况下，例如一列有序整数{1，2，3，4，5，6，7}，按顺序插人，会全部插到右子树上: BST 退化成一个只包含右子树的链表，从根结点到最底层的叶子，深度是n，导致访问一个结点的复杂度是 $O(n)$。在最好的情况下，例如序列{4，2，1，3，6，5，7}，得到的 BST 左、右子树是完全平衡的，深度是 $log_2n$，访问复杂度是 $O(log_2n)$。退化的 BST 和平衡 BST 如下图所示。

(２)查询。建树过程实际上也是一个查询过程，所以查询仍然是从根结点开始的递归过程。访问的复杂度取决于的形态.

(３)删除。在删除一个结点x后，剩下的部分应该仍然是一个BST。首先找到被删结点x，如果x是最底层的叶子结点，直接删除；如果x只有左子树L或者只有右子树R，直接删除x，原位置由L或R代替。如果x左、右子树都有，情况就复杂了，此时，原来以x为根结点的子树需要重新建树。一种做法是，搜索x左子树中的最大元素y，移动到x的位置，这相当于原来以y为根结点的子树，删除了y，然后继续对y的左子树进行类似的操作，这也是一个递归的过程。删除操作的复杂度也取决于BST的形态.

(４)遍历。在5.2.2节中提到用中序遍历BST，返回的是一个从小到大的排序。根据上述过程可知，BST的优劣取决于它是否为一个平衡的二叉树。所以，BST有关算法的主要功能是努力使它保持平衡。那么如何实现一个平衡的BST?由于无法提前安排元素的顺序(如果能一次读入所有元素，也能调整顺序，但是会大费周章，没有必要),所以只能在建树之后通过动态调整使它变得平衡。BST算法的区别就在于用什么办法调整.

BST算法有AVL树、红黑树、Splay树、Treap树、SBT树等。其中容易编程的有Splay树、树等，也是算法竞赛中容易出的题目，本节后续讲解树和树。

BST是一个动态维护的有序数据集，用DFS对它进行中序遍历可以高效地输出字典序、查找第k大的数等。

STL与BST。STL中的set和map是用二叉搜索树(红黑树)实现的，检索和更新的复杂度是O(logn)。如果一个题目需要快速访问集合中的数据，可以用set或map实现。

【习题】 hdu3999 “The order of a Tree”, 模拟BST的建树和访问. hdu3791 “二叉搜索树”, 模拟BST. poj2418 “Hardwood Species”, 用map快速处理字符串.

【习题】hdu 3999 The order of a Tree

#include<cstdio>
    #include<iostream>
    using namespace std;
    struct node{
    	int value;
    	node *l,*r;
    	node(int value=0,node *l=NULL,node *r=NULL):value(value),l(l),r(r){};
    };
    //构建BST(Binary Search Tree)
    void create(int t,node *&root){
    	if(!root) root=new node(t);
    	else if(t < root->value) create(t,root->l);
    	else create(t,root->r);
    }
    //先序遍历
    void preorder(node *root){
    	if(root){
    		printf("%d ",root->value);
    		preorder(root->l);
    		preorder(root->r);
    	}
    }
    int main(void){
    	int n,t;
    	while(~scanf("%d",&n)){
    		node *root=NULL;
    		for(int i=0;i<n;i++) scanf("%d",&t),create(t,root);
    		preorder(root);
    		printf("\n");
    	}
    	return 0;
    }

【习题】hdu3791 二叉搜索树

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=15;
int k;
char a[N],b[N],c[N];
struct node{
	int value;
	node *l,*r;
	node(int value='0',node *l=NULL,node *r=NULL):value(value),l(l),r(r){};
};

void create(int t,node *&root){
	if(!root) root=new node(t);
	else if(t< root->value) create(t,root->l);
	else create(t,root->r);
}

void preorder(char a[],node *root){
	if(root){
		a[k++]=root->value+'0';
		preorder(a,root->l);
		preorder(a,root->r);
	}
}

void remove_tree(node *root){
	if(!root) return;
	remove_tree(root->l);
	remove_tree(root->r);
	delete root;
}

int main(void){
	int n;
	while(scanf("%d",&n)){
		if(n==0) break;
		node *root=NULL;
		scanf("%s",a);
		for(int i=0;a[i]!='\0';i++) create(a[i]-'0',root);
		k=0;
		preorder(b,root);
		b[k]='\0';
		while(n--){
			node *root2=NULL;
			scanf("%s",a);
			for(int i=0;a[i]!='\0';i++) create(a[i]-'0',root2);
			k=0;
			preorder(c,root2);
			c[k]='\0';
			if(strcmp(b,c)==0) cout<<"YES\n";
			else cout<<"No\n";
			remove_tree(root2);
		}
		remove_tree(root);
	}
	return 0;
}

poj2418 Hardwood Species

#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
using namespace std;

int main(void){
	//freopen("a.in","r",stdin);
	map<string,int> mp;
	int cnt=0;
	string s;
	while(getline(cin,s)){
		mp[s]++;
		cnt++;
	}
	//提交poj版本不支持c++11
	//需要用map<string,int>::iterator替代auto
	for(auto it=mp.begin();it!=mp.end();it++){
		cout<<it->first<<" ";
		printf("%.4f\n" , 100.0*(it->second)/cnt);
	}
	return 0;
}