国内最专业的IT技术学习网

UI设计

当前位置:主页 > UI设计 >

图解“红黑树”原理,一看就明白!

发布时间:2019/08/28标签:   节点    点击量:

原标题:图解“红黑树”原理,一看就明白!
【51CTO.com原创稿件】学过数据构造都晓得二叉树的观点,而又有多种比拟罕见的二叉树范例,比方完整二叉树、满二叉树、二叉搜寻树、平衡二叉树、完善二叉树等。图片来自 Pexels明天咱们要说的红黑树就是就是一棵非严厉平衡的二叉树,平衡二叉树又是在二叉搜寻树的基本上增添了主动保持均衡的性子,拔出、搜寻、删除的效力都比拟高。红黑树也是完成 TreeMap 存储构造的基石。二叉搜寻树二叉搜寻树又叫二叉查找树、二叉排序树,咱们先看一下典范的二叉搜寻树,如许的二叉树有何规矩特色呢?二叉搜寻树有以下几个特色: 节点的左子树小于节点自身 节点的右子树大于节点自身 阁下子树一样为二叉搜寻树下图就是一棵典范的二叉搜寻树:二叉搜寻树是平衡二叉树的基本,咱们看一下它的搜寻步调怎样。咱们要从二叉树中找到值为 58 的节点。第一步:起首查找到根节点,值为 60 的节点。第二步:比拟咱们要找的值 58 与该节点的巨细。假如即是,那末祝贺,曾经找到;假如小于,持续找左子树;假如大于,那末找右子树。很显明 58<60,因而咱们找到左子树的节点 56,此时咱们曾经定位到了节点 56。第三步:依照第二步的规矩持续找。58>56 咱们须要持续找右子树,定位到了右子树节点 58,祝贺,此时咱们曾经找到了。咱们经由三步就曾经找到了,实在就是咱们平常所说的二分查找,这类二叉搜寻树似乎查找效力很高,但一样它也出缺陷,以下面如许的二叉搜寻树。看到如许的二叉搜寻树能否很顺当,典范的大长腿瘸子,但它也是二叉搜寻树,假如咱们要找值为 50 的节点,基础上和单链表查问没多大差别了,机能将大打扣头。这个时间咱们的平衡二叉树就粉墨退场了,平衡二叉树就是在二叉搜寻树的基本上增加了主动保持均衡的性子。下面的大长腿瘸子二叉搜寻树经由主动均衡后,能够就成为了上面如许的二叉树。

版权信息Copyright ? IT技术教程 版权所有??? ICP备案编号:鲁ICP备09013610号