网络子系统40_inet_peer平衡二叉树的插入

//	遍历二叉树路径
//	宏的主要任务：	
//		1.遍历到达目标节点的路径
//		2.将路径上经过的节点保存在stack中
//		3.栈顶为peer_avl_empty
//		4.stackptr指向下一个空闲的位置
1.2 #define lookup(_daddr,_stack) 				\
({								\
	struct inet_peer *u, **v;				\
	if (_stack != NULL) {					\
		stackptr = _stack;//栈指针指向栈底		\
		*stackptr++ = &peer_root;//栈底为root，移动栈指针	\
	}							\
	for (u = peer_root; u != peer_avl_empty; ) {		\
		if (_daddr == u->v4daddr)			\
			break;					\
		if ((__force __u32)_daddr < (__force __u32)u->v4daddr)	\
			v = &u->avl_left;			\
		else						\
			v = &u->avl_right;			\
		if (_stack != NULL)				\
			*stackptr++ = v;			\
		u = *v;						\
	}							\
	u;							\
})

//	插入平衡二叉树
//	注：新节点的初始化为1
#define link_to_pool(n)						\
do {								\
	n->avl_height = 1;			\
	n->avl_left = peer_avl_empty;	//左右均为empty		\
	n->avl_right = peer_avl_empty;				\
	**--stackptr = n;	//通过将节点压入栈顶，完成插入操作	\
	peer_avl_rebalance(stack, stackptr);//调整二叉树平衡			\
} while(0)

//	平衡二叉树
//	参数：
//		stack，寻找目标节点时路径上经过的所有节点
//		stackend，栈顶指针

1.3 static void peer_avl_rebalance(struct inet_peer **stack[],
		struct inet_peer ***stackend)
{
	struct inet_peer **nodep, *node, *l, *r;
	int lh, rh;

	while (stackend > stack) {//stackend指向的节点非根节点
		nodep = *--stackend;//nodep为指向要插入节点的父节点的指针
		node = *nodep;//父节点的指针
		l = node->avl_left;//父节点的左孩子
		r = node->avl_right;//右孩子
		lh = node_height(l);//高度
		rh = node_height(r);
		if (lh > rh + 1) { //根平衡因子变为2
			struct inet_peer *ll, *lr, *lrl, *lrr;
			int lrh;
			ll = l->avl_left;//根的左孩子的左孩子
			lr = l->avl_right;//根的左孩子的右孩子
			lrh = node_height(lr);//左孩子的右孩子的高度
			if (lrh <= node_height(ll)) {	//并且是在左孩子的左子树插入节点,RR,情况1.1
				node->avl_left = lr;	/* lr: RH or RH+1 */
				node->avl_right = r;	/* r: RH */
				node->avl_height = lrh + 1; /* RH+1 or RH+2 */
				l->avl_left = ll;	/* ll: RH+1 */
				l->avl_right = node;	/* node: RH+1 or RH+2 */
				l->avl_height = node->avl_height + 1;
				*nodep = l;	//左孩子成为
			} else { //并且是在左孩子的右子树插入节点,LL,RR,情况1.2
				lrl = lr->avl_left;	/* lrl: RH or RH-1 */
				lrr = lr->avl_right;	/* lrr: RH or RH-1 */
				node->avl_left = lrr;	/* lrr: RH or RH-1 */
				node->avl_right = r;	/* r: RH */
				node->avl_height = rh + 1; /* node: RH+1 */
				l->avl_left = ll;	/* ll: RH */
				l->avl_right = lrl;	/* lrl: RH or RH-1 */
				l->avl_height = rh + 1;	/* l: RH+1 */
				lr->avl_left = l;	/* l: RH+1 */
				lr->avl_right = node;	/* node: RH+1 */
				lr->avl_height = rh + 2;
				*nodep = lr;	//左孩子的右子树根成为当前的根节点
			}
		} else if (rh > lh + 1) { //根平衡因子变为-2
			struct inet_peer *rr, *rl, *rlr, *rll;
			int rlh;
			rr = r->avl_right;
			rl = r->avl_left;
			rlh = node_height(rl);
			if (rlh <= node_height(rr)) {	//在右孩子的右子树上插入节点，LL,情况1.3
				node->avl_right = rl;	/* rl: LH or LH+1 */
				node->avl_left = l;	/* l: LH */
				node->avl_height = rlh + 1; /* LH+1 or LH+2 */
				r->avl_right = rr;	/* rr: LH+1 */
				r->avl_left = node;	/* node: LH+1 or LH+2 */
				r->avl_height = node->avl_height + 1;
				*nodep = r;//右孩子作为根节点
			} else { //在右孩子的左子树上插入节点，RR，LL,情况1.4
				rlr = rl->avl_right;	/* rlr: LH or LH-1 */
				rll = rl->avl_left;	/* rll: LH or LH-1 */
				node->avl_right = rll;	/* rll: LH or LH-1 */
				node->avl_left = l;	/* l: LH */
				node->avl_height = lh + 1; /* node: LH+1 */
				r->avl_right = rr;	/* rr: LH */
				r->avl_left = rlr;	/* rlr: LH or LH-1 */
				r->avl_height = lh + 1;	/* r: LH+1 */
				rl->avl_right = r;	/* r: LH+1 */
				rl->avl_left = node;	/* node: LH+1 */
				rl->avl_height = lh + 2;
				*nodep = rl;	//右孩子的左子树根作为当前的根节点
			}
		} else {//平衡因子为0,1,-1
			node->avl_height = (lh > rh ? lh : rh) + 1;
		}
	}
}