balanced_binary_tree 0.1.0

//! 平衡二叉树的相关方法

use std::fmt;

pub struct AvlNode{
	height:isize,
	data:isize,
	l_child:Option<Box<AvlNode>>,
	r_child:Option<Box<AvlNode>>,
}

impl fmt::Display for AvlNode{
	fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{
		write!(f,"[{}({})",self.data,self.height)?;
		match &self.l_child{
			Some(c)=>c.fmt(f)?,
			None=>(),
		}
		match &self.r_child{
			Some(c)=>c.fmt(f)?,
			None=>(),
		}		
		write!(f,"]")
	}
}

impl AvlNode{
	pub fn new_with_child(data:isize,l_child:Option<Box<AvlNode>>,r_child:Option<Box<AvlNode>>)->AvlNode{
		AvlNode{
			height:0,
			data,
			l_child,
			r_child,
		}
	}	
	
	pub fn new(data:isize)->AvlNode{
		AvlNode{
			height:0,
			data,
			l_child:None,
			r_child:None,
		}
	}
	
	pub fn insert(mut self,key:isize)->Option<Box<Self>>{
		let n = AvlNode::new(key);
		if key < self.data{
			self.l_child = match self.l_child{
				Some(pl)=>pl.insert(key),
				None=>{
					Some(Box::new(n))
				},
			};
			self.height = get_height(&self);
			self = balance(self);
		}else if key > self.data{
			self.r_child = match self.r_child{
				Some(pr)=>pr.insert(key),
				None=>{
					Some(Box::new(n))
				},		
			};
			self.height = get_height(&self);
			self = balance(self);			
		}
		return Some(Box::new(self));
	}
	
	pub fn del(mut self,key:isize)->Option<Box<Self>>{
		if key < self.data{
			self.l_child=match self.l_child{
				Some(c)=>{
					c.del(key)
				},
				None=>{
					None
				}
			};
		}else if key > self.data{
			self.r_child=match self.r_child{
				Some(c)=>{
					c.del(key)
				},
				None=>{
					None
				}
			};			
		}else{
			let l_child = self.l_child;
			let r_child = self.r_child;
			
			match l_child{
				Some(lc)=>{
					match r_child{
						Some(rc)=>{
							//2个孩子
							let (n,d) = del_r_d(*lc);
							self.l_child = n;
							self.r_child = Some(rc);
							self.data = d;
							//调整
							self = balance_del(self);
							return Some(Box::new(self));
						},
						None=>{
							//有左没右
							return Some(lc);
						},
					}
				},
				None=>{
					match r_child{
						Some(rc)=>{
							//没左有右
							return Some(rc);
						},
						None=>{
							//0个孩子
							return None;
						},
					}					
				},
			}
		}
		self.height = get_height(&self);
		self = balance(self);
		Some(Box::new(self))
	}	
		
}

/// 删除右下
fn del_r_d(mut node:AvlNode)->(Option<Box<AvlNode>>,isize){
	let n_res;
	let data;
	match node.r_child{
		Some(c)=>{
			let (n,d) = del_r_d(*c);
			node.r_child = n;
			node.height = get_height(&node);
			node = balance(node);
			n_res=Some(Box::new(node));
			data = d;
		},
		None=>{
			data = node.data;
			n_res = match node.l_child{
				Some(l)=>Some(l),
				None=>None,
			};
		},
	}
	(n_res,data)
}

fn balance_del(mut node:AvlNode) -> AvlNode{
	node.r_child = match node.r_child{
		Some(c)=>{
			Some(Box::new(balance_del(*c)))
		},
		None=>{
			None
		},
	};
	node.height = get_height(&node);
	node = balance(node);	
	node
}

fn balance(mut node:AvlNode) -> AvlNode{
	let bf = get_bf(&node);
	if bf == 2{
		node.l_child = match node.l_child{
			Some(mut c)=>{
				let bf1 = get_bf(&c);
				if bf1 == 1{
					//LL
					node.l_child = Some(c);
					node = to_r(node);
					node.l_child
				}else if bf1 == -1{
					//LR
					c = Box::new(to_l(*c));
					node.l_child = Some(c);
					node = to_r(node);
					node.l_child
				}else{
					Some(c)
				}
			},
			None=>{None},
		};
		node.height = get_height(&node);
	} else if bf == -2{
		node.r_child = match node.r_child{
			Some(mut c)=>{
				let bf1 = get_bf(&c);
				if bf1 == 1{
					//RL
					c = Box::new(to_r(*c));
					node.r_child = Some(c);
					node = to_l(node);
					node.r_child				
				}else if bf1 == -1{
					//RR
					node.r_child = Some(c);
					node = to_l(node);
					node.r_child
				}else{
					Some(c)
				}						
			},
			None=>{None},
		};
		node.height = get_height(&node);
	}
	node	
}

fn to_r(mut node:AvlNode) -> AvlNode{
	node.l_child = match node.l_child{
		Some(mut c)=>{
			let data = node.data;
			let lr = c.r_child;
			let r = node.r_child;
			c.r_child = None;
			node.data = c.data;
			let mut n = AvlNode::new_with_child(data,lr,r);
			n.height = get_height(&n);
			node.r_child = Some(Box::new(n));
			c.l_child
		},
		None=>{None},
	};
	node	
}

fn to_l(mut node:AvlNode) -> AvlNode{
	node.r_child = match node.r_child{
		Some(mut c)=>{
			let data = node.data;
			let rl = c.l_child;
			let l = node.l_child;
			c.l_child = None;
			node.data = c.data;
			let mut n = AvlNode::new_with_child(data,l,rl);
			n.height = get_height(&n);
			node.l_child = Some(Box::new(n));
			c.r_child
		},
		None=>{None},
	};
	node	
}

fn get_bf(node:&AvlNode) -> isize{
	let bf;
	match &node.l_child{
		Some(l)=>{
			match &node.r_child{
				Some(r)=>{
					bf = l.height - r.height;
				},
				None=>{
					bf = l.height;
				},
			}
		},
		None=>{
			match &node.r_child{
				Some(r)=>{
					bf = 0 - r.height;
				},
				None=>{
					bf = 0;
				},
			}
		},
	}
	bf	
}

fn get_height(node:&AvlNode) -> isize{
	let h;
	match &node.l_child{
		Some(l)=>{
			match &node.r_child{
				Some(r)=>{
					if l.height - r.height < 0{
						h = r.height + 1;
					}else{
						h = l.height + 1;
					}
				},
				None=>{
					h = l.height + 1;
				},
			}
		},
		None=>{
			match &node.r_child{
				Some(r)=>{
					h = r.height + 1;
				},
				None=>{
					h = 0;
				},
			}
		},
	}
	h	
}