Index
> Windows > Sort numbers and record to binary treeGoto page 1, 2 Next |
| Author |
|
|
Roman 01 Aug 2013, 06:44
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 01 Aug 2013, 08:37
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 01 Aug 2013, 09:36
Wants to see the asm code that does this!
I'm talking about my example |
|||
|
01 Aug 2013, 09:36 |
|
|
JohnFound 01 Aug 2013, 10:12
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 01 Aug 2013, 13:12
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 01 Aug 2013, 13:39
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 01 Aug 2013, 20:05
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 01 Aug 2013, 22:21
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 01 Aug 2013, 22:35
Where did you find a good description of the algorithm?
|
|||
|
01 Aug 2013, 22:35 |
|
|
revolution 01 Aug 2013, 22:45
dogman wrote: Where did you find a good description of the algorithm? |
|||
|
01 Aug 2013, 22:45 |
|
|
dogman 01 Aug 2013, 23:22
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 02 Aug 2013, 04:49
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 02 Aug 2013, 07:00
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 02 Aug 2013, 10:18
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 02 Aug 2013, 13:54
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 02 Aug 2013, 22:51
Niklaus Wirth, "Algorithms + Data Structures = Programs".
|
|||
|
02 Aug 2013, 22:51 |
|
|
bitRAKE 03 Aug 2013, 00:34
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: |
|||
|
03 Aug 2013, 00:34 |
|
|
Roman 03 Aug 2013, 09:01
bitRAKE
Thanks you help ! |
|||
|
03 Aug 2013, 09:01 |
|
|
baldr 03 Aug 2013, 09:22
bitRAKE,
jc instead of natural jb was intended? |
|||
|
03 Aug 2013, 09:22 |
|
| Goto page 1, 2 Next < Last Thread | Next Thread > |
Forum Rules:
|