returns true if a node with value i was found and deleted and returns false otherwise
(i int)
| 89 | // returns true if a node with value i was found |
| 90 | // and deleted and returns false otherwise |
| 91 | func (t *Tree) Delete(i int) bool { |
| 92 | var parent *Node |
| 93 | |
| 94 | h := t.Head |
| 95 | n := &Node{Value: i} |
| 96 | for h != nil { |
| 97 | switch n.Compare(h) { |
| 98 | case -1: |
| 99 | parent = h |
| 100 | h = h.Left |
| 101 | case 1: |
| 102 | parent = h |
| 103 | h = h.Right |
| 104 | case 0: |
| 105 | if h.Left != nil { |
| 106 | right := h.Right |
| 107 | h.Value = h.Left.Value |
| 108 | h.Left = h.Left.Left |
| 109 | h.Right = h.Left.Right |
| 110 | |
| 111 | if right != nil { |
| 112 | subTree := &Tree{Head: h} |
| 113 | IterOnTree(right, func(n *Node) { |
| 114 | subTree.Insert(n.Value) |
| 115 | }) |
| 116 | } |
| 117 | t.Size-- |
| 118 | return true |
| 119 | } |
| 120 | |
| 121 | if h.Right != nil { |
| 122 | h.Value = h.Right.Value |
| 123 | h.Left = h.Right.Left |
| 124 | h.Right = h.Right.Right |
| 125 | |
| 126 | t.Size-- |
| 127 | return true |
| 128 | } |
| 129 | |
| 130 | if parent == nil { |
| 131 | t.Head = nil |
| 132 | t.Size-- |
| 133 | return true |
| 134 | } |
| 135 | |
| 136 | if parent.Left == n { |
| 137 | parent.Left = nil |
| 138 | } else { |
| 139 | parent.Right = nil |
| 140 | } |
| 141 | t.Size-- |
| 142 | return true |
| 143 | } |
| 144 | } |
| 145 | return false |
| 146 | } |
| 147 | |
| 148 | func IterOnTree(n *Node, f func(*Node)) bool { |