平衡树插入节点的疑问

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 3876 天前的主题，其中的信息可能已经有所发展或是发生改变。

AvlTree Insert ( ElementType X, AvlTree T ) { if ( T == NULL ) { /* Create and return a one-node tree */ T = malloc( sizeof( struct AvlNode ) ); if ( T == NULL ) FatalError( "Out of space!!!" ); else { T->Element = X; T->Height = 0; T->Left = T->Right = NULL; } } else if ( X < T->Element ) { T->Left = Insert( X, T->Left ); if ( Height( T->Left ) - Height( T->Right ) == 2 ) if ( X < T->Left->Element ) T = SingleRotateWithLeft( T ); else T = DoubleRotateWithLeft( T ); } else if ( X > T->Element ) { T->Right = Insert( X, T->Right ); if ( Height( T->Right ) - Height( T->Left ) == 2 ) if ( X > T->Right->Element ) T = SingleRotateWithRight( T ); else T = DoubleRotateWithRight( T ); } /* Else X is in the tree already;we'll do nothing */ T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1; return T; }

为什么会有｀if ( X < T->Left->Element )｀这个判断语句，T->left->Element不就是新插入节点的Element吗，那么它跟X不是相同的吗

height

element

left

4 条回复 2015-04-23 11:34:21 +08:00

illuz

2015-04-23 09:01:35 +08:00

`T->Right = Insert( X, T->Right );`
这句话是递归调用，最后插入的 X 会在 (T->Right) 子树叶子节点，或者树中已存在就不插入了，而不是一定插在 (T->Right) 子树的根节点。
所以插入后的 (T->left->Element) 并不一定是新插入节点，它跟 X 可能不是相同的。

illuz

2015-04-23 09:04:40 +08:00

复制语句复制得有点混乱，再来一次。 >.<

先看看前一句的：`T->Left = Insert( X, T->Left );`
这句话是递归调用 Insert 函数，而不是就直接插进去。
最后插入的 X 会在 (T->Left) 子树叶子节点，或者树中已存在就不插入了，而不是一定插在 (T->Left) 子树的根节点。
所以插入后的 (T->left->Element) 并不一定是新插入节点，它跟 X 可能不是相同的。

insaneDream

2015-04-23 09:10:05 +08:00

@illuz `T->Right = Insert( X, T->Right );`，如果T->Right==NULL的，那么它就会创建一个新的节点并返回给T->Right, 那么插入的X不是在T->Right这个节点上吗?

illuz

2015-04-23 11:34:21 +08:00

@makubx1 如果不是，就递归处理了，这样 X 就不在 T->Left 上了，所以说是不一定的。（都按 Left 那边来说）