What is the point of a binary tree? When or why would i ever use one?

Window Managers (BSPWM)

and they are considered to be one of the worst serious implementations around, so there's that

Huffman coding

red black tree

>inefficient naive implementation of huffman coding in intro textbooks
ftfy

i used it while writing an interpreter to create a symbol table in my language, it's a very simple and easy way to implement a pretty efficient (or atleast efficient enough) associative array.

The idea is to divide and conquer. At ever step further into the tree you can just discard half of it. Then another half, and another half... O(ln(n)) in short, which is pretty much always awesome.

Attached: 1454552768970.jpg (720x849, 126K)

>red black tree
Has anyone of you faggots ever tried to implement this, and not just the most basic operations? No? Of course not. Fuck those rotations.

Attached: zoidyslow.gif (200x200, 103K)

maybe programing shouldn't be your main occupation

>HEY WHY ARE YOU ASKING QUESTIONS AND NOT FOLLOWING EVERYTHING BLINDLY REEEE PROGRAMMING IS NOT FOR YOU REEEE

Attached: 1513007204881.png (866x900, 95K)

i know rite? "binary" trees? hello? it's fucking current year you alt-right bigots. stop being so fucking transphobic, the entire industry is moving to fluid trees, with or without you, and hopefully without
----- Sent from my office at Diversity Inc. -----

Seriously, why would anyone do a binary tree when a finger tree exists?

anyone who's taken a data structures class has had to do this....... AVL trees are actually more difficult, anyone who disagrees just has been taught wrong

Hence why college is a meme, because most of the shit they "teach" you is useless or busy work to keep you there for 4 years, when they could get you out in less than 2 if they wanted.

Java implements it HashMap using a RBT.

stackoverflow.com/questions/30164087/how-does-java-8s-hashmap-degenerate-to-balanced-trees-when-many-keys-have-the-s/30180593

you are retarded
AVL is easier because of symmetry of operations involved and does not involve that coloring bullshit. I cannot and will not learn implementing RB Trees even if they are O(1) insertions amortized

It might seem pointless but binary tree structures
are useful for logarithmic updates and queries. They are a middle ground between

O(N) update + O(1) query
and
O(1) update + O(N) query

See Heaps, BSTs, Segment Trees, etc

read Sedgewick's paper on left leaning red black trees. you'll learn that they are a just a way of encoding a 2-3 tree in a manner where normal BST searches / traversals still work. like I said, it means you've been taught wrong if you think having to store balance factor is less complicated than a single bit for color.
>are O(1) insertions amortized
you are thinking of something else because a RB insertion is still log(N)

you can do O(1) update and O(1) query with hashing

For storing big amount of data, so that you can search faster..

Trees are used everywhere and are an essential way we group information. If you're using OOP, then you're literally just creating a tree of objects that extend each other. As others have mentioned, spell checking, searching, and anything that requires you to limit your search and hone in on an attribute will require a tree. I used one for a small game, it's called a quadtree and it requires you to split the map into 4 parts repeatedly to minimize collision checks. Point is: Trees are cool and important.

Binary trees are just used to get people comfortable with trees anyways.

Search efficiency is log(n) in the worst case. Also, it allows you to store data without having to worry about ordering it as you store it.

RB is still O(log(N)), man. RB trees have faster insert/delete by a constant factor, and AVL trees have faster search by a constant factor.

Find my name in the phone book.
My name is Zim Zamson.
No binary search.
Linear search only.

I just use simple linked list for everything, computers nowadays are fast enough anyway, any other data structures are nerd shit.

Attached: 1550469465574.png (640x360, 278K)

to sort niggers for lynching

A sorted array with dichotomy is the exact same thing, but it's faster.

organizational chart

usually on visibility of data on whos under what group of users

Indexes in databases

>all these zoomer CS undergrads thinking binary trees are useful when any serious real world data strucutre will either be a B-tree or a hash table
I bet you also think linked lists are useful.

red and black tree are where I realized I wasn't as bright as I thought

Attached: 1550717417811.jpg (1242x1215, 797K)

Read again, computing an aggregation over any arbitrary subrange like sum, min, max of any subarray with data update operations mixed in. Also
> implying Hashtable inserts are O(1)

You both are right, I made a mistake by not mentioning extra conditions. Insertions are still LogN but when you do amortized analysis on consecutive inserts, you get O(1) per insert [1]

And no, I have not been taught wrong, I just prefer AVL for implementing because symmetry of balancing operations. Otherwise, I go with RB Trees

[1] Page 13 Top from cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

Red black binary search trees often perform better than hashmaps, one example.

how do you insert in O(log n) time?

Binary trees are really good for competitional programming

fOr kEepIng a sOrTed liSt

Binary trees allow for O(log n) search time and range based queries. Some database systems employ B-Tree implementations (which uses more than 2 child nodes) because reading from disk is expensive. It's especially useful for range based queries.

AVL trees are fucking easy

As a special and practical case of high dimensional floating point data compression.
See paper:
proceedings.mlr.press/v28/song13.pdf

AVL is the most simple balanced binary tree

Imagine being a treelet

abstract syntax tree

this

that

Attached: whiteboard.jpg (674x674, 20K)

So underage NPC high school students feel like big boy programmers when writing some shitty B-tree lookup algorithm for competitive programming - they can't write meaningful software and this the closest they'll get to writing "difficult" code.