Javascript

数据结构与算法-树(Tree)-JS

本文主要是介绍数据结构与算法-树(Tree)-JS,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

数据结构与算法-树(Tree)-JS

数组优点:

1.根据下表中访问效率很高;

2.倘若希望根据元素查找对应的位置,比较好的方式是先对数组进行排序,在进行二分查找

数组缺点:

1.需要先对数组进行排序,生成有序数组,才能提高查找效率;

2.另外数组在插入和删除数据时,需要有大量的位移操作,效率很低

链表优点:

插入和删除操作效率都很高

链表缺点:

1.查找效率很低,需要从头开始依次访问查找;

2.而且即使插入和删除效率很高,但是如果插入和删除中间位置的数据,还是需要从头先找到对应的数据

哈希表优点:

插入、查询、删除效率都是非常高的

哈希表缺点:

1.空间利用率不高,需要设置总长度二倍的空间,底层使用的是数据,并且某些单元没有被利用;

2.哈希表中的元素时无序的,不能按照固定的顺序来遍历哈希表中的元素;

3.不嫩快速找出哈希表中的最大者或者最小者这些特殊值。

树优点:

不能说明树结构比其他结构都要好,因为每种数据结构都有自己特定的应用场景。

1.空间利用率是非常高的;

2.相对于哈希表来说,利用率高,而且所有元素都是有序的,可以按照某些顺序进行遍历的,可以非常快速地查找到最大值、最小值;

3.某些场景,使用树结构跟家方便,因为树结构是非线性的,可以表示一对多的关系

树缺点:

查找某个值的效率比列表要快,但比哈希表慢;

树的术语:

节点的度(Degree):节点的子树个数;

树的度:树的所有节点中最大的度数;

叶节点/叶子节点(Leaf):度为0的节点;

父节点(Parent);子节点(Child);

兄弟节点(Sibling):具有同一个父节点的各节点彼此是兄弟节点;

路径和路径长度:一个节点到另一个节点的路径,路径长度取决于路径中的边的个数;

节点的层次(Level):规定根节点在1层,其他节点的层数依次加一;树的深度(Depth):树中所有节点中的最大层次是这棵树的深度。

其实所有的树本质上都可以使用二叉树模拟出来

二叉树有五种形态:

空(没有任何节点);只有根节点;根节点和左子节点;根节点和右节点、根节点和左右子节点

二叉树的特性:

1.一个二叉树第i层的最大节点数为2^(i-1),i>=1;

2.深度为k的二叉树的节点总数的最大值为:2^k-1,k>=1;

3.对任何非空二叉树T,若n0表示叶节点的个数,n2表示度为2的非叶节点个数,那么二者关系为n0=n2+1.

满二叉树(完美二叉树Perfect Binary Tree):

除了最下层的叶节点外,每层节点都有两个子节点;且刚好完全铺满

完全二叉树(Complete Binary Tree):

除了最后一层外,其他各层都达到了最大个数,且最后一层从左向右的叶节点连续存在,不能跳着有节点,完美二叉树是特殊的完全二叉树

完全二叉树才可以使用数组进行存储,如果是一般的二叉树,使用数组存储的话会浪费空间;

二叉树最常见的方式是使用链表存储

二叉搜索树(BST,Binary Search Tree),也叫二叉排序树或二叉查找树

二叉搜索树是一颗二叉树,可以为空;

如果不为空,满足以下性质:

1.非空左子树的所有键值小于其根节点的键值;

2.非空右子树的所有键值大于其根节点的键值;

3.左、右子树本身也都是二叉搜索树。

二叉搜索树的特点:

相对较小的值总是保存在左节点上,相对较大的值总是保存在右节点上,这个特点可以使查找效率非常高,这也是二叉搜索树中搜索的来源。

