二叉搜索树 - javascript
简介
特点：每个结点最多只能有两棵子树，且有左右之分。左比节点小右比节点大；
1. 数组：（顺序存储）线性数据结构，内存连续；除了在数组最后push一个新数据的复杂度为O(1)外，无论你在哪个位置插入新数据的复杂度都为o(n) ***(注)** 在C或者Java等其他语言中，数组大小是固定的且内存地址是连续的，不会进行动态扩容。而在JavaScript中，数组就是对象，可以理解为一个键值映射：var arr = [‘a’, ‘b’, ‘c’];基本上等价于var arr = {1: ‘a’, 2: ‘b’, 3: ‘c’};所以此数组非彼数组
插入数据时，待插入位置的的元素和它后面的所有元素都需要向后移
删除数据时，待删除位置后面的所有元素都需要向前移
- 优点：可以通过下标值访问，效率高；
- 缺点：查找数据时需要先对数据进行排序，生成有序数组，才能提高查找效率；并且在插入和删除元素时，需要大量的位移操作；
2.链表:（链式存储，线性表）元素不之间连续，通过指针将一组零散的内存块串联起来；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度O(1)；链表中最常见的三种结构分别是单链表，双链表，循环链表；***(注)** 数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）
- 优点：数据的插入和删除操作效率都很高；
- 缺点：查找效率低，需要从头开始依次查找，直到找到目标数据为止；当需要在链表中间位置插入或删除数据时，插入或删除的效率都不高。
3.哈希表：哈希表又叫散列表；哈希表的插入、查询、删除效率都是非常高的，拉链法。简单来说，哈希表就是通过一个映射函数f(key)将一组数据散列存储在数组中的一种数据结构 ；当选择了一个哈希函数之后，有可能不同的数据会计算出相同的key；会有一些解决冲突的方法；
- 优点：树结构综合了上述三种结构的优点，同时也弥补了它们存在的缺点（虽然效率不一定都比它们高），比如树结构中数据都是有序的，查找效率高；空间利用率高；并且可以快速获取最大值和最小值等。
- 缺点：当数据是是顺序的话会造成深度过高，这个时候就需要平衡二叉树；
实现
节点函数
1
2
3
4
5
| function Node(key) {
this.key = key;
this.left = null;
this.right = null;
}
|
二叉搜索树函数实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
function BinarySearchTree() {
this.root = null;
this.insert = function (key) {
let newNode = new Node(key);
if (this.root == null) {
this.root = newNode
} else {
this.insertNode(this.root, newNode);
}
}
this.insertNode = function (node, newNode) {
if (newNode.key < node.key) {
if (node.left == null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode)
}
} else {
if (node.right == null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode)
}
}
}
}
}
|
遍历数据
常见的三种二叉树遍历方式为：
还有层序遍历，使用较少。
先序遍历
根->左树->右树
上图为：11->7->15->16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
this.preOrderTraversal = function () {
let result = [];
this.preOrderTraversalNode1(this.root, function (res) {
result.push(res);
})
return result
}
this.preOrderTraversalNode = function (node, handler) {
if (node != null) {
handler(node.key)
this.preOrderTraversalNode1(node.left, handler)
this.preOrderTraversalNode1(node.right, handler)
}
}
|
中序遍历
上图为：7->11->15->16
和先序遍历没什么不同，不同的只是递归操作的时候的handler操作顺序变了
先遍历左子树； 然后遍历根（父）节点； 最后遍历其右子树；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
this.inOrderTraverse = function () {
let result = [];
this.preOrderTraversalNode1(this.root, function (res) {
result.push(res);
})
return result
}
this.inOrderTraverseNode = function (node, handler) {
if (node != null) {
this.inOrderTraverseNode(node.left, handler)
handler(node.key)
this.inOrderTraverseNode(node.right, handler)
}
}
|
后序遍历
上图为：7->16->15->11
和先序遍历也没什么不同，不同的也只是递归操作的时候的handler操作顺序变了
先遍历其左子树； 然后遍历其右子树； 最后遍历根（父）节点；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
this.postorderTraversal= function () {
let result = [];
this.preOrderTraversalNode1(this.root, function (res) {
result.push(res);
})
return result
}
this.postorderTraversalNode= function (node, handler) {
if (node != null) {
this.inOrderTraverseNode(node.left, handler)
handler(node.key)
this.inOrderTraverseNode(node.right, handler)
}
}
|
查找
最大值与最小值
二叉搜索树中的最大值在树的最右边；最小值在最左边；只需要一直查找就可以获得
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
this.max = function () {
let node = this.root;
while (node.right) {
node = node.right;
}
return node.key;
}
this.min = function () {
let node = this.root;
while (node.left) {
node = node.left;
}
return node.key;
}
|
查找特定值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
this.search = function (key) {
let node = this.root;
while (node) {
if (key > node.key) {
node = node.right;
} else if (key > node.key) {
node = node.left;
} else {
return key
}
}
return null
}
this.search = function (key, node) {
if (node) {
if (node.key > key) {
this.search(key, node.right)
} else if (node.key < key) {
this.search(key, node.left)
} else {
return node.key
}
}
return null
}
|
删除节点
删除节点相对来说比较复杂，需要考虑到多种情况：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
this.remove = function (key) {
let current = this.root;
let parent = null;
let isLeftChild = true;
while (current.key != key) {
parent = current;
if (key < current.key) {
isLeftChild = true;
current = current.left;
} else {
isLeftChild = false;
current = current.right;
}
if (current == null) return false;
}
if (current.right == null && current.left == null) {
if (current === this.root) {
this.root = null;
} else if (isLeftChild) {
parent.left = null;
} else {
parent.right = null;
}
}
else if (current.right == null) {
if (current == this.root) {
this.root = current.left
} else if (isLeftChild) {
parent.left = current.left
} else {
parent.right = current.left
}
} else if (current.left == null) {
if (current == this.root) {
this.root = current.right
} else if (isLeftChild) {
parent.left = current.right
} else {
parent.right = current.right
}
}
else {
let successor = this.getSuccess(current);
if (this.root == current) {
this.root = successor
} else if (isLeftChild) {
parent.left = successor
} else {
parent.right = successor
}
successor.left = current.left;
}
return true;
},
this.getSuccess = function (delNode) {
let successor = delNode;
let current = delNode.right
let successorParent = delNode;
while (current != null) {
successorParent = successor;
successor = current;
current = current.left
}
if (successor != delNode.right) {
successorParent.left = successor.right;
successor.right = delNode.right;
}
return successor;
},
|
二叉搜索树是有缺陷的：当插入的数据是有序的数据，就会造成二叉搜索树的深度过大；这个时候就需要对树进行处理达到树得平衡；常见的有AVL和红黑树