binary-search-tree Algorithm

The binary search tree (BST) algorithm is a widely-used data structure that enables efficient searching, inserting, and deleting operations in a sorted dataset. In a binary search tree, each node has at most two child nodes, with the left child node being less than or equal to the parent node and the right child node being greater than or equal to the parent node. This arrangement ensures that the tree remains balanced and allows for searching operations to be performed in O(log n) time complexity, where n is the number of nodes in the tree. One of the primary use cases for binary search trees is implementing associative arrays, dictionaries, or sets, where it allows fast access to elements based on their keys. To perform a search operation in a binary search tree, the algorithm compares the target value with the root node. If the target value is equal to the root node, the search is successful. If the target value is less than the root node, the algorithm proceeds to search the left subtree, and if it is greater, the search continues in the right subtree. This process is repeated until the target value is found or the algorithm reaches a leaf node, indicating that the target value is not present in the tree. Similarly, the algorithm can perform insertion and deletion operations by traversing the tree and maintaining its sorted property.
// Binary search tree
// https://en.wikipedia.org/wiki/Binary_search_tree

package binarySearchTree

// package main

import "fmt"

type node struct {
	val   int
	left  *node
	right *node
}

type btree struct {
	root *node
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func newNode(val int) *node {
	return &node{val, nil, nil}
}

func inorder(n *node) {
	if n != nil {
		inorder(n.left)
		fmt.Print(n.val, " ")
		inorder(n.right)
	}
}

func insert(root *node, val int) *node {
	if root == nil {
		return newNode(val)
	}
	if val < root.val {
		root.left = insert(root.left, val)
	} else {
		root.right = insert(root.right, val)
	}
	return root
}

func inorderSuccessor(root *node) *node {
	cur := root
	for cur.left != nil {
		cur = cur.left
	}
	return cur
}

func bst_delete(root *node, val int) *node {
	if root == nil {
		return nil
	}
	if val < root.val {
		root.left = bst_delete(root.left, val)
	} else if val > root.val {
		root.right = bst_delete(root.right, val)
	} else {
		// this is the node to delete

		// node with one child
		if root.left == nil {
			root = root.right
		} else if root.right == nil {
			root = root.left
		} else {
			// node with two children
			d := inorderSuccessor(root)
			root.val = d.val
			root.right = bst_delete(root.right, d.val)
		}
	}
	return root
}

// helper function for t.depth
func _calculate_depth(n *node, depth int) int {
	if n == nil {
		return depth
	}
	return max(_calculate_depth(n.left, depth+1), _calculate_depth(n.right, depth+1))
}

func (t *btree) depth() int {
	return _calculate_depth(t.root, 0)
}

/*
func main() {
	t := &btree{nil}
	inorder(t.root)
	t.root = insert(t.root, 10)
	t.root = insert(t.root, 20)
	t.root = insert(t.root, 15)
	t.root = insert(t.root, 30)
	fmt.Print(t.depth(), "\n")
	inorder(t.root)
	fmt.Print("\n")
	t.root = bst_delete(t.root, 10)
	inorder(t.root)
	fmt.Print("\n")
	t.root = bst_delete(t.root, 30)
	inorder(t.root)
	fmt.Print("\n")
	t.root = bst_delete(t.root, 15)
	inorder(t.root)
	fmt.Print("\n")
	t.root = bst_delete(t.root, 20)
	inorder(t.root)
	fmt.Print("\n")
	fmt.Print(t.depth(), "\n")
}
*/

LANGUAGE:

DARK MODE: