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