I had a test today and there was a question regarding how to merge two
AVL trees to form another AVL tree without using any AVL tree
operations. Some had done it by using an array, sorted the elements
and then formed the tree. Is there any sort of 'appropriate' algorithm
for doing this? (This seems sort of brute force). 4 6808 ga************* **@gmail.com wrote:
I had a test today and there was a question regarding how to merge two
AVL trees to form another AVL tree without using any AVL tree
operations.
Cannot be done, for exceedingly obvious reasons.
Some had done it by using an array, sorted the elements
and then formed the tree.
And how, then, did he "form the tree" without using any AVL tree
operations? It seems to me that building an AVL tree _is_ an AVL tree
operation.
Is there any sort of 'appropriate' algorithm for doing this?
Yes. Use the tools. Don't work around them.
Richard
On Apr 13, 1:23 am, gagan.singh.ar. ..@gmail.com wrote:
I had a test today and there was a question regarding how to merge two
AVL trees to form another AVL tree without using any AVL tree
operations. Some had done it by using an array, sorted the elements
and then formed the tree. Is there any sort of 'appropriate' algorithm
for doing this? (This seems sort of brute force).
You want news:comp.progr amming, where you will (no doubt) run into Ben
Pfaff (who is quite the AVL tree expert).
I guess that merging two properly formed AVL trees can be a lot more
efficient than simply cramming the smaller tree into the larger, one
object at a time, if there is a merge() function.
But your question is not a C question but an algorithm question.
While news:comp.progr amming is not exactly an algorithms group, it's
the closest thing that I know of.
On Apr 13, 3:01 pm, "user923005 " <dcor...@connx. comwrote:
On Apr 13, 1:23 am, gagan.singh.ar. ..@gmail.com wrote:
I had a test today and there was a question regarding how to merge two
AVL trees to form another AVL tree without using any AVL tree
operations. Some had done it by using an array, sorted the elements
and then formed the tree. Is there any sort of 'appropriate' algorithm
for doing this? (This seems sort of brute force).
You want news:comp.progr amming, where you will (no doubt) run into Ben
Pfaff (who is quite the AVL tree expert).
I guess that merging two properly formed AVL trees can be a lot more
efficient than simply cramming the smaller tree into the larger, one
object at a time, if there is a merge() function.
But your question is not a C question but an algorithm question.
While news:comp.progr amming is not exactly an algorithms group, it's
the closest thing that I know of.
This article http://groups.google.com/group/comp....46b2801c4f84e?
discusses how to build a balanced BST in O(n) time with O(log n) space
if you have input that's already sorted. So to merge _any_ set of
binary BSTs, just traverse them with in-order iterators, always
picking the least iterator value, and inserting this value into a new
balanced BST. It's easy to set the AVL flags on the fly as the new BST
is created or afterward in a separate O(n) pass.
"user923005 " <dc*****@connx. comwrites:
On Apr 13, 1:23 am, gagan.singh.ar. ..@gmail.com wrote:
>I had a test today and there was a question regarding how to merge two AVL trees to form another AVL tree without using any AVL tree operations. Some had done it by using an array, sorted the elements and then formed the tree. Is there any sort of 'appropriate' algorithm for doing this? (This seems sort of brute force).
You want news:comp.progr amming, where you will (no doubt) run into Ben
Pfaff (who is quite the AVL tree expert).
I think that this question is answered in Knuth. It's actually
a coding exercise that I've never properly explored. Perhaps I
will do so for the next version of libavl, should I ever acquire
a round tuit.
--
"To get the best out of this book, I strongly recommend that you read it."
--Richard Heathfield This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: William Ahern |
last post by:
I'm looking for resources on splitting and merging XML trees. Specifically,
on methods to pare large XML documents into smaller documents which can be
merged later.
Off of the top of my head, I can envision unions of node sets, and unions of
node text. But I know there's much more to the subject than that, if not
more alternatives than...
|
by: Klatuu |
last post by:
Whew, I've struggled my way through figuring out how to use XML to transport
data..now I can imagine what having a baby is like :)
But, I'm stuck now. I generate the XML (single table, no indexes) and
populate a dataset using READXML. I then merge the contents of that DS (call
it DS1) with a second DS (call it DS2) that I've created on the...
|
by: Patrick |
last post by:
I have got 2 XML documents, both of which conform to the same XSD Schema,
which define possible optional elements. The 2 XML documents contain 2
disjoint set of XML elements.
What is the best, easiest, most efficient way of merging the 2 XML
Documents? Can I use DataSet.Merge() facility in ADO.NET?? Any
pre-requisites?
Any other...
|
by: Emmett Power |
last post by:
Hi,
I have an Access table with a number of records which refer to the
same person but with data in different fields. So for example the
table would look like this:
Name..............Field 1...................Field 2
Fred Smith........Red
John Brown........Blue
Fred Smith...................................Truck
|
by: svdh |
last post by:
I have posed a question last saturday and have advanced alot in the
meantime. But I am still not there
Problem is that I try to merging various fields from various tables in
one document in Word
1. Query..I want to keep the fields seperatred. I do not want to sent
on field with all accumulated languages from one person to Word. Each...
| |
by: Naresh Narwani |
last post by:
Problem Summary:
Merging two different web applications into one create a problem for User
Controls.
Reason for merging two different Web Application:
To share non serializable object information between the Web applications.
Problem Statement:
Suppose I have two different web applications WebApp1 and WebApp2, both of
them have the
|
by: Ponnurangam |
last post by:
Hi,
I have created two styles from cssclass and merged first one with the second
one.
I then used the style for an Item.
The styles are not merging. Here is the code that I used
Dim mystyle1, mystyle2 As System.Web.UI.WebControls.Style
|
by: Dave Taylor |
last post by:
Is there a decent explanation of how menu merging with MDI forms work in
VB.NET? I've read through the online help and it still seems that whenever
I change menus around or whatever, it breaks everything. VB6, as repetitive
as it was to retype menus, was at least consistent. It seems that VB.NET
throws menu items wherever it feels like.
|
by: Jon Vaughan |
last post by:
I have 2 datasets , one returned as a dataset from a webservice and one
created client side form the same stored procedure that is returned from the
webservice. I then try and merge the data, but they dont seem to merge.
When I return a single table , this method works fine, but im returning 3
tables and the merge isnt happening. Is there...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language...
| |
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it. ...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...
| |