データ構造とアルゴリズムJavaScript記述(8):二叉ルックアップツリー(BST)
6179 ワード
ツリーを検索
二叉ルックアップツリー(BST):特殊な二叉ツリーで、比較的小さい値は左ノードに保存され、大きな値は右ノードに保存されます.
実装:
二叉ルックアップツリー(BST):特殊な二叉ツリーで、比較的小さい値は左ノードに保存され、大きな値は右ノードに保存されます.
実装:
class Node {
constructor(data) {
// Node
this.data = data
this.left = null
this.right = null
}
toString() {
return this.data.toString()
}
}
class BST {
constructor() {
this.root = null
}
//
insert(...datalist) {
for (let data of datalist) {
const node = new Node(data)
if (this.root === null) {
this.root = node
} else {
let current = this.root
let parent
while(true) {
parent = current
if (data < current.data) {
current = current.left
if (current === null) {
parent.left = node
break
}
} else {
current = current.right
if (current === null) {
parent.right = node
break
}
}
}
}
}
}
// : -> ->
preOrder() {
const order = node => {
if (node !== null) {
console.log(`${node.data} `)
order(node.left)
order(node.right)
}
}
order(this.root)
}
// : -> ->
inOrder() {
const order = node => {
if (node !== null) {
order(node.left)
console.log(`${node.data} `)
order(node.right)
}
}
order(this.root)
}
// : -> ->
postOrder() {
const order = node => {
if (node !== null) {
order(node.left)
order(node.right)
console.log(`${node.data} `)
}
}
order(this.root)
}
//
findMin() {
let current = this.root
while(current.left !== null) {
current = current.left
}
return current.data
}
//
findMax() {
let current = this.root
while(current.right !== null) {
current = current.right
}
return current.data
}
//
find(data) {
let current = this.root
while(current !== null) {
if (data === current.data) {
return current
} else if (data < current.data) {
current = current.left
} else if (data > current.data) {
current = current.right
}
}
}
//
find(data) {
let current = this.root
while(current !== null) {
if (data === current.data) {
return current
} else if (data < current.data) {
current = current.left
} else if (data > current.data) {
current = current.right
}
}
return null
}
//
remove(data) {
const findMin = node => {
let current = node
while(current.left !== null) {
current = current.left
}
return current
}
const removeNode = (node, data) => {
if (node === null) {
return null
}
if (data === node.data) {
//
if (node.left === null &&
node.right === null) {
return null
}
//
if (node.left === null) {
return node.right
}
//
if (node.right === null) {
return node.left
}
//
// ,
const tempNode = findMin(node.right)
//
node.data = tempNode.data
//
node.right = removeNode(node.right, tempNode.data)
return node
} else if (data < node.data) {
//
node.left = removeNode(node.left, data)
return node
} else {
//
node.right = removeNode(node.right, data)
return node
}
}
this.root = removeNode(this.root, data)
}
// BST
count() {
let arr = []
const order = node => {
if (node !== null) {
order(node.left, arr)
order(node.right, arr)
arr.push(node.data)
}
}
order(this.root)
return arr.length
}
// BST
edgesCount() {
let count = 0
const edgesCount = node => {
if (node.left !== null && node.right !== null) {
count++
edgesCount(node.left)
count++
edgesCount(node.right)
} else if (node.left !== null) {
count++
edgesCount(node.left)
} else if (node.right !== null) {
count++
edgesCount(node.right)
}
}
edgesCount(this.root)
return count
}
}
// test
const bst = new BST()
bst.insert(23,16,99,30,18,3,120,45)
console.log(bst.count()) // 8
bst.preOrder() // 23 16 3 18 99 30 45 120
bst.inOrder() // 3 16 18 23 30 45 99 120
bst.postOrder() // 3 18 16 45 30 120 99 23
bst.remove(99)
console.log(bst.count()) // 7
console.log(bst.findMin()) // 3
console.log(bst.findMax()) // 120
console.log(bst.find(30)) // Node {data: 30, left: null, right: Node}
console.log(bst.edgesCount()) // 6