Acorn Arcade forums: Programming: balanced binary trees
| |
balanced binary trees |
| |
ramu_ak (12:55 12/3/2004)
monkeyson2 (19:45 12/3/2004)
Paolo Zaino (17:26 18/3/2004)
|
| |
|
ramu |
Message #52879, posted by ramu_ak at 12:55, 12/3/2004 |
Member
Posts: 1
|
hi all
I have a situation in which i maintain a balanced binary tree but the scenario is that I get numbers from 1 to n sequentially as 1,2,3...n as input one by one. So intially i have 1 in binary tree and then 1 and 2 in the tree and so on.. now the problem is that can i find a mapping between the number to be inserterd into the tree and the node in tree at which their might be a possible left rotation.. In my scenario only there might be only a single left rotation when an insertion is performed..
Thanx for any help in advance
bye |
| |
 [ Log in to reply ] |
| |
|
Phil Mellor |
Message #52887, posted by monkeyson2 at 19:45, 12/3/2004, in reply to message #52879 |
 Please don't let them make me be a monkey butler
Posts: 12380
|
Is this coursework? 
I'm sure I remember a question very similar to this in my functional programming module, but I can't remember off the top of me bonce what it was.
I'm sure somebody more capable will answer soon.  |
| |
[ Log in to reply ] |
| |
|
Paolo Fabio Zaino |
Message #53135, posted by Paolo Zaino at 17:26, 18/3/2004, in reply to message #52879 |
Member
Posts: 61
|
Hi, you didn't descrived well your tree but i try to help you anyway...
The insertion in a RB-Tree is executable in a O(lgn) time. You can use a tree-insert procedure like this:
Procedure tree-insert:
insert(T,z)
y <- NULL
x <- root[T]
WHILE x<>NULL
DO y <- x
IF key[z]<key[x] THEN
x <- left[x]
ELSE
x <- right[x]
p[z] <- y
IF y = NULL THEN
root[T] <- z
ELSE IF key[z]<key[y] THEN
left[y] <- z
ELSE
right[y] <- z
for insert a a x node in a T tree like if it was a common binary tree of search, then the inserted node will get red color. For warranty that any properties of the RB-Tree are mantained, you must re-arrange the modified tree recalculating the nodes and executing all rotations. This procedure could help you:
RB-Insert(T,x)
insert(T,x)
color[x] <- RED
WHILE x<>root[T] AND color[p[x]]=RED
DO IF p[x] = left[p[p[x]]] THEN
y <- right[p[p[x]]]
IF color[Y] = RED THEN
color[p[x]] <- BLACK (case 1)
color[y] <- BLACK (case 1)
color[p[p[x]]] <- RED (case 1)
x <- p[p[x]] (case 1)
ELSE IF x = right[p[x]] THEN
x <- p[x] (case 2)
LEFT-ROTATE(T,x) (case 2)
color[p[x]] <- BLACK (case 3)
color[p[p[x]]] <- RED (case 3)
RIGHT-ROTATE(T, p[p[x]]) (case 3)
ELSE (similar to the THEN with "RIGHT" and "LEFT" exchanged)
color[root[T]] <- black
This should work, i wrote it in a not real language cause you didn't specified any langauge you are using right now, and also because it would be more code to write lol 
Hope this help, cheers Paolo.
________
RISC OS Projects: https://github.com/RISC-OS-Community
RISC OS Blog: https://paolozaino.wordpress.com/category/risc-os/
Cheers! |
| |
[ Log in to reply ] |
| |
|
Acorn Arcade forums: Programming: balanced binary trees |
