Rust实现AVL树遇malloc错误：pointer being freed was not allocated

错误信息 #

hello-rust(23862,0x204488600) malloc: *** error for object 0x600003b79140: pointer being freed was not allocated
hello-rust(23862,0x204488600) malloc: *** set a breakpoint in malloc_error_break to debug

问题代码 #

use std::ptr::NonNull;

type Link<T> = Option<NonNull<Node<T>>>;

#[derive(Debug)]
pub struct Node<T> {
    elem: T,
    parent: Link<T>,
    left: Link<T>,
    right: Link<T>,
    bf: i8,
}

impl<T> Node<T> {
    pub fn new_with_elem(elem: T) -> Node<T> {
        Node {
            elem,
            parent: None,
            left: None,
            right: None,
            bf: 0,
        }
    }
}

#[derive(Debug)]
pub struct AvlTree<T> {
    root: Link<T>,
    count: usize,
}

impl<T: PartialEq + Eq + std::cmp::PartialOrd + Clone+std::fmt::Display> AvlTree<T> {
    pub fn new() -> AvlTree<T> {
        AvlTree { root: None, count: 0 }
    }

    pub fn insert(&mut self, elem: T) {
        let elem_clone = elem.clone();
        let mut new_node = Node::new_with_elem(elem);
        if self.count == 0 {
            self.root = new_link_with_node(new_node);
            self.count += 1;
            return;
        }
        let mut bf = 0;
        let mut parent: Link<T> = None;
        let mut n = self.root;
        while n.is_some() {
            n.map(|node| {
                unsafe {
                    println!("elem={}", &elem_clone);
                    let box_node = Box::from_raw(node.clone().as_ptr());
                    if elem_clone == box_node.elem {
                        return;
                    }
                    parent = n;
                    bf <<= 1;
                    if elem_clone < box_node.elem {
                        n = box_node.left;
                    } else {
                        n = box_node.right;
                        bf |= 1;
                    }
                }
            });
        }

    }
}

impl<T: std::fmt::Display> std::fmt::Display for Node<T> {
    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        write!(fmt, " elem:{},bf:{} | ", self.elem, self.bf)
    }
}

impl<T: std::fmt::Display> std::fmt::Display for AvlTree<T> {
    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        if self.root.is_none() {
            write!(fmt, " empty tree! ")
        } else {
            show_node(&self.root);
            write!(fmt, " print over ")
        }
    }
}

fn show_node<T: std::fmt::Display>(node: &Link<T>) {
    node.map(|n| {
        unsafe {
            let box_node = Box::from_raw(n.as_ptr());
            println!("{}", box_node);
            if box_node.left.is_some() {
                show_node(&box_node.left)
            }
            if box_node.right.is_some() {
                show_node(&box_node.right)
            }
        }
    });
}

fn new_link_with_node<T: PartialEq + Eq + std::cmp::PartialOrd + Clone>(node: Node<T>) -> Link<T> {
    NonNull::new(Box::into_raw(Box::new(node)))
}

问题分析与修复方案 #

核心问题 #

错误根源是重复释放同一内存块：Box::from_raw会获取指针的所有权，当Box离开作用域时会自动调用free释放内存。但你在遍历、打印节点时多次用Box::from_raw处理同一个指针，导致同一内存被多次释放，触发malloc错误。

具体修复 #

1. 遍历逻辑修改：避免获取指针所有权
   遍历仅通过指针引用访问节点，不要转换为Box。修改insert方法中的循环部分：

   while n.is_some() {
       let node = n.unwrap();
       unsafe {
           let box_node = &*node.as_ptr(); // 仅获取不可变引用，不夺取所有权
           println!("elem={}", &elem_clone);
           if elem_clone == box_node.elem {
               return;
           }
           parent = n;
           bf <<= 1;
           if elem_clone < box_node.elem {
               n = box_node.left;
           } else {
               n = box_node.right;
               bf |= 1;
           }
       }
   }
   

2. 打印函数修改：用引用访问节点
   同样，show_node函数不要用Box::from_raw，改用引用访问：

   fn show_node<T: std::fmt::Display>(node: &Link<T>) {
       node.map(|n| {
           unsafe {
               let box_node = &*n.as_ptr(); // 获取引用而非所有权
               println!("{}", box_node);
               if box_node.left.is_some() {
                   show_node(&box_node.left)
               }
               if box_node.right.is_some() {
                   show_node(&box_node.right)
               }
           }
       });
   }
   

3. 补充插入逻辑收尾
   当前insert方法找到父节点后未完成新节点挂载，需添加代码将新节点链接到父节点，并后续补充AVL树的平衡因子更新与旋转逻辑：

   // 在insert方法的while循环后添加：
   let new_node_ptr = new_link_with_node(new_node).unwrap();
   unsafe {
       let parent_node = &mut *parent.unwrap().as_ptr();
       if elem_clone < parent_node.elem {
           parent_node.left = Some(new_node_ptr);
       } else {
           parent_node.right = Some(new_node_ptr);
       }
       // 此处需继续实现平衡因子更新、旋转调整逻辑
   }
   self.count += 1;
   

内容的提问来源于stack exchange，提问作者ggl