1. Introduction
A Binary Search Tree (BST) is a type of Binary Tree where the nodes are arranged based on the following properties:
- The left subtree of a node contains only nodes with values less than the node's value.
- The right subtree of a node contains only nodes with values greater than the node's value.
- The left and right subtrees are also BSTs.
BSTs are particularly useful for searching operations, as they facilitate faster look-ups compared to arrays and linked lists.
2. Implementation Steps
1. Define a Node structure with fields for data, left, and right.
2. Implement methods for insertion (Insert), searching (Search), and in-order traversal (InOrder).
3. Enhance the tree with a method to delete a node (Delete).
3. Implementation in Golang
package main
import (
"fmt"
)
type Node struct {
data int
left *Node
right *Node
}
// Insert a value into the BST
func (n *Node) Insert(value int) {
if value <= n.data {
if n.left == nil {
n.left = &Node{data: value}
} else {
n.left.Insert(value)
}
} else {
if n.right == nil {
n.right = &Node{data: value}
} else {
n.right.Insert(value)
}
}
}
// Search for a value in the BST
func (n *Node) Search(value int) bool {
if n == nil {
return false
}
if value == n.data {
return true
}
if value < n.data {
return n.left.Search(value)
}
return n.right.Search(value)
}
// InOrder traversal of the BST
func (n *Node) InOrder() {
if n != nil {
n.left.InOrder()
fmt.Print(n.data, " ")
n.right.InOrder()
}
}
func main() {
root := &Node{data: 50}
root.Insert(30)
root.Insert(70)
root.Insert(20)
root.Insert(40)
root.Insert(60)
root.Insert(80)
fmt.Print("InOrder Traversal: ")
root.InOrder()
fmt.Println("\nSearch for 25:", root.Search(25))
fmt.Println("Search for 60:", root.Search(60))
}
Output:
InOrder Traversal: 20 30 40 50 60 70 80 Search for 25: false Search for 60: true
Explanation:
1. The Node struct is the foundation of the BST. It consists of the data, left, and right pointers.
2. The Insert method adds a new value into the BST by recursively finding the correct position.
3. The Search method checks for the presence of a value in the BST. It traverses the tree based on the value it's looking for, making the search operation efficient.
4. The InOrder method provides an in-order traversal of the BST which results in a sorted output of the tree's values.
5. In the main function, after inserting nodes into the tree, we demonstrate an in-order traversal and perform a couple of search operations.
This Binary Search Tree forms the foundation for many advanced operations like balancing and finding predecessors or successors of a node.
Comments
Post a Comment