{"_id":"@ballsxan/credit-balanced-bst","_rev":"2-a8ba8a3c4ef75405722aec5be832a548","name":"@ballsxan/credit-balanced-bst","dist-tags":{"latest":"0.1.1"},"versions":{"0.1.0":{"name":"@ballsxan/credit-balanced-bst","version":"0.1.0","_id":"@ballsxan/credit-balanced-bst@0.1.0","maintainers":[{"name":"ballsxan","email":"ballsxan@hotmail.com"}],"dist":{"shasum":"31871044d0109c461a5c0aace75e90b4d2423fda","tarball":"https://registry.npmjs.org/@ballsxan/credit-balanced-bst/-/credit-balanced-bst-0.1.0.tgz","fileCount":4,"integrity":"sha512-G+FaJeuczqvJ/SBjcIjLCRWicsL2tq4O25gNhYDZQ3zyu1SHZXUHwyn1Sea8GEQTzqRB8j+QMzAtfuD6Ovoyog==","signatures":[{"sig":"MEQCIHXIFv6wXGEAGn+xDfemX/fK7pxEgmE5U9mnQkazuzIUAiBAeOMkIO0K2eYoRVIRiPwZr3aTHvXHYqjGSjTpM+LwQQ==","keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U"}],"unpackedSize":29546},"main":"dist/index.cjs","module":"dist/index.mjs","exports":{"import":"./dist/index.mjs","require":"./dist/index.cjs"},"gitHead":"454cd507606aa7f825fd4751e1c48bbbedd97222","scripts":{"build":"rollup -c","prepublishOnly":"npm run build"},"_npmUser":{"name":"ballsxan","email":"ballsxan@hotmail.com"},"_npmVersion":"10.5.2","description":"A binary search tree implementation that maintains balance based on credit values rather than height, enabling efficient credit-based search operations.","directories":{},"_nodeVersion":"20.13.1","publishConfig":{"access":"public"},"_hasShrinkwrap":false,"devDependencies":{"rollup":"^4.53.3","@rollup/plugin-node-resolve":"^16.0.3"},"_npmOperationalInternal":{"tmp":"tmp/credit-balanced-bst_0.1.0_1765364313174_0.41631925505332457","host":"s3://npm-registry-packages-npm-production"}},"0.1.1":{"name":"@ballsxan/credit-balanced-bst","version":"0.1.1","main":"dist/credit-balanced-bst.umd.js","module":"dist/credit-balanced-bst.esm.js","scripts":{"build":"rollup -c","prepublishOnly":"npm run build"},"devDependencies":{"@rollup/plugin-node-resolve":"^16.0.3","rollup":"^4.53.3"},"exports":{"import":"./dist/credit-balanced-bst.esm.js","require":"./dist/credit-balanced-bst.umd.js"},"publishConfig":{"access":"public"},"_id":"@ballsxan/credit-balanced-bst@0.1.1","gitHead":"f49e93d5e654f4b63558bbc939c4329327f77d0b","description":"A binary search tree implementation that maintains balance based on credit values rather than height, enabling efficient credit-based search operations.","_nodeVersion":"20.13.1","_npmVersion":"10.5.2","dist":{"integrity":"sha512-Sfnqbp/eu+UuAfaf264BypxSDKA938JzIy9gO5WAlQuKLc7TDTA/aqRuj+MMduD4cxaDWrCF1x7bb9mk0WOevQ==","shasum":"dd15a3f2ce2b854f2ab74cd71d9afc1d677360f2","tarball":"https://registry.npmjs.org/@ballsxan/credit-balanced-bst/-/credit-balanced-bst-0.1.1.tgz","fileCount":4,"unpackedSize":29614,"signatures":[{"keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U","sig":"MEUCIDYKKwPNL9gw0fEakizjpLl95bAZbrbpo0Dj7n6mPtOcAiEAyi5CZdcIRU06vKNSv2ukHlILdoEpHXIKbyydROtrfzQ="}]},"_npmUser":{"name":"ballsxan","email":"ballsxan@hotmail.com"},"directories":{},"maintainers":[{"name":"ballsxan","email":"ballsxan@hotmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/credit-balanced-bst_0.1.1_1765370458882_0.2379160147244641"},"_hasShrinkwrap":false}},"time":{"created":"2025-12-10T10:58:33.099Z","modified":"2025-12-10T12:40:59.235Z","0.1.0":"2025-12-10T10:58:33.317Z","0.1.1":"2025-12-10T12:40:59.041Z"},"description":"A binary search tree implementation that maintains balance based on credit values rather than height, enabling efficient credit-based search operations.","maintainers":[{"name":"ballsxan","email":"ballsxan@hotmail.com"}],"readme":"# Credit Balanced Binary Search Tree\r\n\r\nA binary search tree implementation that maintains balance based on credit values rather than height, enabling efficient credit-based search operations.\r\n\r\n## 📋 Overview\r\n\r\nThis data structure combines the properties of a traditional BST (ordered by key) with a credit-based balancing mechanism. It's particularly useful for scenarios where you need to:\r\n\r\n- Find nodes based on cumulative credit sums in O(log n) time\r\n- Efficiently maintain and modify credit values\r\n- Perform prefix-based key operations\r\n\r\n## 🏗️ Structure\r\n\r\n### CreditNode Class\r\n```javascript\r\nclass CreditNode {\r\n    constructor(key, data, credit) {\r\n        this.key = key;          // Sorting key\r\n        this.data = data;        // Associated data\r\n        this.creditSum = credit; // Sum of credits in subtree\r\n        this.credit = credit;    // Node's own credit\r\n        this.left = null;        // Left child\r\n        this.right = null;       // Right child\r\n    }\r\n}\r\n```\r\n\r\n## 🚀 Features\r\n\r\n- **Dual Balancing**: Ordered by keys, balanced by credits\r\n- **Efficient Operations**: O(log n) for insert, delete, and credit-based search\r\n- **Credit Management**: Maintains cumulative sums for efficient range queries\r\n- **Prefix Search**: Find nodes by key prefixes\r\n\r\n## 📖 API Reference\r\n\r\n### Constructor\r\n```javascript\r\nconst tree = new CreditBalancedBST();\r\n```\r\n\r\n### Methods\r\n\r\n#### `insert(key, data, credit)`\r\nInserts a new node into the tree.\r\n\r\n#### `delete(key)`\r\nRemoves a node with the specified key.\r\n\r\n#### `findNodeByCredit(creditSum)`\r\nFinds the node where the cumulative credit of preceding nodes equals the specified sum.\r\n\r\n#### `findNodesByKey(key)`\r\nReturns all nodes with the specified key.\r\n\r\n#### `findNodesByPrefix(prefix = \"\")`\r\nFinds all nodes whose keys start with the given prefix.\r\n\r\n#### `updateCreditByKey(key, newCredit)`\r\nUpdates the credit value for nodes with the specified key.\r\n\r\n#### `getTotalCredit()`\r\nReturns the sum of all credits in the tree.\r\n\r\n#### `isEmpty()`\r\nChecks if the tree is empty.\r\n\r\n## 💡 Usage Examples\r\n\r\n```javascript\r\nconst tree = new CreditBalancedBST();\r\n\r\n// Insert nodes with credits\r\ntree.insert(\"user1\", { name: \"Alice\" }, 10);\r\ntree.insert(\"user2\", { name: \"Bob\" }, 20);\r\ntree.insert(\"user3\", { name: \"Charlie\" }, 15);\r\n\r\n// Find node by cumulative credit\r\nconst node = tree.findNodeByCredit(25); // Finds node where preceding credits sum to 25\r\n\r\n// Update credits\r\ntree.updateCreditByKey(\"user2\", 25);\r\n\r\n// Search by prefix\r\nconst users = tree.findNodesByPrefix(\"user\");\r\n\r\n// Get total credit\r\nconst total = tree.getTotalCredit(); // Returns 50\r\n```\r\n\r\n## ⚙️ Balancing Mechanism\r\n\r\nThe tree uses a credit-based balancing strategy that considers four possible rotations:\r\n\r\n- **LL**: Single right rotation\r\n- **LR**: Left-right double rotation  \r\n- **RR**: Single left rotation\r\n- **RL**: Right-left double rotation\r\n\r\nEach rotation is evaluated based on a cost function that minimizes credit imbalance between subtrees.\r\n\r\n## 🛠️ Implementation Details\r\n\r\n- **Credit Sum Maintenance**: Each node maintains the sum of credits in its subtree\r\n- **Recursive Operations**: Insertion, deletion, and updates use recursive traversal\r\n- **Error Checking**: Includes validation for credit sum consistency\r\n- **Memory Efficient**: Only stores necessary metadata for balancing\r\n\r\n## 📊 Performance\r\n\r\n| Operation | Time Complexity |\r\n|-----------|-----------------|\r\n| Insert | O(log n) |\r\n| Delete | O(log n) |\r\n| Credit Search | O(log n) |\r\n| Key Search | O(log n) |\r\n| Prefix Search | O(log n + m) |\r\n| Credit Update | O(log n) |\r\n\r\n## 🎯 Use Cases\r\n\r\n- **Weighted Random Selection**: Use credits as weights for probabilistic selection\r\n- **Resource Allocation**: Manage resources with credit-based priorities\r\n- **Load Balancing**: Distribute load based on capacity credits\r\n- **Priority Queues**: Implement efficient priority-based data structures\r\n\r\n## 📝 Notes\r\n\r\n- Keys are used for ordering and searching\r\n- Credits are used for balancing and cumulative operations\r\n- The tree automatically rebalances after insertions, deletions, and credit updates\r\n- All credit modifications should use `updateCreditByKey()` to maintain balance\r\n\r\n## 🔧 Development\r\n\r\nThe implementation uses an IIFE (Immediately Invoked Function Expression) to create a closure around private helper functions while exposing only the public API.\r\n","readmeFilename":"README.md"}