yuzh的博客

❤ ECUST ❤

0%

二叉查找树

发表于 Valine：

基本实现

节点定义

1
2
3
4
5
6
struct Node
{
	int val; //Öµ 
	Node *lefttree,*righttree;//×ó×ÓÊ÷£¬ÓÒ×ÓÊ÷
};
Node *root=NULL;

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
void insert(Node *&node, int val)
{
	if(node==NULL)
	{
		node = new Node;
		node->val=val;
		node->lefttree = node->righttree = NULL;
        return;
	}
	if(node->val==val) return;
	else if(node->val>val) insert(node->lefttree, val);
	else insert(node->righttree, val);
}

查找

1
2
3
4
5
6
7
bool search(Node *&node, int val)
{
	if(node==NULL) return false;
	if(node->val==val) return true;
	else if(node->val>val) search(node->lefttree, val);
	else search(node->righttree, val);
}

获取最大值节点和最小值节点

1
2
3
4
5
6
7
8
9
10
11
12
13
Node *max(Node *&node)
{
	if(node==NULL) return NULL;
	if(node->righttree==NULL) return node;
	else return(max(node->righttree));
}

Node *min(Node *&node)
{
	if(node==NULL) return NULL;
	if(node->lefttree==NULL) return node;
	else return(max(node->lefttree));
}

删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void del(Node *&node, int val)
{
	if(node==NULL) return;
	if(node->val==val)
	{
		if(node->lefttree==NULL && node->righttree==NULL) node=NULL;
		else if(node->lefttree!=NULL)
		{
			Node *pre=max(node->lefttree);
			node->val=pre->val;
			del(node->lefttree, pre->val);
		}
		else if(node->righttree!=NULL)
		{
			Node *aft=min(node->righttree);
			node->val=aft->val;
			del(node->righttree, aft->val);
		}
	}
	else if(node->val>val) del(node->lefttree, val);
	else del(node->righttree, val);
}

使用样例

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
	insert(root, 1);
	insert(root,3);
	insert(root,4);
	insert(root,2);
	//cout<<root->righttree->val;
	//cout<<search(root,3);
	del(root,4);
	cout<<max(root)->val;
	cout<<min(root)->val;
	return 0;
}

性能分析

最优情况下：二叉搜索树为完全二叉树（或者接近完全二叉树），其平均比较次数为：log(N)。

最差情况下：二叉搜索树退化为单支树（或者类似单支），其平均比较次数为 N。

因此，需要使用平衡二叉树来确保查找、插入和删除的时间复杂度为O(log n)。