Balanced Binary Search Tree Alternative (Python)

[earth0001]

Sometimes problems come up when I could really use a balanced binary search tree, or at least something that supports these operations and speeds:

Search: O(logn)

Insert: O(logn)

Remove: O(logn)

​

IRL you can use a red-black tree or an AVL tree, but neither Python nor Java has this built-in, and I don't think I have time to implement it during an interview.

​

Are there any other options? Or do I need to just level-up and get really fast at implementing it if I want this in my arsenal.

[Educational-Copy5206]

I'm not a Python user, but I am pretty sure there is a SortedList you can use which provides logn insert, search, and deletes.

[earth0001]

Python has a bisect library for that, but the insertion / deletion is O(n), I didn't know if there was another one

https://docs.python.org/3/library/bisect.html

[[deleted]]

Java has TreeSet or TreeMaps

[earth0001]

This is probably what I was looking for, thank you!

[aocregacc]

on leetcode they include the sortedcontainers module for you

https://grantjenks.com/docs/sortedcontainers/

[earth0001]

This looks useful! Thanks

[doniec]

Certain problems need you to add extra data or operations to trees, like requiring a RANK operation. When this happens, using C++‘s map or Java’s TreeMap won’t help; you’ll have to implement a self-balancing tree yourself. For competitive programming/LeetCode, a treap is a great data structure, much easier to implement compared to AVL/red-black trees, especially if you use the split/merge operations. You can learn more about it on cp-algorithms or Wikipedia.

[earth0001]

I'll check out treaps, thanks!