473,322 Members | 1,911 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Binary search tree

Hi,

I have to get list of URLs one by one and to find the URLs that I have
more than one time(can't be more than twice).

I thought to put them into binary search tree, this way they'll be
sorted and I'll be able to check if the URL already exist.

Couldn't find any python library that implements trees.
Is there some library of this kind in python? Or can I find it
somewhere else?

Nov 9 '07 #1
5 4107
ma*********@gmail.com wrote:
Hi,

I have to get list of URLs one by one and to find the URLs that I have
more than one time(can't be more than twice).

I thought to put them into binary search tree, this way they'll be
sorted and I'll be able to check if the URL already exist.

Couldn't find any python library that implements trees.
Is there some library of this kind in python? Or can I find it
somewhere else?
Put them into a set. You can check for existence (very fast) and at the end it
is easy to sort.

-Larry
Nov 9 '07 #2
On 2007-11-09, Larry Bates <la*********@websafe.comwrote:
ma*********@gmail.com wrote:
>I have to get list of URLs one by one and to find the URLs
that I have more than one time(can't be more than twice).

I thought to put them into binary search tree, this way
they'll be sorted and I'll be able to check if the URL already
exist.

Couldn't find any python library that implements trees. Is
there some library of this kind in python? Or can I find it
somewhere else?

Put them into a set. You can check for existence (very fast)
and at the end it is easy to sort.
The set is likely the way to go.

Python's library support for binary search trees consists of the
bisect module.

--
Neil Cerutti
Ask about our plans for owning your home --sign at mortgage company
Nov 9 '07 #3
On Nov 9, 4:06 pm, maxim.no...@gmail.com wrote:
Hi,

I have to get list of URLs one by one and to find the URLs that I have
more than one time(can't be more than twice).

I thought to put them into binary search tree, this way they'll be
sorted and I'll be able to check if the URL already exist.

Couldn't find any python library that implements trees.
Is there some library of this kind in python? Or can I find it
somewhere else?
Can you use set() or set.difference()?

Nov 9 '07 #4
ma*********@gmail.com a écrit :
Hi,

I have to get list of URLs one by one and to find the URLs that I have
more than one time(can't be more than twice).

I thought to put them into binary search tree, this way they'll be
sorted and I'll be able to check if the URL already exist.
What about a set ?

s = set()
for url in urls:
if url in s:
print "already have ", url
else:
set.add(url)

Nov 9 '07 #5
On Nov 9, 11:45 pm, Bruno Desthuilliers
<bdesth.quelquech...@free.quelquepart.frwrote:
maxim.no...@gmail.com a écrit :
Hi,
I have to get list of URLs one by one and to find the URLs that I have
more than one time(can't be more than twice).
I thought to put them into binary search tree, this way they'll be
sorted and I'll be able to check if the URL already exist.

What about a set ?

s = set()
for url in urls:
if url in s:
print "already have ", url
else:
set.add(url)
Interesting. For this case I usually used dicts. As in:

d = {}
for url in urls:
if url in d:
print "already have ", url
else:
d[url] = 1

Now, I can see that this method has some superfluous data (the `1`
that is assigned to the dict). So I suppose this is less memory
efficient. But is this slower then? As both implementations use hashes
of the URL to access the data. Just asking out of curiosity ;)

Nov 12 '07 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

0
by: j | last post by:
Hi, Anyone out there with binary search tree experience. Working on a project due tomorrow and really stuck. We need a function that splits a binary tree into a bigger one and smaller one(for a...
3
by: tsunami | last post by:
hi all; I have an array and want to insert all the elements from this array to a binary search tree.That array is an object of the class of a stringtype which includes overloaded "< > = =="...
4
by: Tarique Jawed | last post by:
Alright I needed some help regarding a removal of a binary search tree. Yes its for a class, and yes I have tried working on it on my own, so no patronizing please. I have most of the code working,...
4
by: mathon | last post by:
Hello, im currently implementing a binary search tree means, that a greater number than root will be added as right child and a less number as left child. My insert function looks currently like...
1
by: mathon | last post by:
hi, now i facing a problem which i do not know how to solve it...:( My binary search tree structures stores a double number in every node, whereby a higher number is appended as right child...
1
by: hn.ft.pris | last post by:
I have the following code: Tree.h defines a simple binary search tree node structure ########## FILE Tree.h ################ #ifndef TREE_H #define TREE_H //using namespace std; template...
2
by: pankajit09 | last post by:
Hello, I have a textbox in which I have to enter a string of numbers. The numbers are to be converted in to a Binary Search Tree and then I have to determine whether the BST is a --> 1....
5
gekko3558
by: gekko3558 | last post by:
I am writing a simple binary search tree (nodes are int nodes) with a BSTNode class and a BST class. I have followed the instructions from my C++ book, and now I am trying to get a remove method...
11
by: Defected | last post by:
Hi, How i can create a Binary Search Tree with a class ? thanks
2
by: Defected | last post by:
Hi, How i can implement a main function with this Binary Search Tree. thanks for help. is this code corrected ? #include<iostream>
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.