- 노드는 nil이거나, key값을 갖는다
- 노드의 왼쪽 노드는 nil이거나 노드의 key 보다 작은 key 값을 갖고,
- 노드의 오른쪽 노드는 nil이거나 노드의 key 보다 큰 key 값을 갖는다
이러한 성질때문에, in-order traversal은 오름차순으로 정렬한 결과를 생성한다.
이진 검색 트리에 key를 삽입(insert)하고 삭제(remove)하고 존재 유무를 검색하는 코드를 작성한다.
삽입은 주어진 key와 노드의 key를 비교하여, 주어진 key가 노드의 key보다 큰 경우 오른쪽 sub-tree에 삽입하고, 값이 작은 경우 왼쪽 sub-tree에 삽입한다.
삭제는 주어진 key를 갖는 노드(target node)를 찾았을 때, 오른쪽 자식 노드가 있는 경우 오른쪽 자식 노드와 그 하위 tree에서 가장 작은 값 (replace node)을 해당 노드(target node)의 새로운 key로 변경하고, 재귀적으로 replace node를 삭제한다. 오른쪽 자식 노드가 없는 경우에는 왼쪽 자식노드로 해당 노드(target node)를 대신한다.
type NodeVal int
type Node struct {
Val NodeVal
Left *Node
Right *Node
}
}
func AddNode(node *Node, val NodeVal) *Node {
if node == nil {
return &Node {
Val: val,
Left: nil,
Right: nil,
}
}
if val < node.Val {
node.Left = AddNode(node.Left, val)
} else {
node.Right = AddNode(node.Right, val)
}
return node
}
func FindNode(node *Node, val NodeVal) *Node {
if node == nil {
return nil
}
switch {
case val < node.Val:
return FindNode(node.Left, val)
case val > node.Val:
return FindNode(node.Right, val)
}
return node
}
func RemoveNode(node *Node, val NodeVal) *Node {
if node == nil {
return nil
}
switch {
case val < node.Val:
node.Left = RemoveNode(node.Left, val)
return node
case val > node.Val:
node.Right = RemoveNode(node.Right, val)
return node
}
if node.Right != nil {
replaceNode := node.Right
for replaceNode.Left != nil {
replaceNode = replaceNode.Left
}
node.Val = replaceNode.Val
node.Right = RemoveNode(node.Right, replaceNode.Val)
return node
}
return node.Left
}
댓글 없음:
댓글 쓰기