STL源代码-二叉树搜索树

为了进一步了解RB树二叉排序树查找 算法，首先要了解二叉搜索树

二进制搜索树是二进制树，因此可以使用链结构存储数据. 如果二进制搜索树不为空，则它应具有以下属性:

键值是唯一的. 如果左子树不为空，则子树的任何节点的键值必须小于其根节点的键值. 如果右侧子树不为空，则该子树中任何节点的键值都必须为. 大于或等于其根节点的键值的左右子树仍为二叉搜索树

查找节点:

如果二进制搜索树为空，则搜索失败. 如果树不为空并且搜索数据x等于根节点的值，则搜索成功，并返回根节点. 如果树不为空并且搜索数据x小于根节点的值，则搜索左子树直到值相等，然后返回该节点. 如果树不为空并且搜索数据x大于根节点的值，则搜索右子树直到值相等，然后返回该节点

插入节点:

如果二进制搜索树为空，则将该节点插入为根节点. 如果插入的节点关键字值等于根节点值，则插入失败，如果插入的节点关键字值小于根节点值二叉排序树查找 算法，则返回，然后将该节点插入到左子树中. 如果插入节点的键值大于根节点的值，则该节点将插入到右子树中

删除节点:

如果p节点是叶节点，请删除该叶节点并修改其父节点的指针. 如果p节点仅具有左子树PL或右子树PR，则只需使PL或PR直接成为其父节点的左子树（当p是左子树时）或右子树（当p是右子树时） ）树）. p节点的左右子树不为空. 找到节点p的后继节点y（必须在节点p的右子树中），并使用右子树中的最小数作为后继节点.

以下是实现这些功能的程序

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define LENGTH 11
struct BinSearNode
{
	int key;
	struct BinSearNode *left_child;
	struct BinSearNode *right_child;
	struct BinSearNode *parent;
}Node;
typedef struct BinSearNode *PNode;
/*Search the node of the tree*/
PNode Search_Tree(PNode root,int key)
{
	PNode x=root;
	//the tree is not empty and the key is not equal
	while(NULL!=x && x->key!=key)
	{
		if(x->key<key)
			x=x->right_child;//along the right child of tree,until it is empty
		else
			x=x->left_child;//along the left child of tree,until it is empty
	}
	return x;//return the node
}
/*the minimum key of node in the tree*/
PNode Minimum_Tree(PNode root)
{
	PNode x=root;
	while(NULL!=x->left_child)
	{
		x=x->left_child;
	}
	return x;
}
/*the maxmum key of node in the tree*/
PNode Maxmum_Tree(PNode root)
{
	PNode x=root;
	while(NULL!=x->right_child)
	{
		x=x->right_child;
	}
	return x;
}
/*the successor node of the x,后继节点可以这么理解，将查找树从小到大排序，比他大的值
如果有右孩子，那么应该是右子树当中的最小值
如果没有右孩子，那么应该向上追溯，直至一个分支节点是其父节点的左孩子，返回父节点
可以用于operate++*/
PNode Successor_Tree(PNode x)
{
	PNode y=NULL;
	//case 1:the right subtree of node x is not empty
	if(NULL!=x->right_child)
	{
		y=Minimum_Tree(x->right_child);
	}
	//case 2:the right subtree of node x is empty
	//and the node of x has a successor node y
	else
	{
		y=x->parent;
		while(NULL!=y && x==y->right_child) 
		{
			x=y;
			y=y->parent;
		}
	}
	return y;
}
/*the predecessor node of the x，前任节点
如果节点有左孩子，那么找到左孩子的最大值
如果没有左孩子，那么向上追溯直至一个分支当前节点是对应父节点的右孩子，返回父节点的值
*/
PNode Predecessor_Tree(PNode x)
{
	PNode y=NULL;
	//case 1:the left subtree of node x is not empty
	if(NULL!=x->left_child)
	{
		y=Maxmum_Tree(x->left_child);
	}
	//case 2:the left subtree of node x is empty
	//and the node of x has a predecessor node y
	else
	{
		y=x->parent;
		while(NULL!=y && x==y->left_child)
		{
			x=y;
			y=y->parent;
		}
	}
	return y;
}
/*insert a new node into the BST*/
void Insert_Tree(PNode *root,int key)
{
	PNode x=*root;
	PNode y=NULL;
	PNode z=(PNode)malloc(sizeof(Node));//<开辟一个节点的空间
	if(NULL==z)
	{
		printf("malloc the z is failed.");
		exit(1);
	}
	//initial the node of z
	z->key=key;
	z->left_child=z->right_child=z->parent=NULL;
	//Find the location node of y to insert the node of z
	while(NULL!=x)
	{
		y=x; //<找到当前树满足条件的叶子节点了，表示为y，之后在y节点后面进行插入操作
		if(z->key<x->key)
			x=x->left_child;
		else
			x=x->right_child;
	}
	//insert the node of z
	z->parent=y;
	if(NULL==y)
		*root=z;//tree was empty
	else
	{
		if(z->key<y->key)
			y->left_child=z;
		else
			y->right_child=z;
	}
}
void Transplant(PNode *root,PNode u,PNode v)
{
	if(NULL==u->parent)
		*root=v;
	else
	{
		if(u==u->parent->left_child)
			u->parent->left_child=v;
		else
			u->parent->right_child=v;
	}
	if(NULL!=v)
		v->parent=u->parent;
}
/*delete a node in the binary search tree*/
void Delete_Tree(PNode *root,int key) //<删除节点
{
	//Find the node you want to delete
	PNode p=Search_Tree(*root,key);
	if(NULL==p->left_child)
		Transplant(root,p,p->right_child);
	else
	{
		if(NULL==p->right_child)
			Transplant(root,p,p->left_child);
		else
		{
			PNode y=Successor_Tree(*root);
			if(y->parent!=p)
			{
				Transplant(root,y,y->right_child);
				y->right_child=p->right_child;
				y->right_child->parent=y;
			}
			Transplant(root,p,y);
			y->left_child=p->left_child;
			y->left_child->parent=y;
		}
	}
}
/*print the key of binary search tree*/
void ioder_Tree(PNode root)
{
	if(NULL!=root)
	{
		ioder_Tree(root->left_child);
		printf("  %d",root->key);
		ioder_Tree(root->right_child);
	}
}
int main()  
{  
	int i;  
	int Arr[LENGTH]={16,6,20,2,7,19,22,1,4,11,8};  
	PNode root=NULL;  
	PNode p=NULL;  
	for(i=0;i<LENGTH;i++)  
	{  
		Insert_Tree(&root,Arr[i]);  
	}  
	ioder_Tree(root);  
	printf("\n");  
	//printf("Hello world!\n");  
	Delete_Tree(&root,11);  
	ioder_Tree(root);  
	printf("\n");  
	p=Maxmum_Tree(root);  
	printf("The Maxmum of node is:%d\n",p->key);  
	p=Minimum_Tree(root);  
	printf("The Minimum of node is:%d\n",p->key);  
	return 0;  
}  

结果图:

除了在STL中搜索二叉树之外，还必须以平衡的方式搜索二叉树:

因为相关的容器非常重要，所以搜索效率

平衡树有很多，例如AVL_tree，RB-tree，AA-tree

在平衡的二叉树中插入和删除节点的平均时间相对较长，但它们可以很好地避免难以处理的最坏情况

AVL树要求任何节点的左右子树之间的高度差最大为1

如果插入或删除操作破坏了这些平衡条件，那么应该相应地旋转这种树以达到平衡

RB树的节点在红色和黑色之间有所区别，并且有一些限制，稍后将介绍.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-272665-1.html