//封装二叉搜索树
function BinarySearchTree() {
    //内部类节点
    function Node(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    //属性
    this.root = null;
    //方法
    //插入数据:对外给用户调用的方法
    BinarySearchTree.prototype.insert = function (key) {
        //根据key创建节点
        var newNode = new Node(key);
        //判断根节点是否有值
        if (this.root == null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        } 
    }
    //内部使用的插入方法,用于比较两个节点值的大小
    BinarySearchTree.prototype.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);
            }
        }
    }
    //二叉树的遍历常见有三种方式:先序遍历、中序遍历、后序遍历,还有层序遍历,从第一层开始一层一层从左到右进行遍历,这个使用较少,可以使用队列来完成。
    //先序遍历:1.访问根节点2.先序遍历其左子树3.先序遍历其右子树
    BinarySearchTree.prototype.preOrderTraversal = function (handler) {
        this.preOrderTraversalNode(this.root, handler);
    }
    //如果理解费劲可以画个二叉树的图
    BinarySearchTree.prototype.preOrderTraversalNode = function (node, handler) {
        if (node != null) {
            //处理经过的节点
            //这也是叫先序的原因,是先对node进行处理,处理完之后再去找其他节点
            //先序还可以理解为啥时候处理根节点,在最最前面处理根节点叫做先序
            handler(node.key);
            //查找经过节点的左子节点
            this.preOrderTraversalNode(node.left, handler);
            //查找经过节点的右子节点
            this.preOrderTraversalNode(node.right, handler);
        }
    }
    //中序遍历:1.中序遍历其左子树2.访问根节点3.中序遍历其右子树
    BinarySearchTree.prototype.midOrderTraversal = function (handler) {
        this.midOrderTraversalNode(this.root, handler);
    }
    BinarySearchTree.prototype.midOrderTraversalNode = function (node, handler) {
        if (node != null) {
            //查找左子树中的节点,最开始递归后找到左子树最左边那个节点
            this.midOrderTraversalNode(node.left, handler);
            //处理节点
            handler(node.key);
            //查找右子树中的节点
            this.midOrderTraversalNode(node.right, handler);
        }
    }
    //后序遍历:1.后序遍历其左子树2.后序遍历其右子树3.访问根节点
    BinarySearchTree.prototype.postOrderTraversal = function (handler) {
        this.postOrderTraversalNode(this.root, handler);
    }
    BinarySearchTree.prototype.postOrderTraversalNode = function (node, handler) {
        if (node != null) {
            //查找左子树中的节点
            this.postOrderTraversalNode(node.left, handler) ;
            //查找右子树中的节点
            this.postOrderTraversalNode(node.right, handler);
            //处理节点
            handler(node.key);
        }
    }
    //寻找最值
    //寻找最大值
    BinarySearchTree.prototype.max = function () {
        //获取根节点
        var node = this.root;
        //一次向右不断地查找,直到节点为null
        while (node.right != null) {
            node = node.right;
        }
        return node.key;
    }
    //寻找最小值
    BinarySearchTree.prototype.min = function () {
        //获取根节点
        var node = this.root;
        //一次向右不断地查找,直到节点为null
        while (node.left != null) {
            node = node.left;
        }
        return node.key;
    }
    //搜索特定值,搜索到了返回true
    // //采用递归算法
    // BinarySearchTree.prototype.search = function (key) {
    //     return this.searchNode(this.root, key);
    // }
    // BinarySearchTree.prototype.searchNode = function (node, key) {
    //     //如果传入的node为null,那么就退出递归
    //     if (node == null) {
    //         return false;
    //     }
    //     //判断node节点的值和传入的key大小
    //     if (key < node.key) {
    //         return this.searchNode(node.left, key);
    //     } else if (key > node.key) {
    //         return this.searchNode(node.right, key);
    //     } else {
    //         return true;
    //     }
    // }
    //使用循环实现
    BinarySearchTree.prototype.search = function (key) {
        //获取根节点
        var node = this.root;
        //循环key
        while (node != null) {
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
                return true;
            }
        }
        return false;
    }
    //二叉搜索树的节点的删除
    //1.先找到要删除的节点,如果没有找到,不需要删除2.找到要删除的节点,分三种情况讨论
    //1删除叶子节点2删除只有一个子节点的节点3删除有两个子节点的节点
    //删除节点
    BinarySearchTree.prototype.remove = function (key) {
        //寻找要删除的节点
        var current = this.root;
        var parent = null;
        var isLeftChild = true; //是否是左节点
        //开始寻找删除的节点
        while (current.key != key) {
            parent = current;
            if (key < current.key) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
            //已经找到最后的节点,依然没有找到等于key的节点
            if (current == null) return false;
        }
        //根据对应的情况删除节点
        //删除的节点时叶子节点(没有子节点)
        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;
            }
        //删除的节点有两个子节点
        } else {
            //比较难理解,需要画图理解
            //如果我们要删除的节点有两个子节点,甚至子节点还有子节点,我们需要从下面的子节点中找到一个节点来替换当前的节点
            //这个节点的特征就是current节点下面所有的节点中最接近current的节点
            //比current小一点点的节点,一定是current左子树的最大值;臂current大一点点的节点,一定是current右子树的最小值
            //前驱和后继
            //比current小一点点的节点,称为current节点的前驱;比current大一点点的节点,称为current节点的后继
            //在这里实现找后继
            //获取后继节点
            var successor = this.getSuccssor(current);
            //判断是否为根节点
            if (current == this.root) {
                this.root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            //将删除节点的左子树 = current.left
            successor.left = current.left;
        }
    }
    BinarySearchTree.prototype.getSuccssor = function (delNode) {
        //定义变量,保存找到的后继
        var successor = delNode;
        var current = delNode.right;
        var successorParent = null;
        //循环查找
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }
        //判断寻找的后继节点是否直接就是delNode的right节点
        if (successor != delNode.right) {
            successorParent.left = successor.right;
            successor.right = delNode.right;
        }
        return successor;
    }
}


