flat assembler
Message board for the users of flat assembler.

Index > Windows > Sort numbers and record to binary tree

Goto page 1, 2  Next
Author
Thread Post new topic Reply to topic
Roman



Joined: 21 Apr 2012
Posts: 605
Roman
I have data:

Nums dd 10,40,5,22,77,99,20,30,2,1,55,100,15,17

I need create binary tree (in binary tree nums must be sorting in the left part tree numbers less than 30 and in the right part tree numbers greater than 30) like this:


Description:
Filesize: 17.23 KB
Viewed: 1413 Time(s)

tree.jpg




Last edited by Roman on 01 Aug 2013, 06:49; edited 2 times in total
Post 01 Aug 2013, 06:41
View user's profile Send private message Reply with quote
Roman



Joined: 21 Apr 2012
Posts: 605
Roman
I Use a binary tree to speed up the search.
And of course it should be on the FASM Smile
Post 01 Aug 2013, 06:44
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
So you want to implement sets, of lets say n elements, via binary trees? In order to keep things efficient, you will need to keep the tree 'balanced', i.e. the depth of the tree should be of the order log(n). If you do it correctly(https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree) you should be able to achieve worst case complexities of
Code:
space: O(n)
insertion: O(log(n))
deletion: O(log(n))
search: O(log(n))    

Thus, in order to sort your numbers into a binary tree just read elements from your array and one-by-one perform the insertion operation.
This will indeed give the optimial complexity of O(n*log(n)) for a comparison sort on n numbers because
Code:
log(1) + log(2) + ... + log(n) ~ n*log(n) - n + log(2*pi*n)/2 + 1/(12*n) + ...
                               = O(n*log(n))    
Post 01 Aug 2013, 08:37
View user's profile Send private message Reply with quote
Roman



Joined: 21 Apr 2012
Posts: 605
Roman
Wants to see the asm code that does this!
I'm talking about my example
Post 01 Aug 2013, 09:36
View user's profile Send private message Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3502
Location: Bulgaria
JohnFound
So, you want someone to write the code for you?
Unfortunately for you, this is not very likely to happen. Wink
Post 01 Aug 2013, 10:12
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
Roman, are you trying to learn to program?
You have a computer, compiler, and debugger - why not give it a shot yourself?
You will learn much more this way...
Post 01 Aug 2013, 13:12
View user's profile Send private message Reply with quote
AsmGuru62



Joined: 28 Jan 2004
Posts: 1412
Location: Toronto, Canada
AsmGuru62
Roman, start with the structure defining just one of the tree items:
Code:
struct TREENODE
        PtrLeft         dd ?    ; Pointer to LEFT TREENODE
        PtrRight        dd ?    ; Pointer to RIGHT TREENODE
        Value           dd ?    ; Value inside THIS node
ends
    

After this you need the function which will dynamically allocate the TREENODE structure and fill it with data.
And so on...
Post 01 Aug 2013, 13:39
View user's profile Send private message Send e-mail Reply with quote
dogman



Joined: 18 Jul 2013
Posts: 114
dogman
Yeah this is pretty easy to do. You can figure it out and it's a lot of fun. The hard part is deleting nodes, and it's harder to balance the tree. I have some BST code but didn't do the balancing part yet. Anybody done that? Looks pretty heavy...
Post 01 Aug 2013, 20:05
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17338
Location: In your JS exploiting you and your system
revolution
I use red-black trees usually. Not perfectly balanced all the time but quick to insert and delete. If a lot of operations are updating the tree and fewer operations to scan the tree then this might be a suitable algorithm to use.
Post 01 Aug 2013, 22:21
View user's profile Send private message Visit poster's website Reply with quote
dogman



Joined: 18 Jul 2013
Posts: 114
dogman
Where did you find a good description of the algorithm?
Post 01 Aug 2013, 22:35
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17338
Location: In your JS exploiting you and your system
revolution
dogman wrote:
Where did you find a good description of the algorithm?
I used Google. I don't have a handy link available since I was searching this over 10 years ago and all my saved links have long since disappeared.
Post 01 Aug 2013, 22:45
View user's profile Send private message Visit poster's website Reply with quote
dogman



