package main
import (
"errors"
"fmt"
"log"
)
type Node struct {
Value string
Data string
Left *Node
Right *Node
}
// `Insert()` inserts a new data into the tree, at the position which is determined by the inserted value.
//
// 1. Start at the root node.
// 2. Compare the new value with the current node's value...
// - If it is the same, stop. We have that value already.
// - If it is smaller, repeat 2. with the left child node. If there is no left child node, then add a new one with the new value and stop.
// - If it is greater, repeat 2. with the right child node. If there is no right child node, then add a new one with the new value and stop.
func (n *Node) Insert(value, data string) error {
if n == nil {
return errors.New("Cannot insert a value into a nil tree")
}
switch {
case value == n.Value:
return nil
case value < n.Value:
if n.Left == nil {
n.Left = &Node{Value:value, Data:data}
return nil
}
return n.Left.Insert(value, data)
case value > n.Value:
if n.Right == nil {
n.Right = &Node{Value:value, Data: data}
return nil
}
return n.Right.Insert(value, data)
}
return nil
}
func (n *Node) IterativeInsert(value, data string) error {
var parent *Node
current := n
if current == nil {
return errors.New("Cannot insert a value into a nil tree")
}
for current != nil {
parent = current
if value < current.Value {
current = current.Left
} else {
current = current.Right
}
}
if value < parent.Value {
parent.Left = &Node{Value:value, Data:data}
} else {
parent.Right = &Node{Value:value, Data:data}
}
return nil
}
// `Search()` searches the given data from the tree.
func (n *Node) Search(s string) (string, bool) {
if n == nil {
return "", false
}
switch {
case s == n.Value:
return n.Data, true
case s < n.Value:
return n.Left.Search(s)
default:
return n.Right.Search(s)
}
}
func (n *Node) IterativeSearch(s string) (string, bool) {
var result, p *Node
p = n
for p != nil {
if s == p.Value {
result = p
p = nil
} else {
if s < p.Value {
p = p.Left
} else {
p = p.Right
}
}
}
if result == nil {
return "", false
} else {
return result.Data, true
}
}
// `findMax()` finds the maximum element in a (sub-)tree and returns the node itself and its parent node.
func (n *Node) findMax(parent *Node) (*Node, *Node) {
if n == nil {
return nil, parent
}
if n.Right == nil {
return n, parent
}
return n.Right.findMax(n)
}
// `replace()` replaces the `parent`'s child pointer to `n` with a pointer to the `replacement`node.
func (n *Node)replace(parent, replacement *Node) error {
if n == nil {
return errors.New("`replace()` is not allowed on a nil node")
}
if n == parent.Left {
parent.Left = replacement
return nil
}
parent.Right = replacement
return nil
}
// `Delete()` deletes the given element from the tree.
// It is an error to try deleting an element that does not exist in the tree.
// In order to remove an element properly, `Delete` needs to know the to-be-deleted node's parent.
//
// Delete
// 1. Delete a leaf node.
// - Just set the parent's child pointer to `nil`
// 2. Delete a half-lead node.
// - Just replace the node by its child node.
// 3. Delete an inner node.
// - The to-be-deleted node has two children, and we cannot assign both to the to-be-deleted node's parent node.
// - In the to-be-deleted node's left subtree, find the node with the largest value. Let me call this "Node A"
// - Replace the to-be-deleted node's value with A's value.
// - If A is a leaf node or a half-leaf node, delete Node A as described above for the leaf and half-leaf cases.
// - If A is an inner node, recursively call this `Delete()` on this node.
func (n *Node) Delete(s string, parent *Node) error {
if n == nil {
return errors.New("Value to be deleted does not exist in the tree")
}
switch {
case s < n.Value:
return n.Left.Delete(s, n)
case s > n.Value:
return n.Right.Delete(s, n)
default:
// We find the to-be-deleted node.
// If the node has no children, just remove it from its parent.
if n.Left == nil && n.Right == nil {
n.replace(parent, nil)
return nil
}
// If the node has one children, replace the node with its child.
if n.Left == nil {
n.replace(parent, n.Right)
return nil
}
if n.Right == nil {
n.replace(parent, n.Left)
return nil
}
// If the node has two children, we have to find the node which has the maximum value, in the left subtree of the to-be-deleted node.
replacement, replParent := n.Left.findMax(n)
// Replace the node's value.
n.Value = replacement.Value
n.Data = replacement.Data
// Remove the replaced node.
return replacement.Delete(replacement.Value, replParent)
}
}
type Tree struct {
Root *Node
}
func (t *Tree) Insert(value, data string) error {
if t.Root == nil {
t.Root = &Node{Value:value, Data:data}
return nil
}
return t.Root.Insert(value, data)
}
func (t *Tree) IterativeInsert(value, data string) error {
if t.Root == nil {
t.Root = &Node{Value:value, Data:data}
return nil
}
return t.Root.IterativeInsert(value, data)
}
func (t *Tree) Search(s string) (string, bool) {
if t.Root == nil {
return "", false
}
return t.Root.Search(s)
}
func (t *Tree) IterativeSearch(s string) (string, bool) {
if t.Root == nil {
return "", false
}
return t.Root.IterativeSearch(s)
}
func (t *Tree) Delete(s string) error {
if t.Root == nil {
return errors.New("Cannot delete from an empty tree")
}
// We have to call `Delete()` with fake node in order to avoid having to treat the root node as a special case.
fakeRoot := &Node{Right: t.Root}
err := t.Root.Delete(s, fakeRoot)
if err != nil {
return err
}
// If the root node is the only node in the tree and if it is deleted, `t.Root` still points to the old node, so we have to rectify this by setting `t.Root` to `nil`.
if fakeRoot.Right == nil {
t.Root = nil
}
return nil
}
func (t *Tree) PreorderTraverse(n *Node, f func(*Node)) {
if n == nil {
return
}
f(n)
t.PreorderTraverse(n.Left, f)
t.PreorderTraverse(n.Right, f)
}
func (t *Tree) InorderTraverse(n *Node, f func(*Node)) {
if n == nil {
return
}
t.InorderTraverse(n.Left, f)
f(n)
t.InorderTraverse(n.Right, f)
}
func (t *Tree) PostorderTraverse(n *Node, f func(*Node)) {
if n == nil {
return
}
t.PostorderTraverse(n.Left, f)
t.PostorderTraverse(n.Right, f)
f(n)
}
func PrintTree(root *Node) {
if root == nil {
return
}
fmt.Println(root.Value)
PrintSubTree(root, "")
fmt.Println()
}
func PrintSubTree(root *Node, prefix string) {
if root == nil {
return
}
hasLeft, hasRight := false, false
if root.Left != nil {
hasLeft = true
}
if root.Right != nil {
hasRight = true
}
if !hasLeft && !hasRight {
return
}
fmt.Print(prefix)
if hasLeft && hasRight {
fmt.Print("├── ")
} else {
fmt.Print("")
}
if !hasLeft && hasRight {
fmt.Print("└── ")
} else {
fmt.Print("")
}
if hasRight {
printStrand := hasLeft && hasRight && (root.Right.Right != nil ||root.Right.Left != nil)
newPrefix := ""
if printStrand {
newPrefix = prefix + "│ "
} else {
newPrefix = prefix + " "
}
fmt.Println(root.Right.Value)
PrintSubTree(root.Right, newPrefix)
}
if hasLeft {
if hasRight {
fmt.Print(prefix)
fmt.Print("└── ")
fmt.Print(root.Left.Value)
fmt.Println()
} else {
fmt.Print("")
fmt.Print("└── ")
fmt.Print(root.Left.Value)
fmt.Println()
}
PrintSubTree(root.Left, prefix + " ")
}
}
func main() {
values := []string{"r", "s", "a", "e", "o", "h", "k", "d", "l", "z", "w", "q", "t", "y", "m", "c", "f", "n", "j", "b", "p", "i", "x", "g", "u", "v"}
data := []string{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", "26"}
// Create tree
tree := &Tree{}
for i := 0; i < len(values); i++ {
err := tree.Insert(values[i], data[i])
if err != nil {
log.Fatal("Error inserting value `", values[i], "`: ", err)
}
}
PrintTree(tree.Root)
// Inorder traverse from root
fmt.Print("Sorted values: | ")
tree.InorderTraverse(tree.Root,
func(n *Node) {
fmt.Print(n.Value, ": ", n.Data, " | ")
})
fmt.Println()
// Search
s := "d"
fmt.Print("Find node '", s, "': ")
d, found := tree.Search(s)
if !found {
log.Fatal("Cannot find '" + s + "'")
}
fmt.Println("Found " + s + ": '" + d + "'")
// Delete
err := tree.Delete(s)
if err != nil {
log.Fatal("Error deleting "+s+": ", err)
}
fmt.Print("After deleting '" + s + "': ")
tree.InorderTraverse(tree.Root,
func(n *Node) {
fmt.Print(n.Value, ": ", n.Data, " | ")
})
fmt.Println()
}
More than 5 years have passed since last update.
Register as a new user and use Qiita more conveniently
- You get articles that match your needs
- You can efficiently read back useful information
- You can use dark theme