调试错误的AVL树“插入”操作

问题描述 投票：0回答：1

我正在尝试创建一个可以处理重复元素键的 AVL 树数据结构。我的插入算法基于以下内容：https://www.sanfoundry.com/c-program-implement-avl-tree/#google_vignette。

但是，我的

avl_tree_insert
实现似乎无法处理某些重复键，我不知道为什么；基本上，我已经确定插入有效，除非满足以下所有条件*（*这来自我自己对代码执行的检查的理解，结合调试输出。这可能是错误的逻辑，至少由一条评论。阅读代码了解实际细节）：

  1. 正在插入的密钥已存在于树中。
  2. 根节点具有 null 
    left
    和 
    right
    子字段。
  3. 根节点不平衡（意味着根节点需要右旋）。
  4. 插入的键大于或等于根左侧的键（意味着需要对左节点进行左旋转）。

当代码检查 4 时，会调用左节点的左旋转，这会因空指针取消引用而崩溃（因为 

( *root ).left
和 
( *root ).right
为空，请参阅 2）。

令我困惑的是如何弄清楚如何这个树状态实际上是如何产生的，以及如何修复它；例如，对于树的许多不同的随机状态，使用随机键调用 

avl_tree_insert
通常可以工作数百或数千次，但随后树突然达到如上所述的状态，并且一切都突然失败；这是我不知道如何调试。

下面是一些测试驱动程序代码，使用 

avl_tree_insert
操作会导致崩溃。我尝试在下面包含树数据结构和插入算法的所有相关部分，同时省略任何无关的内容，并且还包含一些调试打印语句。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// Adjust for your hardware.
typedef unsigned long long int  u64;
typedef signed long long int    i64;
typedef signed short int        i16;

/** @brief Type and instance definitions for generic boolean type. */
typedef _Bool bool;
#define true    ( ( bool ) 1 )
#define false   ( ( bool ) 0 )

