6. 树
6.1 概念
6.2 二叉树
6.3 二叉搜索树
实际运用中常见的数据结构，一种特殊的二叉树
概念
- BST(Binary Search Tree)，也称二叉排序树或二叉查找树
- 如果不为空，满足性质：
- 特点：
- 相对较小的值保存在左节点，相对较大的值保存在右节点
- 这个特点使得查找效率非常高，包括查找最值和特定的值
- 利用二分查找思想：
- 查找所需最大次数等于二叉搜索树的深度
- 插入节点也可以如此，逐层比较找到新节点合适的位置
- 缺陷:
代码实现
-
常见操作
- insert(key)：插入一个新的键
- search(key)：查找键，存在返回true，否则返回false
- preOrderTraverse：先序遍历
- inOrderTraverse：中序遍历
- postOrderTraverse：后序遍历
- min：返回最小值
- max：返回最大值
- remove(key)：移除某个键
-
封装：
javascript">class Node{ constructor(){ this.key=key; this.left=null; this.right=null; } } export class BinarySearchTree{ constructor(){ this.root = null; } }
插入
javascript"> //插入操作(需要是一个可以进行比较的键)
insert(key){
//1.根据key创建节点
const newNode = new Node(key);
//2.判断原来的树是否空树
if(this.root === null){
this.root = newNode;
}else{
//调用插入节点方法递归查找到合适位置进行插入
this.insertNode(this.root,newNode);
}
}
//插入节点方法
insertNode(node,newNode){
if(newNode.key>node.key){
if(node.right === null){
node.right = newNode
}else{
this.insertNode(node.right,newNode)
}
}else{
if(node.left === null){
node.left = newNode
}else{
this.insertNode(node.left,newNode)
}
}
}
遍历
- 先序遍历 root->left->right
- 中序遍历 left-root->right
- 后序遍历 left->right->root
javascript"> //先序遍历
preOrderTraverse(){
//递归调用
this.preOrderTraverseNode(root);
}
preOrderTraverseNode(node){
if(node === null)return;
console.log(node.key);//先操作
this.preOrderTraverseNode(node.left);
this.preOrderTraverseNode(node.right);
}
//中序遍历
inOrderTraverse(){
//递归调用
this.inOrderTraverseNode(root);
}
inOrderTraverseNode(node){
if(node === null)return;
this.inOrderTraverseNode(node.left);
console.log(node.key);//中间操作
this.inOrderTraverseNode(node.right);
}
//后序遍历
postOrderTraverse(){
//递归调用
this.postOrderTraverseNode(root);
}
postOrderTraverseNode(node){
if(node === null)return;
this.postOrderTraverseNode(node.left);
this.postOrderTraverseNode(node.right);
console.log(node.key);//后操作
}
获取最值
javascript">
//获取最大值，一直右找
max(){
let node = this.root;
while(node.right!==null){
node = node.right;
}
return node.key;
}
//获取最小值，一直左找
min(){
let node = this.root;
while(node.left!==null){
node = node.left;
}
return node.key;
}
搜索
javascript"> //搜索操作
//递归实现
search(key){
this.searchNode(this.root,key)
}
searchNode(node,key){
if(node.key === key)return true;
if(key<node.key){
return this.searchNode(node.left,key);
}else if(key>node.key){
return this.searchNode(node.right,key);
}else{
return false;
}
}
//循环实现
search2(key){
let node = this.root;
while(node !== null){
if(key < node.key){
node = node.left;
}else if(key > node.key){
node = node.right;
}else{
return true;
}
}
return false
}
删除节点
有时为避免删除操作添加isDeleted标记,简单不改变树结构但浪费空间
-
找到要删除的节点，如果没有找到说明不需要删除
-
找到要删除的节点，三种情况
javascript">//删除操作
remove(key){
//1.定义一些变量记录状态
let current = this.root;
let parent = null;
let isLeftChild = true;
//2.开始查找要删除的节点
while(current.key !== key){
parent = null;
if(key<current.key){
isLeftChild = true;
current = current.left;
}else{
isLeftChild = false;
current = current.right;
}
if(current === null)return false;
}
//找到要删除的节点，记录为current,父节点为parent
//情况一：删除的节点是叶子节点
if(current.left === null && current.right === 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;
}
return true;
}
//情况三：有两个子节点
else{
//1.获取后继节点
let successer = this.getSuccesser(current);
//2.判断是否根节点
if(this.root === current){
this.root = successer;
}else if(isLeftChild){
parent.left = successer;
}else{
parent.right = successer;
}
successer.left = current.left;//原来的左子树赋给后继
}
return true;
}
//找到需要删除节点的后继(或前驱，方法一样)
getSuccesser(delNode){
//1.定义变量存储临时节点
let successerParent = delNode;
let successer = delNode;
let current = delNode.right;
//2.寻找节点（右子树最小节点）
while(current !== null){
successerParent = successer;
successer = current;
current = current.left;
}
//3.后继节点有右子节点（意味着后继节点不直接是delNode的右子节点）
if(successer !== delNode.right){
successerParent.left = successer.right;
successer.right = delNode.right;
}
return successer;
}
6.4 红黑树
红黑树概念
红黑树规则
除二叉搜索树基本规则,添加了五条特性
- 节点红色或黑色
- 根节点黑色
- 每个叶子节点都是黑色的空节点(NIL节点)
- 每个红色节点的两个子节点为黑色(从叶子节点到根的所有路径不能有两个及以上连续红色节点)
- 从任一节点到每个叶子节点的所有路径包含相同数目的黑色节点
