581
网络子系统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;
}
}
}
最后更新：2017-04-03 14:53:37