From: Andrea Arcangeli <andrea@suse.de>
To: Kevin O'Connor <koconnor@cse.Buffalo.EDU>
Cc: Manfred Spraul <manfreds@colorfullife.com>,
Oliver Xymoron <oxymoron@waste.org>,
linux-mm@kvack.org, linux-kernel@vger.rutgers.edu,
Marc Lehmann <pcg@opengroup.org>,
Linus Torvalds <torvalds@transmeta.com>
Subject: Re: [patch] rbtrees [was Re: AVL trees vs. Red-Black trees]
Date: Tue, 30 Nov 1999 15:14:07 +0100 (CET) [thread overview]
Message-ID: <Pine.LNX.4.10.9911301506300.359-100000@alpha.random> (raw)
In-Reply-To: <19991130002755.A22847@armstrong.cse.Buffalo.EDU>
On Tue, 30 Nov 1999, Kevin O'Connor wrote:
>[..] I've got inserts working, but
>removes are becoming a myriad of special cases..
removes are trivial with rbtrees as you never need to compare nodes. All
the rebalancing is done in function of the node color (that is a private
information of each node). The same is true also for the
insert-rebalancing, but to do an insert you must first browse the tree to
do a normal ordered O(log(n)) insert before calling the rebalance (thus a
compare semantic on elements is necessary for the insert operation to
work).
Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/
prev parent reply other threads:[~1999-11-30 14:14 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
1999-11-27 12:59 AVL trees vs. Red-Black trees Kevin O'Connor
1999-11-28 2:57 ` Andrea Arcangeli
1999-11-28 5:29 ` Oliver Xymoron
1999-11-29 15:54 ` [patch] rbtrees [was Re: AVL trees vs. Red-Black trees] Andrea Arcangeli
1999-11-29 19:18 ` Manfred Spraul
1999-11-29 19:17 ` Andrea Arcangeli
1999-11-30 5:27 ` Kevin O'Connor
1999-11-30 14:14 ` Andrea Arcangeli [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Pine.LNX.4.10.9911301506300.359-100000@alpha.random \
--to=andrea@suse.de \
--cc=koconnor@cse.Buffalo.EDU \
--cc=linux-kernel@vger.rutgers.edu \
--cc=linux-mm@kvack.org \
--cc=manfreds@colorfullife.com \
--cc=oxymoron@waste.org \
--cc=pcg@opengroup.org \
--cc=torvalds@transmeta.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox