Balancing area trees: RE: Some jVNC design issues: (offtopic?) Re: vnc-list-digest V1 #481

[W. Brian Blevins]

Alastair,

First, thanks for your suggestion, it really helps to have one's ideas
challenged by colleagues.

My apologies if this is off-topic, but Quentin did invite my comments:

> 
> At the very least, it would be great if you had a chance to publish more
> about your experiences during this project.  It would make interesting
> reading!

Also, my apologies to everyone for leaving the entire digest attached to
the previous posts.  That I should have caught earlier.


> Date: Fri, 8 Oct 1999 09:22:52 +1300
> From: Alastair Carey <alastair "at" hsnz.co.nz>
> Subject: (Getting a little offtopic... :) RE: Some jVNC design issues
> 
> Without understanding your algorithm more, I can't be sure, so forgive me if
> this is a brain-dead suggestion... but is it possible that an AVL tree
> implementation, rather than a standard binary tree implementation, could
> solve your tree balancing problem and guarantee you O (log n) performance?

Balancing the tree would in fact be a great idea.  However, my
understanding
is that balanced trees have a "natural ordering" as the singular
constraint
on placing the children and shifting to achieve or maintain balance. 
While
this works well for rows in a database, it does not seem to apply to my
area tree idea.

The area tree has to maintain *two* constraints for each node:

  1- The rectangles to be drawn have to be drawn in the same order
generated
     by the application.  This I would call the "natural ordering",
since
     an inorder traversal of the tree is needed to properly render its
     contents.

  2- Rectangles in the "left" side of the tree are completely contained
within
     the parent node's rectangle on the frame buffer (or Image). 
Rectangles
     in the "right" side of the tree are completely outside the parent
rectangle.

Constraint number two is necessary to allow efficient removal of
previous
rectangles that have been obscured by later or newer rectangles.  Only
with
inside/outside decisions can I search directly to a subtree containing
rectangles located in or near the same location on the frame buffer
(Image).

If we lift constraint number two, then balancing the tree is certainly
possible.  Nowever, there must be an efficient way of removing
rectangles
that become obscured by later rectangles.  This is important to maintain
a
bounded size for both the memory footprint as well as network bandwidth
considerations.  Area trees will be extremely dynamic.  Everytime the UI
changes, the area tree will change.  Insertion appears to be the most
important operation, determining almost directly the performance of the
java.awt.Graphic object.  After insertion, inorder traversal for
conversion
to VNC wire protocol format would be the next most important operation.


> 
> - -----Original Message-----
> From: W. Brian Blevins [mailto:brian "at" tridia.com]
> Sent: Friday, 8 October 1999 7:03
> To: quentin "at" att.com; vnc-list "at" uk.research.att.com
> Subject: Some jVNC design issues: [Fwd: vnc-list-digest V1 #480]
> 
> a binary tree with an RFBRectangle at each node
> 
> ...
> 
> Inserting a new rectangle requires a search for the
> correct leaf, hopefully O(log n) time, although I have no way to
> guarantee the tree is balanced.  So, I'm back to O(n) worst case
> 


-- 
Brian 
----------------------------------------------------------------------------
Tridia's Mission: To always exceed our customers' expectations by
providing
the absolute best software products backed by outstanding technical
support
and customer service.  Please let us know how we are doing:
brian "at" tridia.com, vince "at" tridia.com (my manager) or
ceo-hotline "at" tridia.com.
----------------------------------------------------------------------------
W. Brian Blevins, Senior Software Engineer, Tridia Corporation
Diplom Informatiker, Sun Certified Java Programmer 1.1
brian "at" tridia.com
1000 Cobb Place Blvd, Suite 210; Kennesaw, GA 30144, USA

---------------------------------------------------------------------
The VNC mailing list - see http://www.uk.research.att.com/vnc/intouch.html
---------------------------------------------------------------------