二叉搜索树是一种支持快速查找、增加和删除元素的数据结构。二叉搜索树中的节点是有序的，因此支持快速查找。该数据结构由P.F.Windley、A.D.Booth、A.J.T.Colin和T.N.Hibbard发明的。
二叉搜索树的平均空间复杂度是O(n)，插入、删除和搜索操作的时间就复杂的是O(logn)。二叉搜索树节点包含以下属性：
- 一个整型key值
- 一个整型value值
- 包含左节点leftNode和右节点rightNode
- 左节点key小于当前节点，右节点key大于当前节点
节点定义代码如下：
type TreeNode struct {
key int
value int
leftNode *TreeNode
rightNode *TreeNode
}
二叉搜索树结构体定义，其包含一个根节点rootNode是TreeNode类型，以及一个互斥锁sync.RWMutex类型。二叉搜索树的遍历是从根节点出发的，然后是左节点和右节点：
type BinarySearchTree struct {
rootNode *TreeNode
lock sync.RWMutex
}
定义好了二叉搜索树结构体类型，接下来实现其方法。
插入方法：InsertElement
该方法作用是将一个包含key和value的节点插入到二叉搜索树中。插入之前要获取锁，插入完成释放锁。
func (tree *BinarySearchTree)InsertElement(key int, value int) {
tree.lock.Lock()
defer tree.lock.Unlock()
var treeNode *TreeNode
treeNode = &TreeNode{
key: key,
value: value,
leftNode: nil,
rightNode: nil,
}
if tree.rootNode == nil {
tree.rootNode = treeNode
} else {
insertTreeNode(tree.rootNode, treeNode)
}
}
先根据key，value创建treeNode节点。然后判断根节点是否为空，如果是空就将新增的节点赋值给根节点。如果根节点不为空，调用insertTreeNode函数找到合适的位置插入。
func insertTreeNode(rootNode *TreeNode, newTreeNode *TreeNode) {
if newTreeNode.key < rootNode.key {
if rootNode.leftNode == nil {
rootNode.leftNode = newTreeNode
} else {
insertTreeNode(rootNode.leftNode, newTreeNode)
}
} else {
if rootNode.rightNode == nil{
rootNode.rightNode = newTreeNode
} else{
insertTreeNode(rootNode.rightNode, newTreeNode)
}
}
}
根据二叉搜索树的特点，每个节点的key比左节点key要大，比右节点的key要小。因此先和左节点的key比较，如果左节点为空，就将新增节点赋值给左节点，否则继续递归找。同理如果新增节点key比左节点大，就和右节点比较，为空就赋值，否则递归。
inOrderTraverse方法：顺序遍历二叉搜索树
该方法按顺序遍历树中的每个节点。先调用RLock()读锁，遍历完后释放：
func (tree *BinarySearchTree)InOrderTraverseTree(function func(int)) {
tree.lock.RLock()
defer tree.lock.RUnlock()
inOrderTraverseTree(tree.rootNode, function)
}
func inOrderTraverseTree(treeNode *TreeNode, function func(int)) {
if treeNode != nil {
inOrderTraverseTree(treeNode.leftNode, function)
function(treeNode.value)
inOrderTraverseTree(treeNode.rightNode, function)
}
}
为了避免数据竞争，这里创建一个内部调用函数来实现有序遍历二叉搜索树。根据二叉搜索树特点，先遍历左子树，然后当前节点最后遍历右子树，也称为中序遍历。
PreOrderTraverse方法：前序遍历
先遍历当前节点，然后是左子树最后右子树；
func (tree *BinarySearchTree)PreOrderTraverseTree(function func(int)) {
tree.lock.RLock()
defer tree.lock.RUnlock()
preOrderTraverseTree(tree.rootNode, function)
}
func preOrderTraverseTree(treeNode *TreeNode, function func(int)) {
if treeNode != nil {
function(treeNode.value)
preOrderTraverseTree(treeNode.leftNode, function)
preOrderTraverseTree(treeNode.rightNode, function)
}
}
PostOrderTraverse方法：后序遍历
后序遍历：先左子树，然后右子树最后是当前节点
func (tree *BinarySearchTree)PostOrderTraverseTree(function func(int)) {
tree.lock.RLock()
defer tree.lock.RUnlock()
postOrderTraverseTree(tree.rootNode, function)
}
func postOrderTraverseTree(treeNode *TreeNode, function func(int)) {
if treeNode != nil {
postOrderTraverseTree(treeNode.leftNode, function)
postOrderTraverseTree(treeNode.rightNode, function)
function(treeNode.value)
}
}
MinNode方法：最小节点
该方法：用于查找二叉搜索树中key最小的节点值。
func (tree *BinarySearchTree)MinNode() *int {
tree.lock.RLock()
defer tree.lock.RUnlock()
var treeNode *TreeNode
treeNode = tree.rootNode
if treeNode == nil {
return (*int)(nil)
}
for {
//最小值位于左子树
if treeNode.leftNode == nil {
return &treeNode.value
}
treeNode = treeNode.leftNode
}
}
根据二叉搜索树的特点：左子树值都小于当前节点，所以如果当前节点的左节点为空，说明当前节点的key是最小的
MaxNode方法：查询最大key节点
该方法和MinNode方法相反，最大子位于当前节点右子树。如果当前节点的右节点为空，说明当前节点是值最大节点。
func (tree *BinarySearchTree)MaxNode() *int {
tree.lock.RLock()
defer tree.lock.RUnlock()
var treeNode *TreeNode
treeNode = tree.rootNode
if treeNode == nil {
return (*int)(nil)
}
for {
if treeNode.rightNode == nil {
return &treeNode.value
}
treeNode = treeNode.rightNode
}
}
SearchNode方法：根据key查询对应节点是否存在。
func (tree *BinarySearchTree)SearchNode(key int) bool {
tree.lock.RLock()
defer tree.lock.RUnlock()
return searchNode(tree.rootNode, key)
}
func searchNode(treeNode *TreeNode, key int) bool {
if treeNode == nil {
return false
}
if key < treeNode.key{
return searchNode(treeNode.leftNode, key)
}
if key > treeNode.key{
return searchNode(treeNode.rightNode, key)
}
return true
}
二叉搜索树：当前节点比左子树所有节点大，比右子树所有节点小。因此在查找一个key是否存在时，如果当前节点key比搜索key更小，就继续在左子树查找；如果要搜索key大于当前节点的key就在右子树查找。否则当前节点就是要查找的节点。
removeNode方法：删除节点
func (tree *BinarySearchTree) RemoveNode(key int) {
tree.lock.Lock()
defer tree.lock.Unlock()
removeNode(tree.rootNode, key)
}
func removeNode(treenode *TreeNode, key int) *TreeNode {
if treenode == nil {
return nil
}
if key < treenode.key {
treenode.leftNode = removeNode(treenode.leftNode, key)
return treenode
}
if key > treenode.key {
treenode.rightNode = removeNode(treenode.rightNode, key)
return treenode
}
//key == treeNode.ley
if treenode.leftNode == nil && treenode.rightNode == nil {
treenode = nil
return nil
}
//要删除的节点，左节点为空
if treenode.leftNode == nil {
treenode = treenode.rightNode
return treenode
}
//要删除的节点，右节点为空
if treenode.rightNode == nil {
treenode = treenode.leftNode
return treenode
}
//要删除的节点，左右节点都不为空
var leftmostrightNode *TreeNode
leftmostrightNode = treenode.rightNode
for {
if leftmostrightNode != nil && leftmostrightNode.leftNode != nil {
leftmostrightNode = leftmostrightNode.leftNode
} else {
break
}
}
//将右子树最小节点值，替换待删除节点的值
treenode.key, treenode.value = leftmostrightNode.key, leftmostrightNode.value
//递归删除右子树最小节点
treenode.rightNode = removeNode(treenode.rightNode, treenode.key)
return treenode
}
二叉搜索树删除节点比较复杂，递归的删除。分4种情况：
1、待删除节点，左右节点为空，直接删除。
2、待删除节点，左节点为空，直接将右节点赋值给删除节点覆盖
3、待删除节点，右节点为空，直接将左节点赋值给删除节点覆盖。
4、待删除节点，左右节点都不为空。用其右子树的最小结点代替待删除结点。代码中的leftmostrightNode节点为右子树最小节点。
网友评论