分类 数据结构 下的文章

红黑树的实现 RBTree


红黑树的实现和2-3树的实现差不多,过程是一样的,如下
添加的新元素和叶子节点结合,如果叶子节点已经有两个元素,则暂时形成三元素
永远添加红色节点
github:https://github.com/Lxido/data-struct/blob/master/tree/rb-tree/RBTree.php
  • 红黑树和avl树一样都需要左旋转和右旋转,而且比avl树的计算次数更少


红黑树 &2-3树


  • 满足的条件 (摘自 算法导论第三版)

    是一颗二分搜索树
    每个节点或者是红色的,或者是黑色的
    根节点是黑色的
    每个叶子节点(最后的空节点)是黑色的
    如果一个节点是红色的,那么他的孩子节点都是黑色的
    从任意一个节点到叶子节点,经过的黑色节点是一样的
    


平衡树和AVL树


今天来聊一下利用php实现一颗AVL树,顺便记录一下自己的学习情况吧。github地址https://github.com/Lxido/data-struct/blob/master/tree/avl/AvlTree.php

AVL树是二分搜索树的一种,他在二分搜索树的基础上市一颗完全的平衡二叉树,这样的主要效果是解决二分搜索树在极端情况下会退化成一条链条的情况(1),大大的提高了性能,充分利用了空间,减少了二分搜索树的高度,因为二分搜索树的时间复杂度直接是和树的高度相关,树的高度越大性能越差