After I tried to implement BST in Go, it seems like I want to modify the BST to AVL because BST is not a fairly optimal tree data structure.
When I said this:
To find a specific node you don’t have to go around the whole tree, you need to know that BST can route to a specific node by checking the node value
It’s half true because there’s a case that BST makes a linear tree like this:
And if you want to find a node with value 6, in the end, you will travel the whole tree. That’s why we need AVL to improve the time complexity. AVL will try to rebalance the tree whenever it becomes imbalance after insertion/deletion.
The whole concept of AVL is much the same with BST besides the rebalancing algorithm. In AVL we need to rebalance the tree by rotating every imbalance sub-tree in every insertion/deletion. So we’re gonna use all the code from here and modified it a bit.
To see the tree is balanced or not, we need to define the height on each node. We can calculate the height by counting the maximum height of the left and the right node recursively. If the node has no child, it means its height is 1 otherwise we compare the maximum height of the children.
Update the node struct by adding the height attribute, add the Getter function, and set the value to 1 inside the constructor.
type node struct {
height, value int left, right *node
}
func (n *node) Height() int {
if n ==nil {
return0 }
return n.height
}
funcnewNode(val int) *node {
return&node{
height: 1,
value: val,
left: nil,
right: nil,
}
}
And to keep track of the height and the balance of the tree after insertion/deletion, we need to have a updateHeight and balanceFactor function.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func (n *node) balanceFactor() int {
if n ==nil {
return0 }
return n.left.Height() - n.right.Height()
}
funcmax(a, b int) int {
if a > b {
return a
}
return b
}
func (n *node) updateHeight() {
// compare the maximum height of the children + its own height
n.height = max(n.left.Height(), n.right.Height()) +1}
balanceFactor function determines whether the tree is heavier on the left or the right side. If it returns an integer below 0, it means it’s heavier on the right side and we need to rotate to the left side of the tree. The thresholds for imbalanced tree are -1 and 1, so if the balanceFactor function returns less then -1 or greater than 1, we need to rotate the tree.
Now let’s create the rotate function. There are 2 types of rotate, rotateLeft and rotateRight. But there are 4 conditions to rotate the tree on insertion and deletion. You can read it and see the picture from here.
funcrightRotate(x *node) *node {
y := x.left
t := y.right
y.right = x
x.left = t
x.updateHeight()
y.updateHeight()
return y
}
funcleftRotate(x *node) *node {
y := x.right
t := y.left
y.left = x
x.right = t
x.updateHeight()
y.updateHeight()
return y
}
The conditions to rotate the tree on insertion are:
When the tree linearly to the right, you need to use leftRotate on the current node
When the tree linearly to the left, you need to use rightRotate on the current node
When the tree creates Less Than Symbol, you need to leftRotate on the left child, and rightRotate on the current node
When the tree creates Greater Than Symbol, you need to rightRotate on the right child, and leftRotate on the current node
funcrotateInsert(node *node, val int) *node {
// update the height on every insertion
node.updateHeight()
// bFactor will tell you which side the weight is on
bFactor := node.balanceFactor()
// linearly to the left
if bFactor > 1&& val < node.left.value {
returnrightRotate(node)
}
// linearly to the right
if bFactor < -1&& val > node.right.value {
returnleftRotate(node)
}
// less than symbol
if bFactor > 1&& val > node.left.value {
node.left = leftRotate(node.left)
returnrightRotate(node)
}
// greater than symbol
if bFactor < -1&& val < node.right.value {
node.right = rightRotate(node.right)
returnleftRotate(node)
}
return node
}
Lastly, you need to update the return statement of the insertNode function.
1
2
3
4
funcinsertNode(node *node, val int) (*node, error) {
...returnrotateInsert(node, val), nil}
funcrotateDelete(node *node) *node {
node.updateHeight()
bFactor := node.balanceFactor()
// linearly to the left
if bFactor > 1&& node.left.balanceFactor() >=0 {
returnrightRotate(node)
}
// less than symbol
if bFactor > 1&& node.left.balanceFactor() < 0 {
node.left = leftRotate(node.left)
returnrightRotate(node)
}
// linearly to the right
if bFactor < -1&& node.right.balanceFactor() <=0 {
returnleftRotate(node)
}
// greater than symbol
if bFactor < -1&& node.right.balanceFactor() > 0 {
node.right = rightRotate(node.right)
returnleftRotate(node)
}
return node
}
Deletion is not like insertion in that we can compare the entered values, because the node we are looking for is already deleted. That’s why we need to compare the current node’s balance factor with the balance factor of the child. Now, you need to modify the removeNode function. Remember when removing a node with 2 children, we need to find the successor and there are 2 ways to find the successor.
Find the least valueable node from the right child of the node
Find the greatest valueable node from the left child of the node
We used the first way while the BST & AVL Visualization Page using the second way. You can also change the code so it’s easy to visualize.
funcgreatest(node *node) *node {
if node ==nil {
returnnil }
if node.right ==nil {
return node
}
returngreatest(node.right)
}
funcremoveNode(node *node, val int) (*node, error) {
if node ==nil {
returnnil, ErrNodeNotFound
}
if val > node.value {
right, err :=removeNode(node.right, val)
if err !=nil {
returnnil, err
}
node.right = right
} elseif val < node.value {
left, err :=removeNode(node.left, val)
if err !=nil {
returnnil, err
}
node.left = left
} else {
if node.left !=nil&& node.right !=nil {
// has 2 children
// find the successor
successor :=greatest(node.left)
value := successor.value
// remove the successor
left, err :=removeNode(node.left, value)
if err !=nil {
returnnil, err
}
node.left = left
// copy the successor value to the current node
node.value = value
} elseif node.left !=nil|| node.right !=nil {
// has 1 child
// move the child position to the current node
if node.left !=nil {
node = node.left
} else {
node = node.right
}
} elseif node.left ==nil&& node.right ==nil {
// has no child
// simply remove the node
node = nil }
}
if node ==nil {
returnnil, nil }
returnrotateDelete(node), nil}
You can validate and recheck your AVL implementation with the BST & AVL visualization page.
package avl
import (
"errors""fmt")
var (
ErrDuplicatedNode error = errors.New("bst: found duplicated value on tree")
ErrNodeNotFound error = errors.New("bst: node not found")
)
type node struct {
height, value int left, right *node
}
func (n *node) balanceFactor() int {
if n ==nil {
return0 }
return n.left.Height() - n.right.Height()
}
func (n *node) updateHeight() {
max :=func (a, b int) int {
if a > b {
return a
}
return b
}
n.height = max(n.left.Height(), n.right.Height()) +1}
func (n *node) Height() int {
if n ==nil {
return0 }
return n.height
}
func (n *node) Value() int {
return n.value
}
func (n *node) Left() *node {
return n.left
}
func (n *node) Right() *node {
return n.right
}
funcnewNode(val int) *node {
return&node{
height: 1,
value: val,
left: nil,
right: nil,
}
}
funcinsertNode(node *node, val int) (*node, error) {
// if there's no node, create one
if node ==nil {
returnnewNode(val), nil }
// if there's duplicated node returns error
if node.value == val {
returnnil, ErrDuplicatedNode
}
// if value is greater than current node's value, insert to the right
if val > node.value {
right, err :=insertNode(node.right, val)
if err !=nil {
returnnil, err
}
node.right = right
}
// if value is less than current node's value, insert to the left
if val < node.value {
left, err :=insertNode(node.left, val)
if err !=nil {
returnnil, err
}
node.left = left
}
returnrotateInsert(node, val), nil}
funcremoveNode(node *node, val int) (*node, error) {
if node ==nil {
returnnil, ErrNodeNotFound
}
if val > node.value {
right, err :=removeNode(node.right, val)
if err !=nil {
returnnil, err
}
node.right = right
} elseif val < node.value {
left, err :=removeNode(node.left, val)
if err !=nil {
returnnil, err
}
node.left = left
} else {
if node.left !=nil&& node.right !=nil {
// has 2 children
// find the successor
successor :=greatest(node.left)
value := successor.value
// remove the successor
left, err :=removeNode(node.left, value)
if err !=nil {
returnnil, err
}
node.left = left
// copy the successor value to the current node
node.value = value
} elseif node.left !=nil|| node.right !=nil {
// has 1 child
// move the child position to the current node
if node.left !=nil {
node = node.left
} else {
node = node.right
}
} elseif node.left ==nil&& node.right ==nil {
// has no child
// simply remove the node
node = nil }
}
if node ==nil {
returnnil, nil }
returnrotateDelete(node), nil}
funcfindNode(node *node, val int) *node {
if node ==nil {
returnnil }
// if the node is found, return the node
if node.value == val {
return node
}
// if value is greater than current node's value, search recursively to the right
if val > node.value {
returnfindNode(node.right, val)
}
// if value is less than current node's value, search recursively to the left
if val < node.value {
returnfindNode(node.left, val)
}
returnnil}
funcrotateInsert(node *node, val int) *node {
// update the height on every insertion
node.updateHeight()
// bFactor will tell you which side the weight is on
bFactor := node.balanceFactor()
// linearly to the left
if bFactor > 1&& val < node.left.value {
returnrightRotate(node)
}
// linearly to the right
if bFactor < -1&& val > node.right.value {
returnleftRotate(node)
}
// less than symbol
if bFactor > 1&& val > node.left.value {
node.left = leftRotate(node.left)
returnrightRotate(node)
}
// greater than symbol
if bFactor < -1&& val < node.right.value {
node.right = rightRotate(node.right)
returnleftRotate(node)
}
return node
}
funcrotateDelete(node *node) *node {
node.updateHeight()
bFactor := node.balanceFactor()
// linearly to the left
if bFactor > 1&& node.left.balanceFactor() >=0 {
returnrightRotate(node)
}
// less than symbol
if bFactor > 1&& node.left.balanceFactor() < 0 {
node.left = leftRotate(node.left)
returnrightRotate(node)
}
// linearly to the right
if bFactor < -1&& node.right.balanceFactor() <=0 {
returnleftRotate(node)
}
// greater than symbol
if bFactor < -1&& node.right.balanceFactor() > 0 {
node.right = rightRotate(node.right)
returnleftRotate(node)
}
return node
}
funcrightRotate(x *node) *node {
y := x.left
t := y.right
y.right = x
x.left = t
x.updateHeight()
y.updateHeight()
return y
}
funcleftRotate(x *node) *node {
y := x.right
t := y.left
y.left = x
x.right = t
x.updateHeight()
y.updateHeight()
return y
}
funcgreatest(node *node) *node {
if node ==nil {
returnnil }
if node.right ==nil {
return node
}
returngreatest(node.right)
}
functraverse(node *node) {
// exit condition
if node ==nil {
return }
fmt.Println(node.value)
traverse(node.left)
traverse(node.right)
}
funcmax(a, b int) int {
if a > b {
return a
}
return b
}
Thank you for reading!
···
Love This Content?
Any kind of supports is greatly appreciated! Kindly support me via Bitcoin, Ko-fi, Trakteer, or just continue to read another content. You can write a response via Webmention and let me know the URL via Telegraph.