树结构
1 树的基本概念,分类和术语
1.1 树的基本概念
- 树的基本概念(转自)
- 树形结构是一对多的非线性结构。
- 树形结构有树和二叉树两种,树的操作实现比较复杂,但树可以转换为二叉树进行处理。
- 树的定义:树(Tree)是 n(n≥0)个相同类型的数据元素的有限集合。
- 树中的数据元素叫节点(Node)。
- n=0 的树称为空树(Empty Tree);
- 对于 n>0 的任意非空树 T 有:
- 有且仅有一个特殊的节点称为树的根(Root)节点,根没有前驱节点;
- 若n>1,则除根节点外,其余节点被分成了m(m>0)个互不相交的集合
T1,T2,。。。,Tm,其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1,T2,。。。,Tm称为这棵树的子树(Subtree)。
- 树的定义是递归的,用树来定义树。因此,树(以及二叉树)的许多算法都使用了递归。
1.2 树的分类
- 树的分类:
- 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树;
- 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树;
- 二叉树:每个节点最多含有两个子树的树称为二叉树;
- 完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;
- 满二叉树:所有叶节点都在最底层的完全二叉树;
- 平衡二叉树(AVL树):当且仅当任何节点的两棵子树的高度差不大于1的二叉树;
- 排序二叉树(二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树);
- 霍夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树;
- B树:一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多余两个子树。
1.3 树的术语
- 二叉树:每个节点最多含有两个子树的树称为二叉树;
- 树的术语
- 节点的度:一个节点含有的子树的个数称为该节点的度;
- 树的度:一棵树中,最大的节点的度称为树的度;
- 叶节点或终端节点:度为零的节点;
- 非终端节点或分支节点:度不为零的节点;
- 父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
- 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
- 兄弟节点:具有相同父节点的节点互称为兄弟节点;
- 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
- 树的高度或深度:树中节点的最大层次;
- 堂兄弟节点:父节点在同一层的节点互为堂兄弟;
- 节点的祖先:从根到该节点所经分支上的所有节点;
- 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林:由m(m>=0)棵互不相交的树的集合称为森林;
2 数组,链表,哈希表和树的比较
2.1 数组
- 优点:
- 根据下标志值访问效率会很高
- 希望根据元素查找对应的位置时,采用线性查找很费事,可以先对数组进行排序,在进行二分查找
- 缺点:
- 优点:
- 链表的插入和删除操作效率都很高
- 缺点
- 优点
- 插入,删除,查询的效率都很高
- 缺点
- 优点:
- 树结构空间利用率高,可以按照顺序进行排列
- 每种树都有其特定的应用场景
- 效率一般情况下没有哈希表高
- 缺点
- 普通的方式
- 儿子-兄弟表示法
- 二叉树:树中的每个节点最多有2个节点
- 二叉树:
- 可以为空,也就是没有节点;
- 不为空时,它是由根节点和左子树和右子树两个不交叉的二叉树组成
- 二叉树的五种形态
- 二叉树的特性
- 完美二叉树(Perfect Binary Tree)/满二叉树(Full Binary Tree):除了最下一层的的叶子节点外,每层节点都有两个节点,构成了满二叉树
- 完全二叉树(Complete Binary Tree):
- 二叉树存储常用的是数组和链表
4.3.1 数组表示
- 对于完全二叉树可以通过父子节点之间的关系求子节点的下标,数组只能表示完全二叉树
- 对于非完全二叉树要转化为完全二叉树才可以按照上面的方式进行存储,会造成很大的空间浪费,不建议使用
4.3.2 链表表示
- 二叉树最常见的表示方法是链表存储
- 每个节点封装成一个Node对象,Node中包含存储的数据,左节点的引用,右节点的引用
- 每个节点封装成一个Node对象,Node中包含存储的数据,左节点的引用,右节点的引用
4.4 二叉搜索树(BST)
- 二叉搜索树(Binary Search Tree),二叉排序树/二叉查找树
- 二叉搜索树特性:
- 为空时,没有节点
- 不为空时,满足以下性质:
- 非空左子树的键值小于根节点的键值
- 非空右子树的所有键值大于根节点的键值
- 左右字数本身也是一个二叉搜索数
- 二叉搜索树的特点
- 相对较小的值总是保存在最左边,相对较大的值总是保存在最右边
- 查找效率非常高
- BST采用的二分查找的思想
- 二叉所有树示意图
- BST方法
- insert(key):向树中插入一个新的键(节点);
- search(key):在书中查找一个键,如果节点存在,返回true;如果不存在,返回false;
- inOrdertraverse:通过中序遍历方式遍历所有节点;
- preorderTraverse:通过先序遍历方式遍历所有的节点;
- postOrdertraverse:通过后序遍历的方式遍历所有的节点;
- min:返回树中的最小值;
- max:返回树中的最大值;
- remove(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
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// 封装搜索二叉树
function BinarySearchTree() {
// 定义节点
function Node(key) {
this.key = key;
this.left = null;
this.right - null;
}
// 定义属性
this.root = null;
// 定义方法
// 1 insert(key):向外暴露的插入方法
BinarySearchTree.prototype.insert = function (key) {
// (1)根据key创建对应的方法
var newNode = new Node(key);
// (2)判断根节点是否存在
if (this.root == null) {
this.root = newNode;
} else {
//(3)递归调用查找
this.insertNode(this.root, newNode);
}
}
// 递归调用查找位置并插入节点
/*
- newNode:待插入的节点
- node:需要比较的节点
*/
BinarySearchTree.prototype.insertNode = function (node, newNode) {
// 向左子树插入节点
if (node.key > newNode.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);
}
}
}
// 2.获取最大值和最小值
/*
最小值:寻找二叉树中的最左边的节点,直到为null,返回上一个节点key
最大值:寻找二叉树中最右边的节点,直到为null,返回上一个节点的key
*/
BinarySearchTree.prototype.max = function () {
var node = this.root;
var key = null;
while (node) {
key = node.key;
node = node.right;
}
// 找到返回key
return key;
}
BinarySearchTree.prototype.min = function () {
var node = this.root;
var key = null;
while (node) {
key = node.key;
node = node.left;
}
return key;
}
// 搜索特定的值
BinarySearchTree.prototype.search = function (key) {
// 这里采用非递归的方式实现
var node = this.root;
//判断条件,node不为null的时候
while (node) {
if (key < node.key) {
node = node.left;
} else if (key > node.key) {
node = node.right;
} else {
// 相等返回true
return true;
}
}
// 找不到返回false
return false;
}
}搜索特定值
- 递归实现有问题,待解决
- 循环实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17BinarySearchTree.prototype.search = function (key) {
// 这里采用非递归的方式实现
var node = this.root;
//判断条件,node不为null的时候
while (node) {
if (key < node.key) {
node = node.left;
} else if (key > node.key) {
node = node.right;
} else {
// 相等返回true
return true;
}
}
// 找不到返回false
return false;
}remove方法
- 删除操作的思路
- 查找要删除节点,
- 找到之后按照下面的三种情况进行
- 叶子节点
- 只有一个子节点
- 有两个子节点
- 删除操作的示意图
- 删除两个节点的情况
- 前驱节点:左子树的最大值
- 后继节点”右子树的最小值
- 在删除两个节点时一般替换的元素要么是前驱节点,要么是后继节点
- 这里以后继节点为例
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// 3.删除操作
// 寻找后继节点
BinarySearchTree.prototype.getsuccessor = function (delNode) {
// 1.使用变量保存临时的节点
var successorParent = delNode
var successor = delNode
var current = delNode.right // 要从右子树开始找
// 2.寻找节点
while (current != null) {
successorParent = successor
successor = current
current = current.left
}
// 3.如果是删除图中15的情况, 还需要如下代码
if (successor != delNode.right) {
successorParent.left = successorParent.right
successor.right = delNode.right
}
return successor;
}
BinarySearchTree.prototype.remove = function (key) {
// 1.定义临时保存的变量
var current = this.root
var parent = this.root
var isLeftChild = true
if (current === null) return false
// 2.开始查找节点
while (current.key != key) {
parent = current;
if (key < current.key) {
isLeftChild = true;
current = current.left;
} else {
isLeftChild = false;
current = current.right;
}
// 如果发现current已经指向null, 那么说明没有找到要删除的数据
if (current === null) {
return false;
}
}
// 3.删除的结点是叶结点
if (current.left === null && current.right === null) {
if (current == this.root) {
this.root == null
} else if (isLeftChild) {
parent.left = null
} else {
parent.right = null
}
}
// 4.删除有一个子节点的节点
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
}
}
// 5.删除有两个节点的节点
else {
// 1.获取后继节点
var successor = this.getsuccessor(current);
// 2.判断是否是根节点
if (current == this.root) {
this.root = successor
} else if (isLeftChild) {
parent.left = successor
} else {
parent.right = successor
}
// 3.将删除节点的左子树赋值给successor
successor.left = current.left
}
return true
}
- 删除总结:
- 删除两个节点的情况
4.4.2 BST的缺陷
- 优势:
- 可以快速的找到给定关键字的数据项,并可以快速的插入和删除数据项
- 缺陷:插入有序的数据会出现不平衡的去年概况
- 非平衡树:
- 遍历针对所有的二叉树都适用
- 树的遍历方式分为三种
- 遍历过程
- 遍历过程
- 遍历过程
- 先序遍历左子树
- 先序遍历右子树
- 访问根节点
- 代码
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// 5.先序遍历
/*
这里的handle是一个句柄(回调函数),在调用方法的时候调用,这里通过该回调函数输出先序遍历的结果
*/
BinarySearchTree.prototype.preorderTraverse = function (handle) {
// 先序遍历,先访问根节点
this.preorderTraverseNode(this.root, handle);
}
// 通过递归先序遍历节点
BinarySearchTree.prototype.preorderTraverseNode = function (node, handle) {
if (node) {
handle(node.key);
// 先序遍历左节点
this.preorderTraverseNode(node.left, handle);
// 先序遍历左节点
this.preorderTraverseNode(node.right, handle);
}
}
// 6.中序遍历
BinarySearchTree.prototype.inOrdertraverse = function (handle) {
this.inOrdertraverseNode(this.root, handle);
}
BinarySearchTree.prototype.inOrdertraverseNode = function (node, handle) {
if (node) {
this.inOrdertraverseNode(node.left, handle);
handle(node.key);
this.inOrdertraverseNode(node.right, handle);
}
}
// 7.后序遍历
BinarySearchTree.prototype.postOrdertraverse = function (handle) {
this.postOrdertraverseNode(this.root, handle);
}
BinarySearchTree.prototype.postOrdertraverseNode = function (node, handle) {
if (node) {
this.postOrdertraverseNode(node.left, handle);
this.postOrdertraverseNode(node.right, handle);
handle(node.key);
}
} - 执行结果
4.6 红黑树
- BST存在的问题
- 当插入的是连续的值是会出现失去平衡的 情况,查找效率比较低
- 解决方案是:平衡树,平衡树有两种
- AVL:最早期的平衡树
- 红黑树
- AVL:是最早的平衡二叉树,平衡二叉树的时间复杂度:O(logN),每次插入和删除操作相对于红黑树效率都不高,整体效率不如红黑树
- 红黑树也通过一些特性来保持树的平衡
- 平衡树的时间复杂度O(logN)
- 删除插入操作红黑树的的性能都要优于AVL
4.6.1 红黑树的特性
- 符合二叉搜索树的基本规则
- 节点是红色或者黑色的
- 根节点是黑色的
- 每个叶子节点都是黑色的空节点(NIL节点)
- 每个红色节点的子节点都是黑色的(即从每个叶子节点到根节点没有两个连续的红色节点)
- 从任一节点到每个叶子节点都包含相同数目的黑色节点
4.6.2 红黑树的相对平衡
- 红黑树的特性决定了红黑树的关键特性:
- 从根到叶子的最长路径不会超过最短可能路径的两倍
- 结果就是这个树基本是平衡的
- 虽然没有做到绝对平衡,但是可以保证在最坏的情况下依然是高效的
- 最长路径不会超过最短路径的的原因:
- 插入一个新的节点,有可能导致树不在平衡,可以通过三种方式的变换,让树保持平衡
- 变色:重新符合红黑树的规则,尝试将红色变为黑色,黑色变为红色
- 左旋转
- 右旋转
- 插入的新节点通常都是红色节点
子节点不会受到影响
4.6.5 红黑树的插入操作
插入的情况:插入的节点为N,父节点为P,祖父节点为G,父亲的兄弟节点为U(P,U是同一个节点的子节点)
分为五中情况
1.新节点N位于根节点没有父节点
- 直接将红色变为黑色
2.新节点的父节点P是黑色
- 此时没有违背红黑树的规则
- 尽管新节点有两个黑色的叶子节点NIL ,但是新节点是红色的,所以通过他的路径中的黑色节点个数依然相同
3.P红U红
- P红U红祖黑->变换为:P黑U黑祖红
- P红U红祖黑->变换为:P黑U黑祖红
4.U黑且N是左孩子节点
- 父红U黑父黑且N是左孩子节点->变换为祖红父黑右旋转(注意旋转的时候始终是以当前待插入节点的父节点作为根进行旋转)
- 父红U黑父黑且N是左孩子节点->变换为祖红父黑右旋转(注意旋转的时候始终是以当前待插入节点的父节点作为根进行旋转)
4.U黑且N是右孩子节点
- 父红叔黑祖黑且N是右孩子节点->变换
- 以P为根节点进行左旋转,将P作为新插入的节点(旋转后将P及子节点作为整体看成新插入的节点)
- N红G黑,以N为根进行右旋转(规则四)
- 父红叔黑祖黑且N是右孩子节点->变换
注意:插入之后出现不平衡的情况时;将修改周后的部分作为整体看成待插入的红色节点,依次递归进行插入操作的变换
- 删除操作
本文作者:
SparkParis
本文链接: https://sparkparis.github.io/2020/04/15/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%843/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!
本文链接: https://sparkparis.github.io/2020/04/15/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%843/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!