Swapping in a Binary Search Tree, and Leaf-Only Trees

General Usage
, ,
1

Hi there,

I’m trying to implement the Bentley-Ottmann Algorithm in Julia. My problem is that I’ve only found out now that this Algorithm doesn’t utilize the normal implementation of a BST (AVL tree, RedBlack tree etc… found in DataStructures) in which there is an immutable ordering based on a comparator function. Specifically, the alg needs to be able to swap the place of elements in the ordering.

For context, the answer given in this stackoverflow is an explanation of exactly what I have run into.

Also an additional question of less importance. Is it possible to have leaf-only trees in the style of a B+ tree?

2

What if you delete and re-insert the elements that need to be swapped? This is O(log n) time per delete and insert.

As for leaf-only, I’m not sure what you mean. If you are looking for a balanced-tree data structure in which you can advance directly from a leaf to a consecutive leaf without hand-coding a tree traversal, consider the sorted containers in DataStructures.jl.

1 Like
3

Since the ordering is given by its sorted rank, in trying to get the previous and next elements in the tree I get the elements at index-1 and index+1, but deleting and reinserting doesn’t change the sorted rank(the index).

By leaf-only, I mean where only the leaf nodes have data(values) associated with them. The sorted containers dont work for I think the same reason as the tree implementations, they have the set ordering from the given isless function used.

According to the solution of this seperate post which is linked in the stackoverflow solution from main post, the CGAL and LEDA libraries use a leaf-only version of the binary tree and then doubly link the leaves together to form a progression.
Specifically the user writes doubly link the leaf nodes data items together and you have created a sorted sequence with the tree as a navigation structure to the linked list of items.

4

You can use SortedDict for this purpose. (I am the main maintainer of SortedDict but not the only maintainer. This usage is undocumented, so it is not guaranteed to work perpetually.) First, I suggest that you use rational numbers instead of Float64 for this purpose so that your data structures are not corrupted by roundoff error. The keys to the SortedDict are structs, say SlopeInter, that contain two rational numbers a and b, where a is a slope and b is an intercept. The comparison operator is something like the function

function Base.isless(p::SlopeInter,q::SlopeInter)
   global x
   y1 = p.a * x[] + p.b
   y2 = q.a * x[] + q.b
   return y1 < y2 || (y1 == y2 && p.a < q.a)
end

Here, x is a global variable defined like:

const x = Array{Rational{Int},0}(undef)

Now as you change x[] the sort order changes. This will corrupt the SortedDict unless the change to x[] does not affect the ordering of any keys currently in the structure. Therefore, when the algorithm detects a crossing, it should delete the two relevant items from the SortedDict, change x[], and then insert them anew.

EDIT: The version I posted earlier redefined isless for all types and probably break Julia because I forgot to qualify it with type names. I fixed this error just now.

1 Like