855学习记录数据结构树(5)搜索树基础——炎泽汐$de$ Blog

文章目录[隐藏]

• 二叉搜索树
• 平衡二叉搜索树($AVL$树)

基于二叉树模板实现

---

      查找：

bool search(TreeNode* root, int x){
	if(!root){
		return false;
	}
	if(x == root -> val){
		return true;
	}else if(x < root -> val){
		if(search(root -> left, x)){
			return true;
		}else{
			return false;
		}
	}else{
		if(search(root -> right, x)){
			return true;
		}else{
			return false;
		}
	}
}

      插入：

void insert(TreeNode* root, int x){
	if(!root){
		root = new TreeNode(x);
		return;
	}
	if(x == root -> val){
		return;
	}else if(x < root -> val){
		insert(root -> left, x);
	}else{
		insert(root -> right, x);
	}
}

      建树：

TreeNode* Create(vector<int>& data){
	TreeNode* root = nullptr;
	for(int i = 0; i < data.size(); i++){
		insert(root, data[i]);
	}
	return root;
}

      删除：

TreeNode* FindMax(TreeNode* root){
	while(root -> right){
		root = root -> right;
	}
	return root;
}

TreeNode* FindMin(TreeNode* root){
	while(root -> left){
		root = root -> left;
	}
	return root;
}

void Delete(TreeNode* &root, int x){
	if(!root){
		return;
	}
	if(root -> val == x){
		if(!root -> left && !root -> right){
			root = nullptr;
		}else if(root -> left){
			TreeNode* pre = FindMax(root -> left);
			root -> val = pre -> data;
			Delete(root -> left, root -> val);
		}else{
			TreeNode* next = FindMin(root -> left);
			root -> val = next -> data;
			Delete(root -> right, root -> val);
		}
	}else if(root -> val < x){
		Delete(root -> right, x);
	}else{
		Delete(root -> left, x);
	}
}

相关实现

---

//AVL 树 
struct AvlNode {
	int val, height;
	AvlNode *left;
	AvlNode *right;
	AvlNode() : val(0), left(nullptr), right(nullptr), height(1) {}
	AvlNode(int x, int y) : val(x), left(nullptr), right(nullptr), height(y) {}
 	AvlNode(int x, int y, AvlNode *left, AvlNode *right) : val(x), left(left), right(right), height(y) {}
};

int getHeight(AvlNode *root){
	if(!root){
		return 0;
	}else{
		return root -> height;
	}
}

int getBalanceFactor(AvlNode *root){
	return getHeight(root -> left) - getHeight(root -> right);
}

void updataHeight(AvlNode *root){
	root -> height = max(getHeight(root -> left), getHeight(root -> right)) + 1;
}

void RR(AvlNode* &root){
	//右右(左单旋)
	AvlNode* temp = root -> right;
	root -> right = temp -> left;
	temp -> left = root;
	updataHeight(root);
	updataHeight(temp);
	root = temp;
}

void LL(AvlNode* &root){
	//左左(右单旋)
	AvlNode* temp = root -> left;
	root -> left = temp -> right;
	temp -> right = root;
	updataHeight(root);
	updataHeight(temp);
	root = temp;
}

void LR(AvlNode* &root){
	RR(root -> left);
	LL(root);
}

void RL(AvlNode* &root){
	LL(root -> right);
	RR(root);
}

void insert(AvlNode* &root, int v){
	if(!root){
		root = new AvlNode(v);
		return;
	}
	if(v < root -> val){
		insert(root -> left, v);
		updataHeight(root);
		if(getBalanceFactor(root) == 2){
			if(getBalanceFactor(root -> left) == 1){
				LL(root);
			}else if(getBalanceFactor(root -> left) == -1){
				LR(root);
			}
		}
	}else{
		insert(root -> right, v);
		updataHeight(root);
		if(getBalanceFactor(root) == -2){
			if(getBalanceFactor(root -> right) == -1){
				RR(root);
			}else if(getBalanceFactor(root -> right) == 1){
				RL(root);
			}
		}
	}
}

AvlNode* Create(vector<int>& data){
	AvlNode* root = nullptr;
	for(int i = 0; i < data.size(); i++){
		insert(root, data[i]);
	}
	return root;
}

AvlNode* getPre(AvlNode* root){
	if(!root) {
		return nullptr;
	}
	while(root -> right){
		root = root -> right;
	}
	return root;
}

void Delete(AvlNode* &root, int v){
	if(!root){
		return;
	}
	if(v < root -> val){
		Delete(root -> left, v);
		updataHeight(root);
		if(getBalanceFactor(root) == -2){
			if(getBalanceFactor(root -> right) == -1){
				RR(root);
			}else if(getBalanceFactor(root -> right) == 1){
				RL(root);
			}
		}
	}else if(v > root -> val){
		Delete(root -> right, v);
		updataHeight(root);
		if(getBalanceFactor(root) == 2){
			if(getBalanceFactor(root -> left) == 1){
				LL(root);
			}else if(getBalanceFactor(root -> left) == -1){
				LR(root);
			}
		}
	}else{
		if(root -> left && root -> right){
			AvlNode* pre = getPre(root -> left);
			root -> val = pre -> val;
			Delete(root -> left, pre -> val);
		}else if(!root -> left && !root -> right){
			delete root;
			root = nullptr;
		}else{
			root = root -> left ? root -> left : root -> right;
		}
	}
	if(root){
		updataHeight(root);
	}
}