Welcome, Guest: Register On Nairaland / LOGIN! / Trending / Recent / NewStats: 3,195,357 members, 7,957,958 topics. Date: Wednesday, 25 September 2024 at 05:53 AM |
Nairaland Forum / Science/Technology / Programming / AVL TREE In Go Programming Lang. (932 Views)
GO Programming Language - Course And Certification / You Have Learnt A Few Programming Lang. But Yet You Cant Build An App? Read This / Where You Will Find Go Programming Language Tutorial? (2) (3) (4)
(1) (Reply)
AVL TREE In Go Programming Lang. by Ibbaba(m): 9:12pm On Feb 19, 2017 |
AVL tree in go programming language *Data structure* ,any one can take this as a challenge and *implement it in python programing language Any guru here who can attemp this Tree.go Package avltree import ( "errors" ) type Tree struct { root *Node } func NewTree(comparator func(a, b *Node) int) (*Tree) { comp = comparator return &Tree{} } func (tree *Tree) Insert(value interface{}) { n := create(value) rootNode := tree.root if rootNode == nil { n.height = 0 tree.root = n } else { rootNode.add(n, tree) } } func (tree *Tree) InOrderTraversal(do func(a *Node)) { inOrderTraversal(tree.root, do) } func (tree *Tree) PreOrderTraversal(do func(a *Node)) { preOrderTraversal(tree.root, do) } func (tree *Tree) PostOrderTraversal(do func(a *Node)) { postOrderTraversal(tree.root, do) } func (tree *Tree) Delete(node *Node) error { if node == nil { return errors.New("Couldn't found node with the value specified" } if node.IsLeave() { parent := node.parent parent.detachChild(node) tree.rebalance(parent) } if node.left != nil && node.right == nil { parent := node.parent parent.setLeft(node.left) tree.rebalance(parent) } else if node.left == nil && node.right != nil { parent := node.parent parent.setRight(node.right) tree.rebalance(parent) } if node.left != nil && node.right != nil { _, successor := tree.Successor(node) node.Value = successor.Value tree.Delete(successor) } return nil } func (tree *Tree) Find(value interface{}) (error, *Node){ n := create(value) foundNode := tree.compare(n, tree.root) if foundNode == nil { return errors.New("Node was not found", nil } return nil, foundNode } func (tree *Tree) Successor(node *Node) (error, *Node) { if node.right != nil { return nil, tree.min(node.right) } else { return errors.New("Node has no right child", nil } } func (tree *Tree) min(node *Node) *Node{ if node.left == nil { return node } return tree.min(node.left) } func (tree *Tree) compare(node, current *Node) (*Node) { if current == nil { return nil } comparison := comp(current, node) if comparison == 0 { return current } else if comparison > 0 { return tree.compare(node, current.right) } else { return tree.compare(node, current.left) } } func (tree *Tree) rebalance(node *Node) { if node != nil { node.updateHeight() if !node.IsBalanced() { bf := balancedFactor(node) if bf > 0 { bfNext := balancedFactor(node.left) if bfNext == 0 || bfNext == 1{ leftLeftRotation(node, tree) } else { leftRightRotation(node, tree) } } else { bfNext := balancedFactor(node.right) if bfNext == 0 || bfNext == 1{ rightRightRotation(node, tree) } else { rightLeftRotation(node, tree) } } } else { tree.rebalance(node.parent) } } } func inOrderTraversal(node *Node, do func(a *Node)) { if node != nil { inOrderTraversal(node.left, do) do(node) inOrderTraversal(node.right, do) } } func preOrderTraversal(node *Node, do func(a *Node)) { if node != nil { do(node) preOrderTraversal(node.left, do) preOrderTraversal(node.right, do) } } func postOrderTraversal(node *Node, do func(a *Node)) { if node != nil { postOrderTraversal(node.left, do) postOrderTraversal(node.right, do) do(node) } } • Node .go • package avltree • • import ( • "math" • "errors" • ) • • type Node struct { • parent *Node • Value interface{} • left *Node • right *Node • height int • } • • var comp func(a, b *Node) int • • func create(value interface{}) (node *Node) { • return &Node{Value:value} • } • • func getHeight(node *Node) int { • if node != nil { • return node.height • } • return -1 • } • • func balancedFactor(node *Node) int { • left := getHeight(node.left) • right := getHeight(node.right) • return left - right • } • • func (n *Node) add(child *Node, tree *Tree) { • greaterFactor := comp(n, child) • if greaterFactor > 0 { • if n.right != nil { • n.right.add(child, tree) • } else { • n.setRight(child) • } • } else { • if n.left != nil { • n.left.add(child, tree) • } else { • n.setLeft(child) • } • • } • • n.updateHeight() • if !n.IsBalanced() { • rotate(n, tree) • } • • } • • func (n *Node) updateHeight() { • hleft := getHeight(n.left) • hright := getHeight(n.right) • n.height = int(math.Max(float64(hleft), float64(hright))) + 1 • } • • func (n *Node) Left() (*Node) { • return n.left • } • • func (n *Node) Right() (*Node) { • return n.right • } • • func (n *Node) IsLeave() bool { • return n.right == nil && n.left == nil • } • • func (n *Node) IsBalanced() bool { • return math.Abs(float64(balancedFactor(n))) < 2 • } • • func (n *Node) GetHeight() int { • return n.height • } • • func (n *Node) GetParent() (*Node) { • return n.parent • } • • func (n *Node) setLeft(node *Node) { • n.left = node • if node != nil { • node.parent = n • } • } • • func (n *Node) setRight(node *Node) { • n.right = node • if node != nil { • node.parent = n • } • } • • func (n *Node) detachChild(node *Node) error { • if n.left == node { • n.left = nil • node.parent = nil • return nil • } • • if n.right == node { • n.right = nil • node.parent = nil • return nil • } • • return errors.New("Node wasn't found" • } • • func rotate(n *Node, tree *Tree) { • if !n.IsBalanced() { • bf := balancedFactor(n) • if bf > 0 { • bfNext := balancedFactor(n.left) • if bfNext > 0 { • leftLeftRotation(n, tree) • } else { • leftRightRotation(n, tree) • } • } else { • bfNext := balancedFactor(n.right) • if bfNext > 0 { • rightLeftRotation(n, tree) • } else { • rightRightRotation(n, tree) • } • } • } • } • • func leftLeftRotation(pivot *Node, tree *Tree) { • child := pivot.left • • // House keeping • fixTree(pivot, child, tree) • • pivot.setLeft(child.right) • child.setRight(pivot) • • updateChild(child) • • } • • func leftRightRotation(pivot *Node, tree *Tree) { • rightRightRotation(pivot.left, tree) • leftLeftRotation(pivot, tree) • } • • func rightRightRotation(pivot *Node, tree *Tree) { • child := pivot.right • • fixTree(pivot, child, tree) • • pivot.setRight(child.left) • child.setLeft(pivot) • • updateChild(child) • } • • func rightLeftRotation(pivot *Node, tree *Tree) { • leftLeftRotation(pivot.right, tree) • rightRightRotation(pivot, tree) • } • • func fixTree(pivot, pivotChild *Node, tree *Tree) { • if tree.root == pivot { • tree.root = pivotChild • pivotChild.parent = nil • } else { • if pivot.parent.left == pivot { • pivot.parent.setLeft(pivotChild) • } else { • pivot.parent.setRight(pivotChild) • } • } • } • • func updateChild(child *Node) { • if child.left != nil { • child.left.updateHeight() • } • • if child.right != nil { • child.right.updateHeight() • } • child.updateHeight() • } |
(1) (Reply)
Affordable Ponzi Site / Small Business Customized Application. Why Not? / How To Marketize A Website
(Go Up)
Sections: politics (1) business autos (1) jobs (1) career education (1) romance computers phones travel sports fashion health religion celebs tv-movies music-radio literature webmasters programming techmarket Links: (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) Nairaland - Copyright © 2005 - 2024 Oluwaseun Osewa. All rights reserved. See How To Advertise. 27 |