binary Tree Algorithm
The binary tree algorithm is a fundamental data structure and search algorithm used in computer science and programming. It is designed to organize data in a hierarchical structure, where each element or node in the tree has at most two child nodes, commonly referred to as the left and right children. This structure allows for quick and efficient searching, insertion, and deletion of elements, as well as providing a natural means for representing hierarchical relationships between objects.
In a binary tree, each node contains a key or value, and its position in the tree is determined by the ordering property of its key. The left subtree of a node contains only nodes with keys less than the node's key, while the right subtree contains nodes with keys greater than the node's key. This ordered structure enables efficient search, insertion, and deletion operations, as each decision to move left or right down the tree eliminates half of the remaining nodes. Common binary tree algorithms include traversal (visiting all nodes in a specified order), searching (finding a node with a specific key), insertion (adding a new node to the tree), and deletion (removing a node from the tree). Balanced binary trees, such as AVL trees and red-black trees, ensure that the height of the tree remains logarithmic, optimizing the performance of these operations.
package binaryTree
import "testing"
type Comparable func(c1 interface{}, c2 interface{}) bool
type BinaryTree struct {
node interface{}
left *BinaryTree
right *BinaryTree
lessFun Comparable
}
func New(compareFun Comparable) *BinaryTree {
return &BinaryTree{
node: nil,
lessFun: compareFun,
}
}
func (tree *BinaryTree) Search(value interface{}) *BinaryTree {
if tree.node == nil {
return nil
}
if tree.node == value {
return tree
}
if tree.lessFun(value, tree.node) {
return tree.left.Search(value)
} else {
return tree.right.Search(value)
}
}
func (tree *BinaryTree) Insert(value interface{}) {
if tree.node == nil {
tree.node = value
tree.right = New(tree.lessFun)
tree.left = New(tree.lessFun)
return
}
if tree.lessFun(value, tree.node) {
tree.left.Insert(value)
} else {
tree.right.Insert(value)
}
}
func (tree *BinaryTree) Max() interface{} {
if tree.node == nil || tree.right.node == nil {
return tree.node
}
return tree.right.Max()
}
func (tree *BinaryTree) Min() interface{} {
if tree.node == nil || tree.left.node == nil {
return tree.node
}
return tree.left.Min()
}
func compare(x interface{}, y interface{}) bool {
return x.(int) < y.(int)
}
func Test_binaryTree(t *testing.T) {
tree := New(compare)
tree.Insert(1)
tree.Insert(2)
tree.Insert(3)
findTree := tree.Search(2)
if findTree.node != 2 {
t.Error("[Error] Search error")
}
findNilTree := tree.Search(100)
if findNilTree != nil {
t.Error("[Error] 2. Search error")
}
}
func Test_minmax(t *testing.T) {
tree := New(compare)
testValues := []int{4, 5, 3, 2, 9}
for _, i := range testValues {
tree.Insert(i)
}
max := tree.Max()
if max != 9 {
t.Errorf("[Error] max: expected 9, got %d", max)
}
min := tree.Min()
if min != 2 {
t.Errorf("[Error] max: expected 2, got %d", min)
}
}
