iT邦幫忙

2021 iThome 鐵人賽

DAY 26
0
Software Development

算法30天系列 第 26

Day.26 Binary Search Tree IV

今天講二元樹的刪除,特別拉一篇出來講,是因為它滿複雜,要處理的case很多。

樹的刪除這邊會把它分成4個case

  1. 左右的child都為空
    https://ithelp.ithome.com.tw/upload/images/20211002/20129767WaxZvUeXeu.png

刪45,45的左右child都為空,直接把30的右child改為空

  1. 左邊的child有值,但右節點為空
    https://ithelp.ithome.com.tw/upload/images/20211002/20129767y8IkgULids.png

刪14,14有左child但沒有右child,把1拉上去,30的左child接到1

  1. 右邊child有值,但它底下沒有左child
    https://ithelp.ithome.com.tw/upload/images/20211002/20129767CyvKk6BqKx.png

刪45,45有右child 60,但60底下沒有左child,那就把60拉上去,60的左child接38,30的右child接60

  1. 右邊child有值,底下有左child
    https://ithelp.ithome.com.tw/upload/images/20211002/20129767mBqhlaNv4a.png

這時候的情境比較複雜,我們需要找右邊child底下最小的值,往右邊child的左child做搜尋,找到最小的值。大家可以試試看如果用54或73做替換,再用樹搜尋一下51,你會發現二元樹的特性被破壞,導致有些值永遠找不到。

刪45,右child不為空,而且60擁有左child,往左child找最小值,找到51,把51拉上來,58的左child接到54,51的左child接38 右child接60,30的右child接51。

4個case都講完了,就可以轉化為程式
這邊會做leetcode的450題,leetcode有大量test case,如果都過了就證明沒問題~


Leetcode #450. Delete Node in a BST

程式

func deleteNode(root *TreeNode, key int) *TreeNode {
	var preNode *TreeNode
	currentNode := root

	// 先找到要刪的節點
	for {
		// 找不到
		if currentNode == nil {
			return root
		}
        
		if currentNode.Val == key {
			break
		}
        
		if key < currentNode.Val {
			// 往左找
			preNode = currentNode
			currentNode = currentNode.Left
		} else {
			// 往右找
			preNode = currentNode
			currentNode = currentNode.Right
		}
	}

	// case.1 左右chil為空
	if currentNode.Left == nil && currentNode.Right == nil {
		// 刪的是root節點
		if preNode == nil {
			root = nil
			return root
		}

		if currentNode.Val < preNode.Val {
			preNode.Left = nil
		} else {
			preNode.Right = nil
		}

		return root
	}

	// case.2 左child有東西 右child為空
	if currentNode.Left != nil && currentNode.Right == nil {
		// 刪的是root節點
		if preNode == nil {
			root = currentNode.Left
			return root
		}

		// 判斷要接到上一個節點的左邊還是加邊
		if currentNode.Val < preNode.Val {
			preNode.Left = currentNode.Left
		} else {
			preNode.Right = currentNode.Left
		}

		return root
	}

	// case.3 右child有東西 但它沒有左child
	if currentNode.Right != nil && currentNode.Right.Left == nil {
		// 把目前節點的左child 接到右child的左child
		currentNode.Right.Left = currentNode.Left

		// 刪的是root節點
		if preNode == nil {
			root = currentNode.Right
			return root
		}

		// 判斷要接到上一個節點的左邊還是加邊
		if currentNode.Val < preNode.Val {
			preNode.Left = currentNode.Right
		} else {
			preNode.Right = currentNode.Right
		}

		return root
	}

	// case.4 右child擁有左child
	// 從左child開始找 找到最小的值
	leftMostParent := currentNode.Right
	leftMost := currentNode.Right.Left
	for leftMost.Left != nil {
		leftMostParent = leftMost
		leftMost = leftMost.Left
	}

	leftMostParent.Left = leftMost.Right
	leftMost.Left = currentNode.Left
	leftMost.Right = currentNode.Right

	// 刪的是root節點
	if preNode == nil {
		root = leftMost
		return root
	}

	if leftMost.Val < preNode.Val {
		preNode.Left = leftMost
	} else {
		preNode.Right = leftMost
	}

	return root
}
Runtime: 12 ms, faster than 86.46% of Go online submissions for Delete Node in a BST.
Memory Usage: 7.1 MB, less than 96.88% of Go online submissions for Delete Node in a BST.

大家在leetcode的soultion可以找到非常簡潔的做法,有興趣可以上去看,不過更不好理解就是了XD

終於講完二元樹的新增刪除走訪了QQ
鏈結的概念一定要先搞懂,不然樹會很難理解
今天先這樣~Bye~~


上一篇
Day.25 Binary Search Tree III
下一篇
Day. 27 Binary Tree Level Order Traversal
系列文
算法30天30

尚未有邦友留言

立即登入留言