节点高度:从节点到任意子节点的彼岸的最大值。这个相对来说容易理解。那么获得节点高度的代码实现如下:
getNodeHeight(node) {
if (node == null) {
return -1;
}
return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
}
平衡因子:每个节点左子树高度和右子树高度的差值。该值为0 、 -1、 1 时则为正常值,说明该二叉树已经平衡。若果该值不是这三个值之一,则需要平衡该树。遵循计算一个节点的平衡因子并返回其值的代码如下:
const BalanceFactor = {
UNBALANCED_RIGHT: 1,
SLIGHTLY_UNBALANCED_RIGHT: 2,
BALANCED: 3,
SLIGHTLY_UNBALANCED_LEFT: 4,
UNBALANCED_LEFT: 5
};
getBalanceFactor(node) {
const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
switch (heightDifference) {
case -2:
return BalanceFactor.UNBALANCED_RIGHT;
case -1:
return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
case 1:
return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
case 2:
return BalanceFactor.UNBALANCED_LEFT;
default:
return BalanceFactor.BALANCED;
}
}
AVL树是一种自平衡树,添加或移除节点时,AVL会尝试保持自平衡,也就是会可能尝试转换为完全树。接下来介绍平衡树进行自平衡的操作,AVL旋转
在对AVL进行添加或者移除节点后,我们需要计算节点的高度并验证是否需要进行平衡。旋转操作分为单旋转和双旋转两种。
/**
* Left left case: rotate right
*
* b a
* / \ / \
* a e -> rotationLL(b) -> c b
* / \ / \
* c d d e
*
* @param node Node<T>
*/
rotationLL(node){
const tmp = node.right;
node.left = tmp.right;
tmp.right = node;
return tmp;
}
/**
* Right right case: rotate left
*
* a b
* / \ / \
* c b -> rotationRR(a) -> a e
* / \ / \
* d e c d
*
* @param node Node<T>
*/
rotationLL(node) {
const tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
}
/**
* Left right case: rotate left then right
* @param node Node<T>
*/
rotationLR(node) {
node.left = this.rotationRR(node.left);
return this.rotationLL(node);
}
/**
* Right left case: rotate right then left
* @param node Node<T>
*/
rotationRL(node) {
node.right = this.rotationLL(node.right);
return this.rotationRR(node);
}
完成平衡操作(旋转)的学习后,我们接下来完善一下AVL树添加或者移除节点的操作
insert(key) {
this.root = this.insertNode(this.root, key);
}
insertNode(node, key) {
if (node == null) {
return new Node(key);
} if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
node.left = this.insertNode(node.left, key);
} else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
node.right = this.insertNode(node.right, key);
} else {
return node; // duplicated key
}
// verify if tree is balanced
const balanceFactor = this.getBalanceFactor(node);
if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
// Left left case
node = this.rotationLL(node);
} else {
// Left right case
return this.rotationLR(node);
}
}
if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
if (this.compareFn(key, node.right.key) === Compare.BIGGER_THAN) {
// Right right case
node = this.rotationRR(node);
} else {
// Right left case
return this.rotationRL(node);
}
}
return node;
}
removeNode(node, key) {
node = super.removeNode(node, key); // {1}
if (node == null) {
return node;
}
// verify if tree is balanced
const balanceFactor = this.getBalanceFactor(node);
if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
// Left left case
if (
this.getBalanceFactor(node.left) === BalanceFactor.BALANCED
|| this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
) {
return this.rotationLL(node);
}
// Left right case
if (this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
return this.rotationLR(node.left);
}
}
if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
// Right right case
if (
this.getBalanceFactor(node.right) === BalanceFactor.BALANCED
|| this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
) {
return this.rotationRR(node);
}
// Right left case
if (this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
return this.rotationRL(node.right);
}
}
return node;
}
}
以上就是关于AVL树基础知识的学习,接下来我们介绍另一种平衡树——红黑树。
和AVL树一样,红黑树也是一个自平衡二叉树。红黑树本质上也是AVL树,但可以包含多次插入和删除。在红黑树中,每个节点都遵循以下规则:
const BalanceFactor = {
UNBALANCED_RIGHT: 1,
SLIGHTLY_UNBALANCED_RIGHT: 2,
BALANCED: 3,
SLIGHTLY_UNBALANCED_LEFT: 4,
UNBALANCED_LEFT: 5
};
//定义颜色类
const Colors = {
RED:'red',
BLACK:'black'
};
//创建红黑树的节点类型
class RedBlackNode extends Node{
constructor(key){
super(key);
this.key = key;
this.color = Colors.RED;
this.parent = null;
}
isRed(){
return this.color === Colors.RED;
}
};
class RedBlackTree extends BinarySearchTree{
constructor(compareFn = defaultCompare){
super(compareFn);
this.compareFn = compareFn;
this.root = null;
};
}
//rotationLL
static rotationLL(node){
const tmp = node.left;
node.left = tmp.right;
if(tmp.right && tmp.right.key){
tmp.right.parent = node;
}
tmp.right.parent = node.parent;
if (!node.parent){
this.root = tmp;
}else{
if(node === node.parent.left){
node.parent.left = tmp;
}else{
node.parent.right = tmp;
}
tmp.right = node;
node.parent = tmp;
}
};
//rotationRR
static rotationRR(node){
const tmp = node.right;
node.right = tmp.left;
if (tmp.left && tmp.left.key){
tmp.left.parent = node;
}
tmp.parent = node.parent;
if (!node.parent){
this.root = tmp;
}else{
if(node === node.parent.left){
node.parent.left = tmp;
}else{
node.parent.right = tmp;
}
}
tmp.left = node;
node.parent = tmp;
}
//插入节点后验证红黑树的属性
static fixTreeProperties(node){
while (node && node.parent && node.parent.color.isRed() && node.color !== Colors.BLACK){
let parent = node.parent;
const grandParent = parent.parent;
//case A:父节点是左侧子节点
if (grandParent && grandParent.left === parent){
const uncle = grandParent.right;
//case 1A:叔节点也是红色——只需要重新填色
if (uncle && uncle.color === Colors.RED){
grandParent.color = Colors.RED;
parent.color = Colors.BLACK;
uncle.color = Colors.BLACK;
node = grandParent;
}else{
// case 2A:节点是右侧子节点——右旋转
if (node === parent.left){
RedBlackTree.rotationRR(parent);
node = parent;
parent = node.parent;
}
//case 3A:子节点是左侧子节点——左旋转
else if(node === parent.right){
RedBlackTree.rotationRR(grandParent);
parent.color = Colors.BLACK;
grandParent.color = Colors.RED;
node = parent;
}
}
}
//case B:父节点是右侧子节点
else{
const uncle = grandParent.left;
//case1B:叔节点是红色——只需要重新填色
if(uncle && uncle.color === Colors.RED){
grandParent.color = Colors.RED;
parent.color = Colors.BLACK;
uncle.color = Colors.BLACK;
node = grandParent;
}
//case2B:节点是左侧子节点—右旋转
if (node === parent.left){
RedBlackTree.rotationLL(parent);
node = parent;
parent = node.parent;
}
//case3B:节点是右侧子节点——左旋转
else if(node === parent.right){
RedBlackTree.rotationRR(grandParent);
parent.color = Colors.BLACK;
grandParent.color = Colors.RED;
node = parent;
}
}
this.root.color = Colors.BLACK;
}
}
//向红黑树插入新节点
insertNode(node,key){
if(this.compareFn(key,node.key) === Compare.LESS_THAN){
if(node.left === null){
node.left = new RedBlackNode(key);
node.left.parent = node;
return node.left;
}
else{
return this.insertNode(node.left,key);
}
}
else if(node.right === null){
node.right = new RedBlackNode(key);
node.right.parent = node;
return node.right;
}
};
insert(key) {
if (this.root === null){
this.root = new RedBlackNode(key);
this.root.color = Colors.BLACK;
}else{
const newNode = this.insertNode(this.root, key);
RedBlackTree.fixTreeProperties(newNode);
}
};
Js二叉树排序实现:1初始化二叉树,2二叉树的遍历,3查找最小值,4查找最大值,5删除节点
当变量指向一个对象的时候,实际指向的是存储地址,数组转树的方式:第一次遍历将数组转节点对象,存储到新的对象里,id为键值方便索引,第二次遍历根据索引插入子节点
计算机科学中最常用和讨论最多的数据结构之一是二叉搜索树。这通常是引入的第一个具有非线性插入算法的数据结构。二叉搜索树类似于双链表,每个节点包含一些数据,以及两个指向其他节点的指针;它们在这些节点彼此相关联的方式上有所不同
JS 将有父子关系的平行数组转换成树形数据:方法一:双重遍历,一次遍历parentId,一次遍历id == parendId;该方法应该能很容易被想到,实现起来也一步一步可以摸索出来;
在编写树形组件时遇到的问题:组件如何才能递归调用?递归组件点击事件如何传递?组件目录及数据结构;在组件模板内调用自身必须明确定义组件的name属性,并且递归调用时组件名称就是name属性
在计算机科学中,抽象语法树(Abstract Syntax Tree,AST),或简称语法树(Syntax tree),是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构,树上的每个节点都表示源代码中的一种结构
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
最近项目又频繁需要对扁平结构进行树形转换,这个算法从我最早接触的时候使用了递归,到现在的单次循环完成,简单记录一下算法的演变,算是对树形算法的一个简单记录,这种类型的算法在项目中的使用挺多的
大概因为平时工作项目的原因,写了很多次树形组件,越写越觉得可以写得更简单并且更具有复用性、扩展性。树组件的应用场景很多,比如一篇文章的目录、一个公司部门组织情况、思维导图等,其实都可以用树形结构来描述
经常有同学问树结构的相关操作,也写了很多次,在这里总结一下JS树形结构一些操作的实现思路,并给出了简洁易懂的代码实现。本文内容结构大概如下:
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!