bst

package
Version: v0.0.0-...-241115c Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 25, 2021 License: MIT Imports: 2 Imported by: 0

Documentation

Overview

Package bst is an implementation for binary search tree data structure in go language

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Node

type Node struct {
	Data  int
	Left  *Node
	Right *Node
}

Node struct contains actual data and address to left and right node

func NewNode

func NewNode(data int) *Node

NewNode creates a new Node with integer data

type Tree

type Tree struct {
	Root *Node
}

Tree struct contains the pointer to root node

func NewBST

func NewBST() *Tree

NewBST creates an empty BST Tree

func (*Tree) Delete

func (t *Tree) Delete(data int) error

Delete deletes a node with said data such that the binary search tree property is still maintained.

The main problem with BST deletion (Hibbard Deletion) is that it is not symmetric. After many insertion and deletion BST become less balance. Researchers proved that after sufficiently long number of random insert and delete height of the tree becomes sqrt(n) . so now every operation (search, insert, delete) will take sqrt(n) time which is not good compare to O(logn).

func (*Tree) Find

func (t *Tree) Find(data int) bool

Find returns true if integer is present in the binary search tree, else false.

func (*Tree) FindMax

func (t *Tree) FindMax() (int, error)

FindMax returns the max element from the dataset

func (*Tree) FindMin

func (t *Tree) FindMin() (int, error)

FindMin returns the max element from the dataset

func (*Tree) Height

func (t *Tree) Height() int

Height returns the height of the tree

func (*Tree) InOrder

func (t *Tree) InOrder(node *Node, printFunction func(*Node))

InOrder traverses the tree in inorder fashion

Inorder Algorithm

Visit all the nodes in the left subtree
Visit the root node
Visit all the nodes in the right subtree

func (*Tree) Insert

func (t *Tree) Insert(data int) error

Insert inserts new integer data into the tree at the position, so that the binary search tree property is maintained.

func (*Tree) IsBST

func (t *Tree) IsBST() bool

IsBST returns true if the existing binary tree is a binary search tree, else false.

func (*Tree) LevelOrder

func (t *Tree) LevelOrder()

LevelOrder traversal of a tree is breadth first traversal for the tree

Example:

        F
      /	  \
     B     G
   /   \    \
 A      D    I

Level Order Traversal := F -> B -> G -> A -> D -> I

func (*Tree) PostOrder

func (t *Tree) PostOrder(node *Node, printFunction func(*Node))

PostOrder traverses the tree in inorder fashion

Postorder Algorithm

Visit all the nodes in the left subtree
Visit all the nodes in the right subtree
Visit the root node

func (*Tree) PreOrder

func (t *Tree) PreOrder(node *Node, printFunction func(*Node))

PreOrder traverses the tree in inorder fashion

Preorder Algorithm

Visit the root node
Visit all the nodes in the left subtree
Visit all the nodes in the right subtree

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
t or T : Toggle theme light dark auto
y or Y : Canonical URL