OSDev.org
https://forum.osdev.org/

AVL Removal Advice?
https://forum.osdev.org/viewtopic.php?f=13&t=13421		 Page 1 of 1
Author:  elderK [ Sat Mar 24, 2007 6:58 pm ]
Post subject:  AVL Removal Advice?
Yes, I know, It's me again ... posting about AVL trees.

Point is, What is a good way to gauge AVL tree performance, like... function performance for insertion / removal.

And, whats a good idea for removal?

My insertion routine is simple. I traverse down to the insertion point, connect the new node, then scale back up the tree updating the balances. If any balance becomes critical rebalance, if any node becomes completely balanced after the balance update, I stop scaling up the tree.

Removal is going to be much more complicated. :(
So, I would really really ... love the chance to talk in real time with a person in-the-know with this structure.

Alternatively, I will post my Removal idea here, for feedback / advice.

~Zeii.
Author:  ces_mohab [ Sun Mar 25, 2007 12:56 am ]
Post subject:  Re: AVL Removal Advice?
zeii wrote:
Point is, What is a good way to gauge AVL tree performance, like... function performance for insertion / removal.

And, whats a good idea for removal?

Removal is going to be much more complicated. :(
So, I would really really ... love the chance to talk in real time with a person in-the-know with this structure.

Alternatively, I will post my Removal idea here, for feedback / advice.

~Zeii.


I have implemented an AVL tree. I can post code if you want but i doubt using recursive structures in OS development. because of stack overflow bad bugs :( . is your implementation recursive :?:

Any way if the data to be inserted in an AVL tree are randomly distributed then no advantage in AVL than binary search trees. while imagine inserting sorted elements in A binary search tree :!: degeneration will occur and binary search tree will be a linked list which is the advantage of AVL trees.
Author:  elderK [ Sun Mar 25, 2007 5:05 am ]
Post subject: 
mohab, Id appreciate talking to you in real time, if possible.

Im implementing AVL Iterative. @!#$ Recursive code man!
My kernel only has a 4 Kilobyte stack! :P

~Zeii
Author:  mystran [ Sun Mar 25, 2007 11:04 pm ]
Post subject: 
Your implementation is truly iterative without having a manually managed stack, I assume?

I guess you could get some off-the-shelf AVL trees, then compare performance with your implementation with largish amounts of test data. I don't think there's much better way..
Author:  ces_mohab [ Mon Mar 26, 2007 11:49 am ]
Post subject: 
zeii wrote:
Im implementing AVL Iterative.


Weldone :!:

OK i will give you a key for deleting a node in an AVL tree.
deletion is very symmetric to insertion.

zeii wrote:
mohab, Id appreciate talking to you in real time, if possible.


if you want sent me your yahoo! id private mail.
Author:  elderK [ Sun Apr 15, 2007 11:07 pm ]
Post subject: 
Hey all, yes, it has been a long time.

Ces, Id appreciate it if you could test out my AVL implementation?

:)

~Zeii.
Author:  elderK [ Mon Apr 16, 2007 1:07 pm ]
Post subject: 
Hey people, if possible... Id like to see someones implementation of an AVL tree, just to help me debug my own.

Id appreciate implementations of the Iterative type.
Thanks!

~zeii.
ps: Tonight, closest attempt yet - Only subtree-node removal is killing me now... and its very nearly working... soooo .... close :(
Author:  mystran [ Mon Apr 16, 2007 2:00 pm ]
Post subject: 
Depending on what you're going to use the tree for, one simple method for doing deletions is to just mark the nodes as deleted. Obviously that keeps the tree as big as it was, but you can reuse the deleted nodes next time you need to store something where it was. But I guess you probably want a real deletion, right?

The easiest method I can think for actually doing the deletion, is to move the node to be deleted to a point where it has at most once children (one or none). Trivially this is done by moving the node all the way down until it's a leaf. While moving (and looking for?) the node down, there's two things to take care of: only the node-to-be-removed may violate the normal BST order (after it's deleted the tree must be BST again), and when rebalancing (during the move), take into account that the to-be-deleted node doesn't count as a node (since after it has been deleted, the tree must be in balance... might be you must start rotating even before you've found the node to avoid moving back up).

I didn't prove that the above strategy actually works. Specifically, I didn't figure out how to make sure that balance can be preserved. But it obviously works for a normal (unbalanced) BST, so I guess (well it's an "educated guess") one can do the necessary rotations on the way down to keep it an AVL.
Author:  elderK [ Mon Apr 16, 2007 4:07 pm ]
Post subject: 
Hey, Thanks mystran.

Sequential insertion works fine (Ascending). Descending seems to check out okay.

Removal ends up messing up... I believe it is in the rebalance calls.

I post the code up here, in hopes of mysterious salvation because my brain simply cant take any more. Ive given it all I can, and Im stuck.

If anyone manages to find the bug, or some bugs... please let me know!

~Zeii

Attachments:
abm_main.c [12.45 KiB]
Downloaded 42 times
Author:  elderK [ Tue Apr 17, 2007 1:54 pm ]
Post subject: 
New attempt, going a lot better.
Working on Deletion now.
(Leaf is going well, Insertion works nicely - Random and sequential insertion with no problems, tree checks out fine).

Problem is this... (Balances are in Brackets)

1(+1)
0(0) 3(0)
2(0) 4(0)


We want to remove Element 0.
Now problem, my Implementation says... intermediately, it goes into this step:

1(+2)
3(0)
2(0) 4(0)

Oh No! Says the Implementation, We are Right Critical! We need to rebalance!. So, It tries - It checks the Right Subtree.

Okay, It says! This is not a crazy Right-Left-Right or Right-Left-Left case, it s just a cheerful Right-Right case! (Because Node 3 balance is ZERO!).

So, It rotates right only and winds up with this.

3(0)
1(0) 4(0)
2(0)

As you can see, The balances for the nodes are all screwed up.
It should be :


3(-1)
1(1) 4(0)
2(0)

Any ideas? Id really appreciate them.

~zeii.
Author:  Combuster [ Tue Apr 17, 2007 3:27 pm ]
Post subject: 
Whatever your rotation code does, it does not adjust/compute the new weights appropriately. Most likely it just assumes that the weight of node 3 = +1: after an insert that assumption holds or you wouldn't trigger a right-right rotation, unfortunately, it doesnt necessarily hold after an delete. (Excercise for the reader to find out why)

Code:
  1 (+2)
/ \
a   3 (0)
   / \
  2   4
/ \ / \
     b c

next you rotate over 1-3-4, which is ok (1-3-2 would work as well, but here you can choose)

we know that
h(a) = h(3)-2
h(2) = h(3)-1 or h(3)-2
h(1) = h(3)+1
h(4) = h(3)-1
h(b) = h(3)-2 or h(3)-3
h(c) = h(3)-2 or h(3)-3

after rotation,
Code:
   3
  / \
1   4
/ \ / \
a 2 b c

the heights and balances of a, 2, b, and c remain the same. we can deduce the new balances:
the balance of 1 is 0 (if 2 was smaller than 4), i.e. if the balance of 3 was +1, otherwise its +1 (2 was of equal size)
in pseudocode, 1.new.balance = 1 - 3.old.balance

the new height of node 1 is h(2) + 1 = h(3) or h(3) - 1, or h(3) - 1 + 1.new.balance

the leaves/subtrees of node 4 haven't changed, so the balance and height of 4 remain equal

we know the heights of both subtrees of the 3.new, so we can compute the balance:
its either 0 (if 2 was smaller than 4) or -1 (if 2 equals 4 in height)

the height of the entire subtree shrinks when subtree 2 is smaller than subtree 4, i.e. if the old balance of 3 equals +1. In this case you need to recurse upward to adjust weights higher up the tree

summarized the new balances can be computed as follows

4.new.balance = 4.old.balance (i.e. unchanged)
1.new.balance = 1 - 3.old.balance
3.new.balance = -1 + 3.old.balance
recurse = (3.old.balance == +1)

when doing a right-right rotation.

i'll leave the exercise of figuring out the maths for the other three rotations to you.
Author:  elderK [ Wed Apr 18, 2007 11:05 am ]
Post subject: 
:D Combusterrrr!
I DID IT:D
I THINK :D

I finally got it, I think!

:D My test cases so far check out okay.

:D Id appreciate a codereview, feedback on how I could improve it and make the code much less ugly. :D

~Zeii.

Attachments:
avlmk5_main.c [13.54 KiB]
Downloaded 64 times
Page 1 of 1 All times are UTC - 6 hours
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/