// Print line binding.
// Requires compiler support for __VA_ARGS__.
#define println(formatting,...) \
    printf ( formatting"\n" , ##__VA_ARGS__ )

// Evaluates to the maximum of two values.
// Requires compiler support for __typeof__.
#define MAX(a,b)                      \
    ({                                \
        __typeof__ ( (a) ) a__ = (a); \
        __typeof__ ( (b) ) b__ = (b); \
       ( a__ > b__ ) ? a__ : b__;     \
    })

/** @brief Type definition for an AVL tree node. */
typedef struct node_t
{
    i64             key;
    u64             depth;

    struct node_t*  left;
    struct node_t*  right;

    void*           content;
}
node_t;

/** @brief Type definition for an AVL tree. */
typedef struct
{
    u64         element_width;
    u64         element_count;

    u64         node_count;
    node_t*     root;
}
avl_tree_t;

// Global op count.
static u64 op_count = 0;

// Global debug flag.
static bool debug_flag;

bool
avl_tree_create
(   u64             element_width
,   avl_tree_t**    tree_
)
{
    if ( !element_width )
    {
        println ( "avl_tree_create: Value of element_width argument must be non-zero." );
        return false;
    }
    if ( !tree_ )
    {
        println ( "avl_tree_create: Missing argument: tree (output buffer)." );
        return false;
    }

    avl_tree_t* tree = malloc ( sizeof ( avl_tree_t ) );
    ( *tree ).element_width = element_width;
    ( *tree ).element_count = 0;
    ( *tree ).node_count = 0;
    ( *tree ).root = 0;
    
    *tree_ = tree;
    return true;
}

u64
avl_tree_recompute_depth
(   node_t* root
)
{
    u64 left;
    u64 right;
    
    if ( !root )
    {
        return 0;
    }

    if ( !( *root ).left )
    {
        left = 0;
    }
    else
    {
        left = 1 + ( *( ( *root ).left ) ).depth;
    }

    if ( !( *root ).right )
    {
        right = 0;
    }
    else
    {
        right = 1 + ( *( ( *root ).right ) ).depth;
    }

    return MAX ( left , right );
}

i64
avl_tree_balance_factor
(   node_t* root
)
{
    u64 left;
    u64 right;
    
    if ( !root )
    {
        return 0;
    }

    if ( !( *root ).left )
    {
        left = 0;
    }
    else
    {
        left = 1 + ( *( ( *root ).left ) ).depth;
    }

    if ( !( *root ).right )
    {
        right = 0;
    }
    else
    {
        right = 1 + ( *( ( *root ).right ) ).depth;
    }

    return left - right;
}

node_t*
avl_tree_rotate_left
(   node_t* root
)
{
    // Rotate left.
    node_t* right = ( *root ).right;
    if ( !right ) println ( "Failure on append #%llu. No node to the right of %i." , op_count , ( *root ).key );
    ( *root ).right = ( *right ).left;
    ( *right ).left = root;

    // Update depth.
    ( *root ).depth = avl_tree_recompute_depth ( root );
    ( *right ).depth = avl_tree_recompute_depth ( right );

    return right;
}

node_t*
avl_tree_rotate_right
(   node_t* root
)
{
    // Rotate right.
    node_t* left = ( *root ).left;
    if ( !left ) println ( "Failure on append #%llu. No node to the left of %i." , op_count , ( *root ).key );
    ( *root ).left = ( *left ).right;
    ( *left ).right = root;

    // Update depth.
    ( *root ).depth = avl_tree_recompute_depth ( root );
    ( *left ).depth = avl_tree_recompute_depth ( left );

    return left;
}

node_t*
__avl_tree_insert
(   avl_tree_t* tree
,   node_t*     root
,   const void* src
,   const i64   key
)
{
    // CASE: End of branch.
    if ( !root )
    {
        // Initialize a new element node.
        node_t* node = malloc ( sizeof ( node_t ) + ( *tree ).element_width );
        memset ( node , 0 , sizeof ( node_t ) );
        ( *node ).key = key;
        ( *node ).content = ( void* )( ( ( u64 ) node ) + sizeof ( node_t ) );
        memcpy ( ( *node ).content , src , ( *tree ).element_width );

        // Insert the node into the tree.
        root = node;

        // Update state.
        ( *tree ).node_count += 1;
        ( *tree ).element_count += 1;
    }

    // CASE: Key > root key (recurse right).
    else if ( key > ( *root ).key )
    {
        ( *root ).right = __avl_tree_insert ( tree
                                            , ( *root ).right
                                            , src
                                            , key
                                            );

        // Rebalance? Y/N
        if ( avl_tree_balance_factor ( root ) < -1 )
        {
            if ( key <= ( *( ( *root ).right ) ).key )
            {
                ( *root ).right = avl_tree_rotate_right ( ( *root ).right );
            }
            root = avl_tree_rotate_left ( root );
        }
    }

    // CASE: Key <= root key (recurse left).
    else
    {
        if ( key == ( *root ).key )
        {
            debug_flag = true;
            println ( "Keys match: %i, left key: %i, right key: %i"
                    , key
                    , ( ( *root ).left ? ( *( ( *root ).left ) ).key : -1 )
                    , ( ( *root ).right ? ( *( ( *root ).right ) ).key : -1 )
                    );
        }
        ( *root ).left = __avl_tree_insert ( tree
                                           , ( *root ).left
                                           , src
                                           , key
                                           );

        // Rebalance? Y/N
        if ( avl_tree_balance_factor ( root ) > 1 )
        {
            if ( key >= ( *( ( *root ).left ) ).key )
            {
                if ( debug_flag ) println ("Rotate left required." );
                ( *root ).left = avl_tree_rotate_left ( ( *root ).left );
            }
            root = avl_tree_rotate_right ( root );
        }
    }
    
    ( *root ).depth = avl_tree_recompute_depth ( root );
    return root;
}

void
_avl_tree_insert
(   avl_tree_t* tree
,   const void* src
,   const i64   key
)
{
    debug_flag = false;
    ( *tree ).root = __avl_tree_insert ( tree
                                       , ( *tree ).root
                                       , src
                                       , key
                                       );
}

// Alias for calling _avl_tree_insert on a literal value.
// Requires compiler support for __typeof__.
#define avl_tree_insert(tree,value,key)            \
    do                                             \
    {                                              \
        __typeof__ ( (value) ) tmp = (value);      \
       _avl_tree_insert ( (tree) , &tmp , (key) ); \
    }                                              \
    while ( 0 )

// Test driver.
int
main
( void )
{
    srand ( time ( 0 ) );

    avl_tree_t* tree;
    avl_tree_create ( sizeof ( i16 ) , &tree );

    for ( u64 i = 0; i < 1000000; ++i )
    {
        i16 key;
        do
        {
            key = rand ();
        }
        while ( key == -1 );
        op_count += 1;
        avl_tree_insert ( tree , key , key ); // Value can just be same as key here.
    }
    println ( "Num elements in tree: %llu" , ( *tree ).element_count );

    return 0;
}

输出示例（-1表示空键）：

Keys match: 2214, left key: -1, right key: -1
Keys match: 5145, left key: -1, right key: -1
Keys match: 7141, left key: -1, right key: -1
Keys match: 16453, left key: -1, right key: -1
Keys match: 15365, left key: -1, right key: -1
Keys match: 22779, left key: 22764, right key: 22816
Keys match: 11855, left key: -1, right key: -1
Rotate left required.
Failure on append #857. No node to the right of 11855.
// (OS crashes the program)
c data-structures binary-tree avl-tree insertion
1个回答
0
投票

只需插入以下三个值即可重现这一点：2、1、1。

问题的直接原因在于如何确定是否需要双旋转。执行先右后左旋转的条件是：

if ( key <= ( *( ( *root ).right ) ).key )

...还有镜盒：

if ( key >= ( *( ( *root ).left ) ).key )

这是错误的。双轮换的条件是存在“内”孙子。因此，请通过以下方式纠正这两个条件： if (root->right->left) 

和

if (root->left->right) 

除此之外我没有测试您的代码，但这至少是您遇到问题的原因。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.