//测试代码
//创建BinarySearchTree
var bst = new BinarySearchTree();
//插入数据
bst.insert(11);       
bst.insert(7);       
bst.insert(15);       
bst.insert(5);       
bst.insert(3);     
bst.insert(9);
bst.insert(8);
bst.insert(10);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);
bst.insert(6);
//测试先序遍历
var resultString = '';
bst.preOrderTraversal(function (key) {
    resultString += key + " ";
})
// alert(resultString); //11 7 5 3 6 9 8 10 15 13 12 14 20 18 25 
//测试中序遍历
resultString = '';
bst.midOrderTraversal(function (key) {
    resultString += key + " ";
})
// alert(resultString); //3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
//测试后序遍历
resultString = '';
bst.postOrderTraversal(function (key) {
    resultString += key + " ";
})
// alert(resultString); //3 6 5 8 10 9 7 12 14 13 18 25 20 15 11 
// //测试最值
// alert(bst.max());
// alert(bst.min());
// //测试搜索方法
// alert(bst.search(25));
// alert(bst.search(2));
//测试删除代码
bst.remove(9);
bst.remove(7);
bst.remove(15);
resultString = '';
bst.postOrderTraversal(function (key) {
    resultString += key + " ";
})
alert(resultString); //3 6 5 10 8 12 14 13 25 20 18 11 

非平衡树:

比较好的二叉搜索树数据应该是左右均匀分布的,如果插入的数据是有序的数据,分布不均匀,就叫做非平衡树。

平衡二叉树的插入或查找的效率是O(logN),和深度有关系;非平衡二叉树,相当于编写了一个链表,查找效率变成了O(N)

所以需要保证树总是平衡的,即每个节点左边的子孙节点个数尽可能等于右边的子孙节点的个数

常见的平衡树有AVL树和红黑树

AVL树是最早的一种平衡树,使用每个节点多存储一个额外的数据的方法保持树的平衡,时间复杂度为为O(logN),但是每次插入或删除操作的效率相对于红黑树来说不高,所以整体效率不如红黑树

红黑树的时间复杂度也是O(logN),现在平衡树的应用基本都是红黑树

红黑树的规则:

1.节点时红色或黑色

2.根节点是黑色

3.每个叶子节点都是黑色的空节点(NIL节点)

4.每个红色节点的两个子节点都是黑色(从每个叶子节点到根节点的所有路径上不能有两个连续的红色节点)

5.从任一节点到其每个叶子的所有路径都包含相同数据的黑色节点