Joined: 18 Jul 2013
Posts: 114
dogman
All the stuff I found looks either too general or is not explained very well. I will have to keep looking.
Post 01 Aug 2013, 23:22
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17338
Location: In your JS exploiting you and your system
revolution
IIRC I think I had a found good demo of RB-tree working code using Java. I mostly just ported the relevant parts of the Java code to assembly.

I also discovered there are a lot of broken implementations of RB-tree code that fail to leave a good tree when deleting certain nodes. Make sure you find a description and/or code example that enumerates all the deletion possibilities.
Post 02 Aug 2013, 04:49
View user's profile Send private message Visit poster's website Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
I'm thinking that the TREENODE struct should have a few more members:
Code:
struct TREENODE 
        PtrLeft         dd ?    ; Pointer to LEFT TREENODE, 
        PtrRight        dd ?    ; Pointer to RIGHT TREENODE
        PtrParent       dd ?    ; Pointer to PARENT TREENODE
        Depth           dd ?    ; depth of subtree rooted at THIS node (= 1+max(left.Depth,right.Depth))
        Value           dd ?    ; Value inside THIS node 
ends     


Let say that a node x is unbalanced if abs(x.left.Depth-x.right.Depth)>c for some fixed natural number c (c=1 is OK).
For insertion, you can insert the node into the tree as usual, possibly leaving a tree with an unbalanced node.
Note that the number of unbalanced nodes is << log(n) and these resulting unbalanced nodes must all occure as ancestors of the inserted node.


EX: (nodes are marked with their Depth member)
Original balanced tree (c=1):
Code:
                    4
                   / \
                  /   \
                 /     2
                3     / \
               / \   1   1
              /   1   \   \
             /   / \   0   0
            2   0   0
           / \
          /   \
         1     1
        / \   / \
       0   0 0   0       




tree after inserting a node and updating the Depth member along the ancestor line, unbalanced nodes have ().
Code:
                   (5)
                   / \
                  /   \
                 /     2
               (4)    / \
               / \   1   1
              /   1   \   \
             /   / \   0   0
            3   0   0
           / \
          /   \
         1     2
        / \   / \
       0   0 1   0
            /
           0                     


You will need to do some rotations to fix the (4) and then the (5). They are straighforward but messy for me to describe here...
Post 02 Aug 2013, 07:00
View user's profile Send private message Reply with quote
Roman



Joined: 21 Apr 2012
Posts: 605
Roman
It seems the binary tree limited and uncomfortable in programming.
I'm sorry to bother , but thanks for the clarification
Post 02 Aug 2013, 10:18
View user's profile Send private message Reply with quote
dogman



Joined: 18 Jul 2013
Posts: 114
dogman
After queues and stacks and linked lists, BSTs and general trees are one of the most important data structures in all of computing. Most databases and filesystems are based on search trees. The basic case of BST is not hard to code. The balancing is hard to understand and hard to code but it's only necessary for production software. You can do a lot with unbalanced BSTs. There are some libraries for balanced trees available if you don't want to write it yourself.
Post 02 Aug 2013, 13:54
View user's profile Send private message Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
Niklaus Wirth, "Algorithms + Data Structures = Programs".
Post 02 Aug 2013, 22:51
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
Static tree...
Code:
    mov edi,Nums
    movzx edx,byte[edi] ; index limit
    mov ecx,1
    lodsb               ; byte to find
.branch:
    cmp [edi+ecx],al
    jz .match
    adc ecx,ecx
    cmp ecx,edx
    jc .branch
.no_match


.match:


Nums:
  db .end - $
  db 22,10,77,2,17,40,100,1,5,15,20,30,55,99
.end:    
Post 03 Aug 2013, 00:34
View user's profile Send private message Visit poster's website Reply with quote
Roman



Joined: 21 Apr 2012
Posts: 605
Roman
bitRAKE
Thanks you help !
Post 03 Aug 2013, 09:01
View user's profile Send private message Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
bitRAKE,

jc instead of natural jb was intended?
Post 03 Aug 2013, 09:22
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2  Next

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.