[DS] AVL Tree
Feature
A balanced BST is a BST that h = O(log N). AVL Tree (Adelson-Velskii & Landis, 1962) that is named after its inventor: Adelson-Velskii and Landis.
...detail TBD ...
extends BST
AVL Tree 亦是一種 BST, 所有對 BST 的操作都適用於 AVL Tree. 適合類別界面封裝概念, 操作時無須考慮是由那一種 Tree 實作, 透過類別封裝界面操作即可.
另一點則是實作上 AVL Tree 中許多函式都可以直接沿用 BST 界面, 也適合用繼承以利程式重複使用與維護.
- Go
- JavaScript
- TypeScript
- Python
type AVLNode struct {
value int
height int
left *AVLNode
right *AVLNode
}
func newAVLNode(v int) *AVLNode {
return &AVLNode{
value: v,
height: 1,
left: nil,
right: nil,
}
}
class AVL extends BST {
constructor(data) {
super()
this.root = null
if (typeof(data) === 'number') {
this.root = new AVLNode(data)
} else if (Array.isArray(data)) {
this.root = new AVLNode(data[0])
for (let i = 1; i < data.length; i++)
this.insert(data[i])
}
}
}
class AVLNode extends BSTNode {
constructor(data) {
super()
this.value = data
this.left = null
this.right = null
this.height = 1
}
}
export class AVL extends BST {
constructor(data: number | Array<number>) {
super(null)
this.root = null
if (typeof (data) === 'number') {
this.root = new AVLNode(data)
} else if (Array.isArray(data)) {
this.root = new AVLNode(data[0])
for (let i = 1; i < data.length; i++)
this.insert(data[i])
}
}
}
export class AVLNode extends BSTNode {
left: IAVLNode
right: IAVLNode
height: number
constructor(data: number) {
super(data)
this.left = null
this.right = null
this.height = 1
}
}
class AVL(BST):
def __init__(self, data):
self.root = None
if isinstance(data, int):
self._root = AVLNode(data)
elif isinstance(data, list):
self._root = AVLNode(data[0])
for i in range(1, len(data), 1):
self.insert(data[i])
class AVLNode(BSTNode):
def __init__(self, data):
self.value = data
self.left = None
self.right = None
self.height = 1