前面的约束确保了红黑树的关键特性:从根到叶子的最长可能路径,不会超过最短可能路径的两倍长,结果就是这个树基本是平衡的,虽然没有做到绝对的平衡,但是可以保证在最坏的情况下,依然是高效的。

为什么可以做到最长路径不超过最短路径的二倍?性质4决定了路径不能有两个相连的红色节点,最短的可能路径都是黑色的节点,最长的可能路径是红色和黑色交替,性质5所有路径都有相同数目的黑色节点,这就表明了最长的路径只能是红黑一直相互交替,表明了没有路径能多于任何其他路径的两倍长。

插入一个新节点时,有可能树不再平衡,可以通过三种方式的变换,让树保持平衡:换色;左旋转;有旋转

变色:

为了重新复核红黑树的规则,尝试吧红色节点变为黑色,或者把黑色节点变为红色。

首先,需要知道插入的新节点通常都是红色节点,因为在插入节点为红色的时候,有可能插入一次是不违反红黑树任何规则的,而插入黑色节点,必然会导致一条路径上多了黑色节点,这是很难调整的,插入红色节点可能导致红红相连的情况,但是这种情况可以通过颜色调换和旋转来调整。

左旋转:

逆时针旋转红黑树的两个节点,使得父节点被自己的右孩子取代,而自己成为自己的左孩子;右旋转:顺时针旋转红黑树的两个节点,使得父节点被自己的左孩子取代,而自己成为自己的右孩子。

插入一个新节点会有五种情况:设要插入的节点为N,其父节点为P,其祖父节点为G,其父亲的兄弟节点为U。

情况一:新节点N位于树的根上,没有父节点,这种情况下,直接将红色编程黑色即可,这样满足性质2。

情况二:新节点的父节点P是黑色,性质4没有失效,性质5也没有问题,尽管新节点N有两个黑色的叶子结点NIL,但是新节点N是红色的,所以通过它的路径中黑色节点的个数依然相同,满足性质5。

情况三:P为红色,U为红色,G为黑色,将P和U变换为黑色,并且将G变换为红色,每条路径上的黑色节点的数目没有改变。可能出现的问题:N的祖父节点G的父节点也可能是红色,这就违反了性质3,可以递归地调整颜色,但是如果递归调整颜色到了根节点,就需要进行旋转了,下面会有例子讲到。

情况四:P红U黑G黑,N为左儿子,方案,P黑,G红,GP进行右旋转,也可以将旋转与变色的顺序互换。

情况五:P红U黑G黑,N是右儿子,方案,PN进行左旋转,形成情况四的结果,最祖父节点G进行一次右旋转,并且改变颜色即可。

案例:依次插入10 9 8 7 6 5 4 3 2 1

插入10(将节点10的颜色变为黑色)=>插入9(不需要用任何变换)=>插入8(情况四,父变黑,祖变红,父和祖有旋转)=>插入7(符合情况三,父变黑,叔变黑,祖变红,不满足性质2,只需要把根节点变为黑色就可以了)=>插入6(情况四,父变黑,祖变红,父和祖进行右旋转)=>插入5(情况三,父和叔变黑,祖变红)=>插入4(情况四,父变黑,祖变红,父和祖进行右旋转)=>插入3(情况三,父变黑,叔变黑,祖变红,此时5和7是挨着的红色,是情况四,7变黑,9变红,7和9进行右旋转)=>插入2(情况四,父3变黑,祖4变红,父3祖4进行右旋转)=>插入1(情况三,父2变黑,叔4变黑,祖3变红,此时3和5是挨着的红色,把3以下看做新插入的红色节点,父5变黑,叔9变黑,祖7变红,根节点不满足性质2,将根节点7变黑)

红黑树的删除,需要将二叉搜索树的删除操作和红黑树的插入规则结合起来,难度非常大,需要考虑删除中间节点的话会不会对后序的子节点产生影响,而且一旦删除后会不会对红黑树的整个规则产生影响。

红黑树的插入和删除的代码,需要按照之前分析的不同情况进行分析。前端就先了解到这里,如果需要学习和了解其他后端语言以及其源码,比如Java、Python、Go等,可以再深入了解代码实现。

这篇关于数据结构与算法-树(Tree)-JS的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!