What should I choose for an easy to code balanced binary search tree?
I would like to know which balanced BST would be easy to code in C++, and still have a complexity roughly equal to O(logn).
I've already tried Red Black trees, but would like an alternative that is less complex to code. I have worked with Treaps in the past, but am interested in exploring options that either perform better or are easier to implement.
What are your suggestions?
AVL trees generally perform better than Treaps in my experience, and they're not any harder to implement.
They work by rotating branches of the tree that become unbalanced after any insertion or deletion. This guarantees that they will have perfect balance so they can't be "tricked" by strange data.
Treaps on the other hand are distributed randomly, which for large data sets is close to balanced, but you still don't get that perfect O(logn). Furthermore you could just happen to come across a data set that inserts in a very unbalanced way, and your access time can get close to O(n).
Check out wikipedia's page for more info: en.wikipedia.org/wiki/Avl_tree
- Segmentation fault when converting char * to char **
- What's the difference between "C system calls" and "C library routines"?
- C standard - const qualification of struct members
- Conventions/good ways to initialize variables with default/NULL values
- why there are int56_t in clang c header file, and how to use them
- How to watch char values of strings pointed by a pointer to pointers in debugger mode of VSCode
- How to repeat a char using printf?
- Is left shifting a long long considered Undefined Behavior in C?
- String buffer gets skipped on the last loop iteration
- Unsigned int weird behavior with Loops in C
- How are Linked Lists implemented in the Ready Queue before moving onto the scheduler during the PCB implementation?
- How do C/C++/Objective-C compare with C# when it comes to using libraries?
- Why no switch on pointers?
- Similar syntax causes strange, repeated compile errors when building PHP from source on Windows
- Segmentation fault in C shellcode x64
- Where is the documentation for the XRandr header?
- i*=j ==x and i=i*j ==x behaving differently in C
- How can I make objcopy -Obinary append every text section?
- timespec equivalent for windows
- Register keyword: stack or heap
- Detect a parenthesized macro argument in C
- Modifying (stealing) Linux syscalls using kprobe
- Python's bz2 module not compiled by default
- ASCII file encoding with 16-bit bytes
- GtkContainer/GtkWidget maximum width
- AF-XDP: Implement Shared Umem sockets
- Are there known implementations of the CIEDE2000 or CIE94 Delta-E color difference calculation algorithm?
- ssh_channel_request_exec is not working without ssh_channel_read
- Are DHCP options ordered?
- Can't install apk using adb