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
Roman

Joined: 21 Apr 2012
Posts: 1080
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: 3204 Time(s)

Last edited by Roman on 01 Aug 2013, 06:49; edited 2 times in total
01 Aug 2013, 06:41
Roman

Joined: 21 Apr 2012
Posts: 1080
Roman
I Use a binary tree to speed up the search.
And of course it should be on the FASM
01 Aug 2013, 06:44
tthsqe

Joined: 20 May 2009
Posts: 731
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))    ```
01 Aug 2013, 08:37
Roman

Joined: 21 Apr 2012
Posts: 1080
Roman
Wants to see the asm code that does this!
01 Aug 2013, 09:36
JohnFound

Joined: 16 Jun 2003
Posts: 3499
Location: Bulgaria
JohnFound
So, you want someone to write the code for you?
Unfortunately for you, this is not very likely to happen.
01 Aug 2013, 10:12
tthsqe

Joined: 20 May 2009
Posts: 731
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...
01 Aug 2013, 13:12
AsmGuru62

Joined: 28 Jan 2004
Posts: 1425
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...
01 Aug 2013, 13:39
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...
01 Aug 2013, 20:05
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 18182
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.
01 Aug 2013, 22:21
dogman

Joined: 18 Jul 2013
Posts: 114
dogman
Where did you find a good description of the algorithm?
01 Aug 2013, 22:35
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 18182
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.
01 Aug 2013, 22:45
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.
01 Aug 2013, 23:22
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 18182
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.
02 Aug 2013, 04:49
tthsqe

Joined: 20 May 2009
Posts: 731
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...
02 Aug 2013, 07:00
Roman

Joined: 21 Apr 2012
Posts: 1080
Roman
It seems the binary tree limited and uncomfortable in programming.
I'm sorry to bother , but thanks for the clarification
02 Aug 2013, 10:18
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.
02 Aug 2013, 13:54
baldr

Joined: 19 Mar 2008
Posts: 1651
baldr
Niklaus Wirth, "Algorithms + Data Structures = Programs".
02 Aug 2013, 22:51
bitRAKE

Joined: 21 Jul 2003
Posts: 3290
Location: vpcmipstrm
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
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:    ```
03 Aug 2013, 00:34
Roman

Joined: 21 Apr 2012
Posts: 1080
Roman
bitRAKE
Thanks you help !
03 Aug 2013, 09:01
baldr

Joined: 19 Mar 2008
Posts: 1651
baldr
bitRAKE,

jc instead of natural jb was intended?
03 Aug 2013, 09:22
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area
Goto page 1, 2  Next

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum