@raikuxq/alg-ds

Binary Search Tree

Difference between Binary Search Tree and Randomized BST implementations

Binary search tree

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is directly proportional to the height of the tree.

Read full: wiki/binary_search_treeopen in new window

Randomized binary search tree

In computer science and probability theory, a random binary tree is a binary tree selected at random from some probability distribution on binary trees.

Read full: wiki/randomized_bstopen in new window

Import

import {BinarySearchTree, RandBinarySearchTree} from "@raikuxq/alg-ds/lib/exports/data-structures";

API reference

BST API: /api/data-structures/binary-tree

Example usage

import {BinarySearchTree} from "@raikuxq/alg-ds/lib/exports/data-structures";
import {EnumTreeTraversalType} from "@raikuxq/alg-ds/lib/exports/types";

const tree: IBinaryTree<number> = new BinarySearchTree();

tree.insert(5);
tree.insert(12);
tree.insert(7);
tree.insert(20);

tree.max(); // 20
tree.min(); // 5
tree.traverse(EnumTreeTraversalType.IN_ORDER); // [5,7,12,20]

tree.has(20); // true
tree.delete(20);
tree.has(20); // false