Whats the difference between these two trees?

[cunning slate]

<@&987246584574140416> please have a look, thanks.

[inner bone]

Both are balanced binary trees?

but the one published in 1972 apparently is not considered a binary search tree

[analog locust]

If you always have a branching factor of two, thats a binary search tree

if you have a higher branching factor, thats still a search tree just not a binary one

[inner bone]

so what was actually accomplished by making it a red-black tree? both trees have the same time complexity

[analog locust]

because trees need to stay kinda "balanced"

and red black trees, the way they rebalance, is more efficient

https://cs.stackexchange.com/questions/41969/why-are-red-black-trees-so-popular

at least, i think thats the point

[inner bone]

as a real world devloper have you implemented a red black tree or seen any bit of real world usage of this structure?

[analog locust]

its used behind the scenes in stuff

i never implemented it myself

[boreal mirage]

Red black trees are height balanced so search time has a limit. If you have the sedgewick algorithm book then there it is explained in detail including how to implement. If I recall it's implemented with 2-3 trees and those are implemented as two binary nodes.

Anyway, real world use. For transport logistics, it's important to fill a space with as much cargo as possible to maximize profit. There are many algorithms for packing but there is one called Best Fit. It goes something like this: Put the next package in the fullest container that still fits the next package size. To find the fullest container that fits, you search a red black tree arranged by remaining space, which is changing all the time after every package assigned. If you didn't have a height balanced tree, the tree can end up having spikes of linked lists that you would have to traverse.

[inner bone]

this is amazing. thank you for sharing that

from what ive learned so far it seems like redblack tree can become inefficient in larger data sets since it would require lots of rotations. Is that true?

[boreal mirage]

I don't know what the amortized runtime is. There's a wiki page for just about every algorithm that will probably mention it.

[inner bone]

So, I've implemented a reblack tree from scratch. is this an appropriate way to capture the time it takes to run? java public class Driver { public static void main(String[] args) { RedBlackTree tree = new RedBlackTree(); long start = System.nanoTime(); tree.insertNode(2); long end = System.nanoTime(); System.out.println("Time elapsed: " + (end-start));

[cunning slate]

Detected code, here are some useful tools:

Formatted code

public class Driver {
  public static void main(String[] args) {
    RedBlackTree tree = new RedBlackTree();
    long start = System.nanoTime();
    tree.insertNode(2);
    long end = System.nanoTime();
    System.out.println("Time elapsed: " + (end - start));

[inner bone]

im going to scale it to take in a csv file that has hundreds of numbers to insert but i just wanted to make sure i have a base down before adding that

[split tartan]

Use a tombstone when nulls are allowed, use nulls when they aren't