search

zrwusa / data-structure-typed

Javascript Data Structure & TypeScript Data Structure. Heap, Binary Tree, Red Black Tree, Linked List, Deque, Trie, HashMap, Directed Graph, Undirected Graph, Binary Search Tree, AVL Tree, Priority Queue, Graph, Queue, Tree Multiset, Singly Linked List, Doubly Linked List, Max Heap, Max Priority Queue, Min Heap, Min Priority Queue, Stack.
https://data-structure-typed-docs.vercel.app
MIT License
114 stars 8 forks source link

Inserting nodes into a Red-Black Tree in sorted order #78

Closed zrwusa closed 7 months ago

zrwusa commented 8 months ago

Describe the bug When inserting nodes into a Red-Black Tree in sorted order, the tree collapses into a structure resembling a linked list. It is essential to optimize for this scenario; otherwise, the degenerated Red-Black Tree loses any advantages of being a balanced binary tree.

To Reproduce Steps to reproduce the behavior:

  const treeMS = new RbTreeMultimap<number, number>();
   for (let i = 0; i < inputSize; i++) {
      treeMS.add(i);
    }
zrwusa commented 7 months ago

Reimplemented the Red-Black Tree to replace the original classic Red-Black Tree. This issue has been resolved in version 1.50.9.