------- You are receiving this mail because: -------
You are the QA contact for the bug, or are watching the QA contact.
http://www.exim.org/bugzilla/show_bug.cgi?id=474 ------- Comment #4 from anomie@users.sourceforge.net 2007-02-21 17:38 -------
On Wed, Feb 21, 2007 at 12:05:44PM +0000, ph10@hermes.cam.ac.uk wrote:
>
> The tree is a binary balanced tree. I do not know of an algorithm for removing
> nodes and keeping the tree still balanced. These trees are intended for
> additions, but not subtractions. Therefore, I don't think anybody will ever
> write tree_removenode.
Some quick searching turns up this algorithm for AVL balanced binary trees:
If the node to remove is a leaf, you can just remove it. Then
rebalance.
If the node to remove has only one child, you can remove the node
and put the child in its place. The tree has always become shorter,
so rebalance.
Otherwise, pick either the largest node from the left subtree or the
smallest node from the right subtree of the to-be-removed node,
which will always fall into one of the above two cases. Remove this
moved-node from the tree as above and replace the to-be-removed node
with it, and rebalance ('starting' from where the moved-node used to
be, not from where the to-be-removed node was).
D C E
/ \ / \ / \
B F => B F or B F
/ \ / \ / / \ / \ \
A C E G A E G A C G
Rebalancing seems to be a little more complicated than in the insertion
case, since the tree may need to be rebalanced at more than one point.
Let me explain my reasoning (mainly for my own use if I get time to
implement this).
The 'balance factor' of a node is the difference between the height of
the left subtree and the height of the right subtree (R-L, usually); in
a balanced tree this is either -1, 0, or +1. An insertion or deletion
changes the balance factor of the parent node by 1 (± depending on which
operation and which side of the parent it is on), and if the new factor
is -2 or +2 we perform a rotation which returns the factor to 0. So far
so good.
In insertion, changing the balance factor on a node from ±1 to 0
(either directly changing from ±1 to 0, or by changing to ±2 then
rotating) means the height of the subtree rooted at this node has not
changed and therefore the node's parent's balance factor has not
changed. Otherwise, we need to adjust the balance on the node's parent
(-1 if this is the left node and +1 if this is the right) and iterate
this paragraph. Note that only 1 rotation is ever needed since any
rotation moves to 0, and this rotation can only ever be at the most
recent parent that is ±1. Exim takes advantage of this.
In deletion, changing the balance factor on a node from ±1 to 0
means the height of the subtree rooted at this node HAS changed. We can
limit the changes to the subtree rooted at the most recent parent that
is 0, but there is a possible rotation at every parent in between. At
least we can determine if rotation is needed for any parent just by
considering that parent's balance and the side that contained the
deleted node.
--
Configure bugmail:
http://www.exim.org/bugzilla/userprefs.cgi?tab=email