好像好久没更了。。。
Overview
BinarySearchTree是一个很基础的数据结构，每棵树由很多个TreeNodes和一个Root组成。Root也是一个TreeNode，他跟其他的TreeNode不同之处在于他的Pre为nil。每一个TreeNode只有两个child nodes，分别为Left和Right。Left小于等于parent，Right大于等于parent。如果一个TreeNode两个child nodes都为nil，那么它就是一个leaf node。
The depth of a node is the number of edges from the node to the tree’s root node. Root has a depth of 0.
The height of a node is the number of edges on the longest path from the node to a leaf. Leaf node has a height of 0.
Height and depth of a tree is equal but height and depth of a node varies.
type TreeNode struct {
Key int
Left *TreeNode
Right *TreeNode
Pre *TreeNode
}
type BST struct {
Root *TreeNode
}
Traverse of a BST
总共有三种traverse的方法：InOrder, PreOrder, PostOrder
Inorder Traverse
InOrder 先visit一个node的left child，如果left node 不为nil，则继续visit它的left child。若left child为nil，则visit current node，然后visit right node。之后再以right node 为start point继续visit。总体上就是先visit left child和left subtree，再visite current node，最后visit right child和right subtree。这样traverse下来的结果是由小到大顺序的。这也是为什么这个叫做InOrder Traverse。
func InOrderTraverse(node *TreeNode) {
if node == nil {
return
}
InOrderTraverse(node.Left)
fmt.Println(node.Key)
InOrderTraverse(node.Right)
}
func InOrderTraverseIterative(node *TreeNode) {
if node == nil {
return
}
s := make([]*TreeNode, 0)
s = append(s, node)
for len(s) != 0 {
top := s[len(s)-1]
if top.Left != nil {
s = append(s, top.Left)
} else {
fmt.Println(top.Key)
s = s[:len(s)-1]
if top.Right != nil {
s = append(s, top.Right)
}
}
}
}
PreOrder Traverse
PreOrder与InOrder的区别在于PreOrder先visit current node 再visit left subtree和right subtree
func PreOrderTraverse(node *TreeNode) {
if node == nil {
return
}
fmt.Println(node.Key)
PreOrderTraverse(node.Left)
PreOrderTraverse(node.Right)
}
PostOrder Traverse
PostOrder是先visit left subtree和right subtree，再visit current node
func PostOrderTraverse(node *TreeNode) {
if node == nil {
return
}
PostOrderTraverse(node.Left)
PostOrderTraverse(node.Right)
fmt.Println(node.Key)
}
BST的一些基本操作
这些基本操作包括searchTreeNode, TreeMax, TreeMin, getSuccessor, addTreeNode, deleteTreeNode
searchTreeNode
searchTreeNode会traverse整个BST，返回nil（node not found）或者node with the same key。Time complexity is linear with the tree height h(O(h))
func SearchTreeNode(node *TreeNode, k int) *TreeNode {
if node == nil || node.Key == k {
return node
}
if k < node.Key {
return SearchTreeNode(node.Left, k)
} else {
return SearchTreeNode(node.Right, k)
}
}
func SearchTreeNodeIterative(node *TreeNode, k int) *TreeNode {
for node != nil && node.Key != k {
if k < node.Key {
node = node.Left
} else {
node = node.Right
}
}
return node
}
find the maximum node in the tree
根据BST的性质，一棵树最大的node就是the rightmost node。 Time complexity: O(h)
func TreeMax(node *TreeNode) *TreeNode {
for node != nil {
node = node.Right
}
return node
}
find the minimum node in the tree
相应的，一棵树最小的node就是the leftmost node。 Time complexity: O(h)
func TreeMin(node *TreeNode) *TreeNode {
for node != nil {
node = node.Left
}
return node
}
get successor of a node
一个node的successor就是按照InOrder顺序的下一个node。找一个node的successor要分为两种情况，此node有right child和没有right child。如果这个node有right child，直接return right child。若是没有right child，则要找这个node的parent，向上查找，直到此node不是parent的right child，return parent Time complexity: O(h)
func GetSuccessor(node *TreeNode) *TreeNode {
if node.Right != nil {
return TreeMin(node.Right)
}
pre := node.Pre
for pre != nil && node == pre.Right {
node = pre
pre = pre.Pre
}
return pre
}
add a node into BST
插入一个node到BST里，最重要的就是找的它的《位置》。。。插入后需要保证这棵树还是BST。其实跟search a node in the tree很类似，就是找到一个nil的slot，把这个node添加进去 Time complexity: O(h)
func (tree *BST) AddTreeNode(node *TreeNode) {
cur := tree.Root
tmp := &TreeNode{}
for cur != nil {
tmp = cur
if node.Key < cur.Key {
cur = cur.Left
} else {
cur = cur.Right
}
}
node.Pre = tmp
if tree.Root == nil {
tree.Root = node
} else if node.Key < tmp.Key {
tmp.Left = node
} else {
tmp.Right = node
}
}
delete a node from BST
插入node不难，但是删除一个node就会麻烦一点，需要考虑到不同的情况。 如果这个node只有一个child，只需要移除这个node，把它的left或者right subtree transplant过来就可以了。 但是如果这个node两个child都有，要先找到这个node的successor。如果这个successor不是这个node的child，需要transplant两次，否则只需要一次。具体操作请看code。 Time complexity: O(h)
func (tree *BST) DeleteTreeNode(node *TreeNode) {
if node.Left == nil {
tree.Transplant(node, node.Right)
} else if node.Right == nil {
tree.Transplant(node, node.Left)
} else {
y := TreeMin(node.Right)
if y.Pre != node {
tree.Transplant(y, y.Right)
y.Right = node.Right
y.Right.Pre = y
}
tree.Transplant(node, y)
y.Left = node.Left
y.Left.Pre = y
}
}
func (tree *BST) Transplant(u *TreeNode, v *TreeNode) {
if u.Pre == nil {
tree.Root = v
} else if u == v.Pre.Left {
u.Pre.Left = v
} else {
u.Pre.Right = v
}
if v != nil {
v.Pre = u.Pre
}
}
总结
以上这些有关于BST的操作都跟BST的高度有关，如果BST不balance，在最差的情况下time complexity is linear to the number of nodes in the tree，由此可见有一颗balanced的BST是多么的重要啊！所以下一章的话就要讲一讲red black tree了，这颗不管怎么样都是balance的BST。
