摘要:概述樹在前端的重要性就不言而喻了,隨處可見,,,,有時候前后端交互中也會收到具有遞歸性質的結構數據,需要注意一點的是中雖然出現了和數據結構,但其實現和其它語言例如中底層實現不同,在的中其實現基于,利用空間換時間的思想,畢竟查找起來而紅黑樹。
概述
樹在前端的重要性就不言而喻了,隨處可見,vdom,dom tree,render tree,有時候前后端交互中也會收到具有遞歸性質的tree結構數據,需要注意一點的是es6中雖然出現了set和map數據結構,但其實現和其它語言(例如java中)底層實現不同,在chrome的 v8中其實現基于hash,利用空間換時間的思想,畢竟查找起來hash O(1)而紅黑樹O(LgN)。但是紅黑樹作為一種經典且重要的數據結構,綜合優勢比較好,curd操作以及空間消耗在大量數據下優勢就體現出來了。
js實現const RED = true; const BLACK = false; class Node { constructor(key, value) { this.key = key; this.value = value; this.left = null; this.right = null; this.color = RED; } }
class RBT { constructor() { this.root = null; this.size = 0; } isRed(node) { if (!node) return BLACK; return node.color; } // 左旋 右紅左黑 leftRotate(node) { let tmp = node.right; node.right = tmp.left; tmp.left = node; tmp.color = node.color; node.color = RED; return tmp; } // 右旋轉 左紅左子紅 rightRoate(node) { let tmp = node.left; node.left = tmp.right; tmp.right = node; tmp.color = node.color; node.color = RED; return tmp; } // 顏色翻轉 flipColors(node) { node.color = RED; node.left.color = BLACK; node.right.color = BLACK; } add(key, value) { this.root = this.addRoot(this.root, key, value); this.root.color = BLACK; // 根節點始終是黑色 } addRoot(node, key, value) { if (!node) { this.size++; return new Node(key, value); } if (key < node.key) { node.left = this.addRoot(node.left, key, value); } else if (key > node.key) { node.right = this.addRoot(node.right, key, value); } else { node.value = value; } if (this.isRed(node.right) && !this.isRed((node.left))) { node = this.leftRotate(node); } if (this.isRed(node.left) && this.isRed((node.left.left))) { node = this.rightRoate(node); } if (this.isRed(node.left) && this.isRed(node.right)) { this.flipColors(node); } return node; } isEmpty() { return this.size == 0 ? true : false; } getSize() { return this.size; } contains(key) { let ans = ""; !(function getNode(node, key) { if (!node || key == node.key) { ans = node; return node; } else if (key > node.key) { return getNode(node.right, key); } else { return getNode(node.right, key); } })(this.root, key); return !!ans; } // bst前序遍歷(遞歸版本) preOrder(node = this.root) { if (node == null) return; console.log(node.key); this.preOrder(node.left); this.preOrder(node.right); } preOrderNR() { if (this.root == null) return; let stack = []; stack.push(this.root); while (stack.length > 0) { let curNode = stack.pop(); console.log(curNode.key); if (curNode.right != null) stack.push(curNode.right); if (curNode.left != null) curNode.push(curNode.left); } } // bst中序遍歷 inOrder(node = this.root) { if (node == null) return; this.inOrder(node.left); console.log(node.key); this.inOrder(node.right); } // bst后續遍歷 postOrder(node = this.root) { if (node == null) return; this.postOrder(node.left); this.postOrder(node.right); console.log(node.key); } // bsf + 隊列的方式實現層次遍歷 generateDepthString1() { let queue = []; queue.unshift(this.root); while (queue.length > 0) { let tmpqueue = []; let ans = []; queue.forEach(item => { ans.push(item.key); item.left ? tmpqueue.push(item.left) : ""; item.right ? tmpqueue.push(item.right) : ""; }); console.log(...ans); queue = tmpqueue; } } minmun(node = this.root) { if (node.left == null) return node; return this.minmun(node.left); } maximum(node = this.root) { if (node.right == null) return node; return this.maximum(node.right); } }
let btins = new RBT(); let ary = [5, 3, 6, 8, 4, 2]; ary.forEach(value => btins.add(value)); btins.generateDepthString1(); // /////////////// // 5 // // / // // 3 8 // // / / // // 2 4 6 // // /////////////// console.log(btins.minmun()); // 2 console.log(btins.maximum()); // 8圖解
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/100591.html
摘要:很多文章或書籍在介紹紅黑樹的時候直接上來就是紅黑樹的個基本性質插入刪除操作等。這也不奇怪,算法的作者就是紅黑樹的作者之一。所以,理解樹對掌握紅黑樹是至關重要的。 本文主要包括以下內容: 什么是2-3樹 2-3樹的插入操作 紅黑樹與2-3樹的等價關系 《算法4》和《算法導論》上關于紅黑樹的差異 紅黑樹的5條基本性質的分析 紅黑樹與2-3-4樹的等價關系 紅黑樹的插入、刪除操作 JDK ...
摘要:并且,我們的底層都是紅黑樹來實現的。紅黑樹是一種平衡二叉樹因此它沒有節點。 前言 聲明,本文用得是jdk1.8 前面已經講了Collection的總覽和剖析List集合: Collection總覽 List集合就這么簡單【源碼剖析】 原本我是打算繼續將Collection下的Set集合的,結果看了源碼發現:Set集合實際上就是HashMap來構建的! showImg(https:/...
摘要:用這種范例表示紅黑樹是可能的,但是這會改變一些性質并使算法復雜。插入會出現種情況為根節點,即紅黑樹的根節點。 說到HashMap,就一定要說到紅黑樹,紅黑樹作為一種自平衡二叉查找樹,是一種用途較廣的數據結構,在jdk1.8中使用紅黑樹提升HashMap的性能,今天就來說一說紅黑樹。 前言 限于篇幅,本文只對紅黑樹的基礎進行說明,暫不涉及源碼部分,大部分摘抄自維基百科,這里也貼出對應鏈接...
摘要:當往中放入新的鍵值對后,可能會破壞紅黑樹的性質。修復操作要重新使紅黑樹恢復平衡,修復操作的源碼分析如下方法分析如下上面對部分代碼邏輯就行了分析,通過配圖的形式解析了每段代碼邏輯所處理的情況。四總結本文可以看做是本人紅黑樹詳細分析一文的延續。 一、簡介 TreeMap最早出現在JDK 1.2中,是 Java 集合框架中比較重要一個的實現。TreeMap 底層基于紅黑樹實現,可保證在log...
摘要:需要執行的操作依次是首先,將紅黑樹當作一顆二叉查找樹,將該節點從二叉查找樹中刪除然后,通過旋轉和重新著色等一系列來修正該樹,使之重新成為一棵紅黑樹。 雖是讀書筆記,但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨 關于二叉樹的基本知識,可以參見:Java 實現基本數據結構 2(樹) 以下是算法導論第13章的學...
閱讀 882·2021-11-23 09:51
閱讀 1089·2021-11-15 17:57
閱讀 1667·2021-09-22 15:24
閱讀 812·2021-09-07 09:59
閱讀 2221·2019-08-29 15:10
閱讀 1849·2019-08-29 12:47
閱讀 751·2019-08-29 12:30
閱讀 3369·2019-08-26 13:51