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不是相同的吗
1
illuz 2015-04-23 09:01:35 +08:00
`T->Right = Insert( X, T->Right );`
这句话是递归调用,最后插入的 X 会在 (T->Right) 子树叶子节点,或者树中已存在就不插入了,而不是一定插在 (T->Right) 子树的根节点。 所以插入后的 (T->left->Element) 并不一定是新插入节点,它跟 X 可能不是相同的。 |
2
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 可能不是相同的。 |
3
insaneDream OP @illuz `T->Right = Insert( X, T->Right );`,如果T->Right==NULL的,那么它就会创建一个新的节点并返回给T->Right, 那么插入的X不是在T->Right这个节点上吗?
|