From c975ced620ee01bdc815169caf1b9d80f8e18f29 Mon Sep 17 00:00:00 2001
From: Ir1d <sirius.caffrey@gmail.com>
Date: Wed, 16 Jan 2019 16:29:50 +0800
Subject: [PATCH] feat: avl

---
 docs/ds/avl.md | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/docs/ds/avl.md b/docs/ds/avl.md
index 8b137891..8b8c7791 100644
--- a/docs/ds/avl.md
+++ b/docs/ds/avl.md
@@ -1 +1,21 @@
+AVL 树，是一种平衡的二叉搜索树
+
+## 性质
+
+1. 空二叉树是一个 AVL 树
+2. 如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且 $|h(ls) - h(rs) \leq 1|$， h 是其左右子树的高度
+3. 树高为 $O(\log n)$
+
+平衡因子：右子树高度- 左子树高度
+
+## 插入结点
+
+与 BST（二叉搜索树）中类似，先进行一次失败的查找来确定插入的位置，插入节点后根据平衡因子来决定是否需要调整。
+
+## 删除结点
+
+删除和 BST 类似，将结点与后继交换后再删除。
+
+删除会导致树高以及平衡因子变化，这时需要沿着被删除结点到根的路径来调整这种变化。
+
 
-- 
2.11.0