Haskell二叉搜索树（BST）插入函数失效问题求助

Hey there! Let's break down what's going wrong with your BST insertion function and get it working properly step by step.

First: Your Initial Tree is Invalid #

The output you showed from foldTree [1,2,3] is Node 1 (Node 0 Empty 2 Empty) 3 (Node 0 Empty 1 Empty)—that's not a valid BST! In a BST, every node in the right subtree must be larger than the root, but here your root is 3 and its right child is 1 (way smaller).

This tells me your foldTree function isn't using your treeInsert correctly (or has its own bug). For example, if you implement foldTree as a simple fold over your insertion function, you'll get a valid tree:

foldTree :: Ord a => [a] -> Tree a
foldTree = foldr treeInsert Empty

Running foldTree [1,2,3] with this would give a valid BST like Node 2 (Node 1 (Node 0 Empty 1 Empty) 2 Empty) 3 Empty—which makes sense for an unbalanced tree.

Second: Your Insert Function Isn't Updating Heights #

Your Tree type includes a height field, but your treeInsert completely ignores updating it after modifying a subtree. The original height value stays the same even when the subtree grows, which breaks any logic that relies on height (like balancing later on).

Third: Possible Misunderstanding of Haskell's Immutability #

You said tree = treeInsert 4 tree didn't change the tree—remember, Haskell variables are immutable. That line creates a new binding for tree, not modifies the old one. In GHCI, you need to either reference the new binding directly or recheck after assigning:

-- Do this:
let tree = foldTree [1,2,3]
let updatedTree = treeInsert 4 tree
updatedTree  -- This will show the new tree

-- Or this:
tree = foldTree [1,2,3]
tree = treeInsert 4 tree
tree  -- Now this shows the updated version

Fixed Insertion Function #

Here's a corrected version of treeInsert that properly updates heights and maintains BST properties:

data Tree a = Empty | Node Integer (Tree a) a (Tree a) deriving (Show, Eq)

-- Helper to get the height of any tree (empty tree has height -1 by convention)
treeHeight :: Tree a -> Integer
treeHeight Empty = -1
treeHeight (Node h _ _ _) = h

-- Helper to calculate the correct height for a node after modifying its subtrees
calculateHeight :: Tree a -> Tree a -> Integer
calculateHeight left right = max (treeHeight left) (treeHeight right) + 1

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x Empty = Node 0 Empty x Empty  -- Leaf nodes have height 0
treeInsert x (Node _ left val right)  -- We ignore the old height, recalculate it
    | x == val = Node (calculateHeight left right) left x right  -- Value exists, just update height
    | x < val = let newLeft = treeInsert x left
                in Node (calculateHeight newLeft right) newLeft val right
    | x > val = let newRight = treeInsert x right
                in Node (calculateHeight left newRight) left val newRight

Test It Out #

With this fixed code:

tree = foldTree [1,2,3]
-- Output: Node 2 (Node 1 (Node 0 Empty 1 Empty) 2 Empty) 3 Empty

updatedTree = treeInsert 4 tree
-- Output: Node 3 (Node 1 (Node 0 Empty 1 Empty) 2 Empty) 3 (Node 0 Empty 4 Empty)

Now the insertion works as expected, and heights are correctly updated!

Key Takeaways #

• Make sure your foldTree uses your insertion function to build valid BSTs.
• Always update node heights after modifying subtrees—otherwise the height field is useless.
• Remember Haskell's immutability: you're creating new tree values, not modifying existing ones.

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